연결리스트(Linked List)정의 및 구현 feat.kotlin

연결 리스트, 링크드 리스트(linked list)

 

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다.

그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

 

단 방향 연결리스트

 

 Head 노드 (첫번째 데이터 노드)를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다. 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 체인이 끊어진 양 거기부터 뒤쪽 자료들을 유실한다. 따라서 안정적인 자료구조는 아니다.
파일 시스템 중 FAT 파일 시스템이 이 단순 연결 리스트로 파일 청크를 연결하는데 그래서 FAT 파일 시스템은 파일 내용 일부가 손상될 경우 파일의 상당 부분을 유실할 수 있고 랜덤 액세스 성능도 낮다.

단순히 Head의 참조만 변경해 주면 되기 때문에 상수시간의 시간 복잡도를 지닌다.

pushFront() - O(1) 

popFront()  - O(1) 

 

연결의 가장 마지막에 새로운 노드를 추가해주거나 링크를 끊어야 하기 때문에 마지막 노드까지 접근하는데 걸리는 시간이 O(n) 

pushBack() - O(n) 

popBack() - O(n) 

 

최악의 경우 모든 노드를 탐색 해야되기 때문에 노드 개수가 n개라면 O(n)

search() - O(n)

 

code

class SinglyLinkedList: Iterable<Int> {
    private data class Node(val key: Int, var next: Node? = null)

    private var head: Node? = null

    private var _size = 0
    val size
        get() = _size
    
    fun pushFront(key: Int) {
        val newNode = Node(key)
        newNode.next = head
        head = newNode
        _size += 1
    }

    fun pushBack(key: Int) {
        val newNode = Node(key)
        if (_size == 0) {
            head = newNode
        } else {
            var tail = head
            while (tail?.next != null) {
                tail = tail.next
            }
            tail?.next = newNode
        }
        _size += 1
    }

    fun popFront(): Int? =
        if (_size == 0) {
            null
        } else {
            val temp = head!!
            val key = temp.key

            head = temp.next
            temp.next = null
            _size -= 1
            key
        }


    fun popBack(): Int? =
        if (_size == 0) {
            null
        } else if (_size == 1) {
            val key = head?.key
            head = null
            _size -= 1
            key
        } else {
            var prev: Node? = null
            var tail = head

            while (tail?.next != null) {
                prev = tail
                tail = tail.next
            }
            val key = tail?.key
            prev?.next = null
            _size -= 1
            key
        }

    fun search(key: Int): Int? {
        var node = head
        while (node != null) {
            if (key == node.key) break
            node = node.next
        }

        return node?.key
    }

    private class SinglyLinkedListIterator(val list: SinglyLinkedList) : Iterator<Int> {

        var index = 0
        var lastNode = list.head
        override fun hasNext(): Boolean {
           return index < list.size
        }

        override fun next(): Int {
           if (lastNode == null) throw IndexOutOfBoundsException()
            val key = lastNode!!.key
            lastNode = lastNode!!.next
            index++
            return key
        }
    }
    override fun iterator(): Iterator<Int> {
        return SinglyLinkedListIterator(this)
    }

    override fun toString(): String {
        val sb = StringBuilder()
        var node = head
        while (node != null) {
            sb.append("${node.key} ")
            node = node.next
        }
        return sb.toString()
    }
}

 

이중 연결 리스트

다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키게 하면 이중 연결 리스트가 된다. 뒤로 탐색하는 게 가능하다는 단순한 장점 이외에도 한 가지 장점이 더 있는데, 단순 연결 리스트는 현재 가리키고 있는 노드를 삭제하는 게 한 번에 안 되고 O(n)이 될 수밖에 없는데 비해 이중 연결 리스트에서 현재 노드를 삭제하는 것은 훨씬 간단하다. 대신 관리해야 할 참조가 두 개나 있기 때문에 삽입이나 정렬의 경우 작업량이 더 많고 자료구조의 크기가 약간 더 커진다.