[자료구조] 리스트(2).연결리스트(LinkedList)

연결리스트(LinkedList)

 

순차리스트가 배열로 구성된 리스트라면, 연결리스트는 노드로 구성된 리스트이다.

노드는 두 가지의 정보를 가지고 있다.

• 데이터
• 다음 노드를 가리키는 포인터

즉, 다음과 같은 형태를 갖게 된다.

이때 pointer는 다음 노드의 주소를 값으로 갖고 있게 된다.

 

코틀린에서의 LinkedList를 열어 Node를 보면 다음과 같다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

위에서 Node는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다 했지만, 코틀린 및 자바에는 포인터라는 개념이 없다. 따라서 Node 객체를 참조하게 된다.

또한 다음 노드뿐만 아니라 이전 노드 또한 갖고 있는 것을 확인할 수 있다.

이는 양방향으로 연결된 Doubly LinkedList인데, 여기서는 다음 노드만을 아는 일방향인 Singly LinkedList를 알아보도록 한다.

따라서 Singly LinkedList를 구현해보도록 한다.

구현

우선 Node를 data class로 item과 다음 노드를 참조하는 데이터를 선언한다.

data class Node<T>(
    var item: T?,
    var next: Node<T>?
)

삽입

class LinkedListExample<T> {
    private var head: Node<T>? = null

    fun add(item: T) {
        val newNode = Node(item, null)

        if(head == null) head = newNode
        else {
            var curNode = head

            while(curNode?.next != null) {
                curNode = curNode.next
            }

            curNode?.next = newNode
        }
    }

    fun add(index: Int, item: T) {
        if(index == 0) {
            head = if(head == null) Node(item, null) else Node(item, head)
        }

        var curIdx = 0
        var curNode = head
        var preNode: Node<T>? = null

        while(curIdx < index) {
            preNode = curNode
            curNode = curNode?.next
            curIdx++
        }

        val newNode = Node(item, null)
        newNode.next = preNode?.next
        preNode?.next = newNode
    }
}

인덱스를 따로 지정해주지 않은 add 함수를 보자.

새로운 Node를 추가해주는 것이므로 새로운 노드를 선언해준다.

이때 다음 노드는 없으므로 Node(item, null)로 선언이 된다.

 

만약 head가 null이라면 리스트가 비어있는 것이므로 head = newNode가 되며,

null이 아니라면 마지막 노드까지 반복문을 통해 올라간 후 그 다음 노드를 newNode로 해주게 된다.

다음으로는 파라미터로 인덱스까지 받는 add 함수이다.

추가하고자하는 인덱스가 0이면서, head가 null이라면 리스트가 비어있는 것이므로 기존 add에서와 같이 head = Node(item, null)을 해주면 된다.

head가 null이 아닐 시, head = Node(item, head)를 해줌으로써 추가하고자 하는 노드의 뒤에 현재까지의 정보를 가지고 있는 head를 next로 주면 된다.

이해를 돕기 이해 출력을 보자.

head가 이렇게 있을 때, 0의 인덱스에 값을 추가하고자 한다면, Node(item, head)를 통해 맨 앞에 값을 추가할 수 있게 되는 것이다.

 

추가하고자 하는 인덱스가 0이 아닌 다른 값이라면 반복문을 통해 그 위치만큼 인덱스를 옮겨준 후, 노드를 추가해준다.

삭제

class LinkedListExample<T> {
    // ...
    
    fun remove(item: T) {
        if(head == null) return println("Empty List")
        else {
            if(head?.item == item) head = head?.next
            else {
                var curNode = head

                while(curNode?.next?.item != item && curNode?.next?.next != null) {
                    curNode = curNode.next
                }

                curNode?.next = curNode?.next?.next
            }
        }
    }
}

head가 null이라면 리스트가 비어있는 것이므로 Empty List를 표시해준다.

head의 item이 지우고자 하는 값이라면 현재 헤드에 다음 노드를 할당해준다.

이를 통해 현재 노드가 다음 노드로 덮어씌워지며 지우고자 하는 값이 제거된다.

 

그 외에 다음 반복문인 while을 확인해보면, curNode의 다음 노드의 아이템이 지우고자 하는 값일 때까지 반복하고, 그 다음 노드가 null이 아닐 때까지 반복을 한다.

반복이 끝났다면 curNode의 다음 노드가 지우고자 하는 노드일 것이므로, curNode의 다다음 노드를 curNode의 다음에 덮어주면 값이 지워지게된다.