[자료구조] 연결 리스트(Linked List) 알아보기

이번 게시글에서는 연결 리스트에 대해서 알아보도록 하겠습니다. 또 다른 말로는 링크드 리스트라고도 합니다.
이러한 연결 리스트에는 단일 연결 리스트와 이중 연결 리스트로 두 가지 방식이 있는데요. 단일 연결 리스트의 단점을 보완하기 위해 이중 연결 리스트가 나왔다고 생각해도 좋습니다.
이제 자세하게 알아보도록 하겠습니다.

---

01. 단일 연결 리스트(Single Linked List)

---

링크드 리스트는 데이터들을 저장하기 위해 사용되는 자료구조입니다. 배열과 다르게 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조입니다.
그 중 단일 연결 리스트 또는 Single Linked List는 데이트들이 한쪽 방향으로만 연결되어 있습니다.

1) 기본 구조와 용어

• 노드 (Node) : 데이터 저장 단위(데이터값, 포인터) 로 구성 → 하나의 데이터
• 포인터(Pointer) : 각 노드 안에서, 다음 노드의 연결 정보를 가지고 있는 공간
• 헤드(Head) : 리스트에서 가장 앞 부분에 위치한 노드

위 이미지를 보면 한 노드안에는 Data(Value)와 next(다음 노드의 정보)가 포함되어 있습니다.

 

2) 장, 단점

링크드 리스트의 장점은 데이터 공간을 미리 할당하지 않아도 된다는 점입니다.
단점으로는 연결을 위한 별도 데이터 공간이 필요해서 저장공간이 비효율적입니다. 또한 원하는 데이터를 찾기 위해서 리스트의 Head부터 탐색을 시작해야한다는 점도 있습니다. 따라서 접근 속도와 시간이 다소 걸린 다는 단점이 있습니다. 이 외에도 중간에 위치한 노드를 삭제 또는 삽입시 노드간의 연결 정보를 재구성해야한다는 점이 있습니다.

 

3) Single Linked List 구현하기

아래 코드들은 모두 SingleLinkedList<T> 클래스 내부에 작성한 내용입니다.
설명을 위해서 단위별로 나누도록 하겠습니다.

 

---

① SingleLinkedList 내부에 제네릭 타입 Node 클래스 생성

public class SingleLinkedList<T> {
 	
    // 리스트의 head 부분을 null로 미리 지정
    public Node<T> head = null;

    /**
     * 노드 생성
     */
    public class Node<T> {

        T data; // value에 해당
        Node<T> next = null; // 다음 노드의 정보

        public Node(T data) {
            this.data = data;
        }
    }
}

---

② 노드를 추가하는 메서드 구현

    /**
     * 노드 추가
     */
    public void addNode(T data){

		// 리스트 안에 데이터가 없을 때
        if(this.head == null) {
            this.head = new Node<T>(data);
        } else { // 리스트 안에 데이터가 있을 때
            Node<T> node = this.head;

			// 데이터가 없을 때까지 노드들을 순회
            while(node.next != null) {
                node = node.next;
            }

			// next가 null일 때 마지막 노드를 저장하고 해당 노드의 next에 새로운 노드 생성
            node.next = new Node<T>(data);
        }
    }

 

 

---

③ 리스트 안 데이터 전체 출력 메서드 구현

    /**
     * 데이터 전체 출력
     */
    public void printAll() {
    
    	// 리스트 안에 데이터가 있을 경우
        if(head != null) {
            Node<T> node = this.head;
            System.out.print(node.data + " ");

            while(node.next != null) {
                node = node.next;
                System.out.print(node.data + " ");
            }

            System.out.println();
        } else {
            System.out.println("데이터가 없습니다.");
        }
    }

---

④ 노드 검색 및 추가 삽입 메서드

   /**
     * 리스트 중간에 데이터 삽입
     * @Param data : 새로 넣을 데이터
     * @Param isData : 리스트 안에 존재하는 데이터
     */
    public void insertNode(T data, T isData) {
        Node<T> searchedNode = this.search(isData); // 찾는 데이터를 갖는 node

		// 해당 데이터의 노드가 없을 경우
        if(searchedNode == null) {
            this.addNode(data); // 찾는 데이터를 갖는 node가 없으면, 저장할 데이터를 제일 뒤에 저장
        } else {
            Node<T> nextNode = searchedNode.next; // 찾은 노드의 다음 노드를 nextNode에 저장
            searchedNode.next = new Node<T>(data); // 찾은 노드의 다음 노드에 새로운 노드 생성
            searchedNode.next.next = nextNode; // 찾은 노드의 다음 다음에 nextNode 연결
        }

    }
    
    // 해당 데이터를 갖는 노드 검색
    public Node<T> search(T data) {

        if(this.head != null) {
        
            Node<T> node = this.head;
            
            while(node.data != null) {
                if(node.data == data) {
                    return node;
                } else {
                    node = node.next;
                }
            }
            
        }
        return null; // this.head가 null일 경우
    }

