[자료구조] 연결리스트(Linked List)란?

연결리스트란?

• 연결리스트는 데이터를 순차적으로 저장하는 단방향 선형구조이다.
• 각 요소는 노드로 구성되어 있으며, 각 노드는 자신의 데이터와 다음 노드를 가리키는 포인터(혹은 링크)로 이루어져 있다.

연결리스트의 특징

• 각 노드는 포인터(혹은 링크)를 갖고 있어 데이터가 일렬로 연결되는데, 한 방향으로만 탐색이 가능하다.
• 연결리스트의 시작을 알리는 헤드가 있는데, 이 헤드 노드는 첫 번째 노드를 가리키는 역할을 한다.
• 동적으로 크기를 조절할 수 있어 삽입과 삭제가 배열보다 간단하고 메모리 효율도 좋다.
• 특정 요소에 접근하기 위해서는 헤드부터 순차적으로 탐색해야 한다.
• 연결리스트의 연산으로는 노드 추가, 노드 삭제, 탐색이 있다.

연결리스트의 시간복잡도

노드 추가

노드 추가에는 크게 head에 추가, 마지막에 추가, 특정 위치에 추가로 나뉜다.

1. head에 추가

• 맨 처음에 연결리스트에는 데이터가 없거나, Head 바로 앞에 노드를 추가한다.
• 따라서 시간복잡도는 O(1)이다.

2. 마지막에 추가

• 연결리스트의 마지막에 노드를 추가한다.
• 연결리스트를 순회하며 마지막을 찾고, 마지막 노드가 가리키는 null 대신 새로운 노드에 추가한다.
• 따라서 시간복잡도는 O(n)이다.

 

3. 특정 위치에 추가

• 연결리스트의 특정 위치에 노드를 추가한다.
• 연결리스트에서 특정 위치까지 순회를 한 후, 해당 위치에 노드를 추가한 뒤에 link를 변경한다.
• 따라서 시간복잡도는 O(n)이다.

노드삭제

노드 삭제는 크게 마지막 노드 삭제, 특정 위치의 노드 삭제로 나뉜다.

1. 마지막 노드 삭제

• 연결리스트의 마지막 노드를 삭제한다.
• 연결리스트를 순회하며 마지막 노드를 찾고, 그 노드를 삭제한다.
• 따라서 시간복잡도는 O(n)이다.

2. 특정 데이터 노드 삭제

• 연결리스트를 순회하며 특정 데이터를 찾아 삭제한다.
• 따라서 시간복잡도는 O(n)이다.

탐색

• 연결리스트를 순회하며 특정 데이터를 찾는다.
• 따라서 시간복잡도는 O(n)이다.

연결리스트의 장단점

1. 장점
   • 배열에 비해 삽입 삭제가 용이하다.
   • 크기를 동적으로 조절할 수 있어 메모리를 유연하게 가져갈 수 있다.
2. 단점
   • 다음 변수를 가리키는 포인터(링크)가 추가로 있어 배열에 비해 추가적인 메모리를 차지한다.
   • 특정 요소를 접근하기 위해서는 무조건 Head부터 순회해야해서 탐색 시간이 증가한다.

예제

class Node(data: Int?, next: Node?) {
    var data: Int?
    var next: Node?

    init {
        this.data = data
        this.next = next
    }
}

class LinkedList {
    private var head: Node
    private var count: Int

    init {
        head = Node(null, null)
        count = 0
    }

    fun addFirst(data: Int) {
        if(null == head.next)
            head.next = Node(data, null)
        else {
            var newNode = Node(data, head.next)
            head.next = newNode
        }

        count++
    }

    fun addMiddle(data: Int, index: Int) {
        if(null == head.next)
            return

        var middle = head.next!!
        for(i in 1 until index){
            if(null == middle.next) {
                middle.next = Node(data, null)
                return
            }

            middle = middle.next!!
        }

        var newNode = Node(data, middle.next)
        middle.next = newNode

        count++
    }

    fun addLast(data: Int) {
        if(null == head.next)
            return

        var last = head.next
        while (last?.next != null)
            last = last.next

        last?.next = Node(data, null)
        count++
    }

    fun search(data: Int): Boolean {
        if(null == head.next)
            return false

        var node = head.next
        while(true) {
            if(null == node?.next)
                return false

            if(node.data == data){
                return true
            }

            node = node.next
        }
    }

    fun removeFirst() {
        if(null == head.next)
            return

        if(count == 1)
            head.next = null
        else {
            var node = head.next
            head.next = node?.next
        }

        count--
    }

    fun removeMiddle(data: Int) {
        if(null == head.next)
            return

        if(count == 1){
            removeFirst()
            return
        }

        var node = head.next
        while(node?.next?.data != data) {
            node = node?.next
        }

        if(null == node.next) {
            removeLast()
            return
        }

        var temp = node.next?.next
        node.next = temp

        count--
    }

    fun removeLast() {
        if(null == head.next)
            return

        if(count == 1){
            removeFirst()
            return
        }

        var node = head.next
        while(null != node?.next?.next)
            node = node.next

        node?.next = null
        count--
    }

    fun print() {
        if(null == head.next){
            println("LinkedList가 비어있음")
            return
        }

        var data = head.next
        print("head -> ")
        while (null != data?.next) {
            print("${data.data} -> ")
            data = data.next
        }

        println(data?.data)
    }

    fun count(): Int = count
    fun isEmpty(): Boolean = count == 0
}

fun main() {
    val linkedList = LinkedList()
    linkedList.addFirst(1)
    linkedList.addFirst(2)
    linkedList.addLast(3)

    linkedList.print()
    println(linkedList.search(2))

    linkedList.addMiddle(4, 2)
    linkedList.print()

    linkedList.removeFirst()
    linkedList.removeLast()
    linkedList.print()

    linkedList.addFirst(2)
    linkedList.removeMiddle(1)
    linkedList.print()
}

사실 이렇게 해도 kotlin은 java의 LinkedList를 사용할 수 있어 그걸 사용하는게 좋다..