Single Linked List

Single Linked List

---

Single Linked List(단일 연결 리스트)는 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

 

-header : 리스트의 가장 첫번째에 위치하는 Node이며 Node를 찾기 위해서는 header부터 탐색을 해야한다

-Node(노드) : 데이터 저장 단위(데이터값, 포인터)로 구성

-Pointer(포인터) : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

Single Linked List의 특징

---

• 노드의 삽입, 삭제 작업이 용이하다.
• 배열은 미리 데이터 공간을 할당 해야 하지만 링크드 리스트는 미리 데이터 공간을 할당하지 않아도 된다.
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않다.
• 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.
• 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.
• 트리를 표현할 때 가장 적합한 자료 구조이다.

 

Single Linked List 구현해보기

---

public class SingleLinkedList<T> {
    
    //Linked List의 head
    public Node<T> head = null;
    
    //각각의 Node를 구현한 inner class
    public class Node<T> {
        T data;
        //다음의 Node 주소가 저장되는 pointer
        Node<T> next = null;
        
        public Node(T data) {
            this.data = data;                          
        }
    }
    
    //Node를 추가하는 메소드
    public void addNode(T data) {
        if (head == null) {
            //head가 null 즉 처음 들어온 data인 경우 head에 data 추가
            head = new Node<T>(data);
        } else {
            //첫 Node를 시작으로 마지막 Node까지 찾아가는 과정
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            //마지막 Node에 왔을 시 마지막 Node의 next에 parameter로 받은 data를 대입 
            node.next = new Node<T>(data);
        }
    }
    
    //모든 Linked List를 보여주는 메소드
    public void printAll() {
        if (head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }
    
    //찾고싶은 Node를 검색하는 메소드
    public Node<T> search(T data) {
        if (this.head == null) {
            return null;
        } else {
            Node<T> node = this.head;            
            while (node != null) { 
                if (node.data == data) {
                    return node;
                } else {
                    node = node.next;
                }
            }
            return null;
        }
    }
    
    //existedData뒤에 addData를 추가하는 메소드
    public void addNodeInside(T existedData, T addData) {
        Node<T> searchedNode = this.search(existedData);
        
        if (searchedNode == null) {
            //검색된 data가 없으면 마지막에 Node 추가
            this.addNode(addData);
        } else {
            //스와핑
            Node<T> nextNode = searchedNode.next;
            searchedNode.next = new Node<T>(addData);
            searchedNode.next.next = nextNode;
        }
    }
    
    //Node를 삭제하는 메소드
    public boolean delNode(T data) {
        if (this.head == null) {
            return false;
        } else {
            Node<T> node = this.head;
            if (node.data == data) {
                //head와 일치할 경우 head의 다음 Node를 head로 변경
                this.head = this.head.next;
                return true;
            } else {
                while (node.next != null) {
                    if (node.next.data == data) {
                        node.next = node.next.next;
                        return true;
                    }
                    node = node.next;
                }
                return false;
            }
        }
    }
}