---

⑤ 노드 삭제 메서드

   	/**
     * 노드 삭제
     */
    public boolean delNode(T data) {

        if(this.head != null) {
            Node<T> node = this.head;

            if(node.data == data) {
                node = node.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; // 일치하는 data가 없을 시
            }
        }
        return false; // 데이터가 없을 시, 삭제 실패
    }

---

⑤ 실행

    public static void main(String[] args) {
        SingleLinkedList<Integer> myLink = new SingleLinkedList<>();

        myLink.addNode(1);
        myLink.addNode(5);
        myLink.addNode(2);
        myLink.addNode(7);
        myLink.addNode(8);

        myLink.printAll(); // 1, 5, 2, 7, 8

        myLink.insertNode(4,2); // 2를 갖는 노드 뒤에 4를 갖는 노드 추가
        myLink.printAll(); // 1, 5, 2, 4, 7, 8

        myLink.delNode(2); // 2를 갖는 노드 삭제
        myLink.printAll(); // 1, 5, 4, 7, 8
    }

 

---

4) 추가 설명

리스트 중간에 노드를 추가하거나 삭제할 때

① 노드를 추가할 때

→ 기존 리스트가 [3 - 29 - 12 - null] 이라는 데이터를 가졌다고 생각해보겠습니다. 여기서 2의 노드를 29와 12 사이에 추가한다면, 기존에는 29 노드의 next가 12 노드를 가리키고 있습니다. 이제 2의 노드가 추가되니 위 이미지처럼 29의 next는 2를 가리키게 됩니다. 그리고 2가 다음 12를 가리켜야 하기 때문에 2의 next는 12를 가리키게 합니다.
→ 이 내용을 위에서 작성한 코드와 같이 본다면 29가 isData 변수에 해당하고, 2는 Data 변수에 해당합니다.

② 노드를 삭제할 때

→ 이번에는 [3 - 29 - 12- null] 을 갖는 기존 리스트에서 29를 삭제하겠습니다. 그럼 Head의 next를 29가 아닌 12를 가리키게 하면 됩니다.

---

---

02. 이중 연결 리스트(Double Linked List)

---

위에서 알아본 단일 연결 리스트는 노드의 Pointer가 다음 노드의 정보만 갖고 있었습니다.
반면 이중 연결 리스트는 다음 노드의 정보와 이전 노드의 정보 두 가지를 갖고 있게 됩니다.
그림으로 보면 아래와 같습니다.

추가로 이중 연결 리스트에서는 Head 뿐만 아니라, 가장 뒤에 있는 노드로 Tail을 갖게 됩니다.
이 같은 특징들로 Tail에서부터 탐색을 할 수 있게 되는데요. 덕분에 양방향으로 노드 탐색이 가능하게 됩니다.
만약 뒤 쪽에 위치한 데이터를 찾을 때 Tail로 부터 검색한다면,더 빠르게 검색할 수 있겠죠?

 

1) Double Linked List 코드 구현

코드 구현 부분이 길어져서 자세한 코드는 아래 Github 링크를 참고해주세요.

https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/DoubleLinkedList.java

GitHub - Si-Hyeak-KANG/java_algorithm: JAVA를 활용한 코딩 테스트 공부

---

① head와 tail을 추가하고, 각 노드가 이전 노드의 정보도 가질 수 있도록 prev 변수 추가

public class DoubleLinkedList<T> {

    private Node<T> head = null;
    private Node<T> tail = null;

    /**
     * 노드 생성
     */
    public class Node<T> {
        T data;
        Node<T> next = null; // 다음 노드의 정보
        Node<T> prev = null; // 이전 노드의 정보

        public Node(T data) {
            this.data = data;
        }
    }
}

---

2) 단일 연결 리스트보다 조금 더 복잡한 이중 연결 리스트의 추가 삭제

① 노드를 추가할 때

! 만약 새로 넣는 위치가 제일 앞이거나, 뒤일 경우 HEAD와 TAIL로 지정해줘야 합니다.

② 노드를 삭제할 때