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

LinkedList란 무엇인가?

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

단일 연결 리스트

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

이 때문에 이전 노드와 다음 노드의 참조를 모두 가지는 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)는 각 노드에서 이전 노드와 다음 노드에 대한 참조를 가지고 있어 각 노드에서 이전 노드와 다음 노드로 모두 이동할 수 있는 리스트이다.

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

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

양방향 연결 리스트의 접근 연산을 위한 시간 복잡도는 여전히 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
}

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

저작자표시 비영리 변경금지

티스토리툴바