LinkedList란 무엇인가? 단일 연결 리스트, 양방향 연결 리스트 간단하게 구현해보기

LinkedList란 무엇인가?

LinkedList는 각 노드에서 단방향으로 포인터를 가진 단일 연결 리스트(Singly Linked List)와 양방향으로 포인터를 가진 양방향 연결 리스트(Doubly Linked List)로 나뉜다.

 

단일 연결 리스트

 단일 연결 리스트(Singly Linked List)는 각 노드에서 다음 노드에 대한 참조를 가지고 있어 다음 노드로 이동할 수는 있지만 이전 노드로 이동할 수는 없는 리스트이다.

 

그림1. 단일 연결 리스트

 

이 때문에 이전 노드와 다음 노드의 참조를 모두 가지는 Double Linked List에 비해 메모리 공간을 약간 덜 차지하는 장점이 있으며, 특정 노드 삭제를 위해 삭제할 노드의 이전 노드의 포인터를 다음 노드로 변경하면 되기 때문에 삭제가 매우 간단하다.

 

 하지만 여러 단점이 있다. 이 중 주요한 단점은 뒤의 노드에서 앞의 노드로의 접근이 불가능하다는 문제이며, 특정 노드를 찾기 위해 O(N)의 시간 복잡도가 필요하다는 점이다.

 

 

단일 연결 리스트의 시간 복잡도

• 단방향 연결 리스트의 접근 연산을 위한 시간 복잡도는 O(N)이다. 모든 원소들을 순회하면서 찾아야 하기 때문이다.
• 삭제 연산 또한 삭제할 노드를 찾아야 하므로 O(N)이다.
• 특정 위치 삽입 연산의 경우 삽입할 위치까지 이동해야 하므로 O(N)이다.
• 삽입 연산의 경우 맨 뒤의 노드에 대한 참조가 있는 경우 해당 노드의 다음 노드의 참조로 추가하면 되므로 O(1)이다. 하지만 맨 앞의 노드에 대한 참조만 있는 경우 맨 뒤의 노드까지 이동해야 하기 때문에 O(N)이 된다.

연산	시간 복잡도
접근	O(N)
삭제	O(N)
특정 위치 삽입	O(N)
맨 뒤에 삽입	맨 뒤의 노드에 대한 참조가 있는 경우 : O(1) 맨 뒤의 노드에 대한 참조가 없는 경우 : O(N)

 

양방향 연결 리스트

 단일 연결 리스트에서 다음 노드에서 이전 노드로의 접근이 불가능한 문제를 해결하기 위해 만들어진 것이 바로 양방향 연결 리스트(Doubly Linked List)이다. 양방향 연결 리스트(Doubly Linked List)는 각 노드에서 이전 노드와 다음 노드에 대한 참조를 가지고 있어 각 노드에서 이전 노드와 다음 노드로 모두 이동할 수 있는 리스트이다.

그림2. 양방향 연결 리스트

이 때문에 원소를 찾을 때 단일 연결 노드의 평균적으로 반 정도의 시간이 들어가며 단일 연결 리스트에 비해 삭제 연산이 약간 복잡하다. 

 

양방향 연결 리스트의 시간 복잡도

• 양방향 연결 리스트의 접근 연산을 위한 시간 복잡도는 여전히 O(N)이다. 단방향에 비해 시간이 반정도 걸리는 것으로 개선되지만 여전히 느리다.
• 삭제 연산 또한 삭제할 노드를 찾아야 하므로 O(N)이다.
• 특정 위치에 노드를 삽입하기 위해서는 해당 위치로 이동해야 하므로 O(N)이 걸린다.
• 맨 뒤의 노드에 삽입하기 위해서는 맨 뒤의 노드에 대한 참조가 있는 경우, 해당 노드의 다음 노드의 참조로 추가하고 추가할 노드에 맨 뒤의 노드를 이전 노드로 참조 추가하면 되므로 O(1)이다. 하지만 맨 앞의 노드에 대한 참조만 있는 경우 결국 맨 뒤의 노드까지 이동해야 하기 때문에 O(N)이 된다.

연산	시간 복잡도
접근	O(N)
삭제	O(N)
특정 위치 노드 삽입	O(N)
맨 뒤의 노드 삽입	맨 뒤의 노드에 대한 참조가 있는 경우 : O(1) 맨 뒤의 노드에 대한 참조가 없는 경우 : O(N)

 

 

연결 리스트 구현

단일 연결 리스트 간단하게 구현해 보기

내부 연산 없이 단일 연결 리스트를 만드는 것은 매우 간단하다. 값과 다음 Node에 대한 참조를 가진 Node 클래스를 만들어보자.

class Node<T>(val value: T, var next: Node<T>? = null)

맨 앞 Node(head) 노드에 대한 참조만을 가지도록 만들면 아주 간단한 SinglyLinkedList가 완성된다. 맨 뒤(tail) 노드에 대한 참조를 추가로 가지게 할 수도 있다.

class SinglyLinkedList<T> {
    var head: Node<T>? = null
}

이에 대한 노드 추가 연산은 아래와 같이 구현할 수 있다. 현재 노드에 대한 참조를 유지하고, 현재 다음 노드가 없을 때 현재 노드의 다음 노드를 새로운 노드로 만들면 된다.

class SinglyLinkedList<T> {
    private var head: Node<T>? = null
    
    fun add(value: T) {
        val addNode = Node(value)
        if (head == null) {
            head = addNode
        } else {
            var current = head
            while (current?.next != null) {
                current = current.next
            }
            current?.next = addNode
        }
    }
}

특정 노드 삭제 연산은 아래와 같이 구현할 수 있다. 삭제 연산을 구현할 때 주의할 점은 head가 삭제할 값인 경우를 따로 구현해주어야 한다는 점이다. 만약 삭제할 노드가 head 가 아니라면 이전 노드(prev)에 대한 참조를 유지하고 삭제할 값이 나왔을 때 이전 노드의 포인터(next)를 다음 노드로 옮겨 주어야 한다.

class SinglyLinkedList<T> {
    private var head: Node<T>? = null
    
    fun remove(value: T) {
        // Check head is same to value
        if (head == null) return
        if (head.value == value) {
            head = head.next
            return
        }
        
        // If head is not same to value
        var current = head
        var prev: Node<T>? = null
        while (current != null) {
            if (current.value == value) {
                prev?.next = current.next
                return
            }
            prev = current
            current = current.next
        }
    }
}

 

양방향 연결 리스트 간단하게 구현해 보기

양방향 연결 리스트를 구현하기 위해서는 노드에 다음 노드에 대한 참조를 만들어야 한다.

 Node<T>(val value: T, var prev: Node<T>? = null, var next: Node<T>? = null)

맨 앞 노드에 대한 참조를 만들어주면 양방향 연결 리스트에 대한 구현이 완성된다. 맨 뒤(tail) 노드에 대한 참조를 가지게 할 수도 있다.

class DoublyLinkedList<T> {
    var head: Node<T>? = null
}

추가 연산, 삭제 연산 등은 생략한다.