[자료구조 with 코틀린] 1. LinkedList

1. 개념

하나의 노드에 데이터와 포인터가 있으며, 이를 연결하는 방식으로 데이터를 저장하는 선형 자료구조입니다.

2. 시간복잡도

1) 검색

논리적 저장 순서와 물리적 저장 순서가 다르기 때문에, 첫 노드부터 순회해서 탐색해야 합니다. 따라서 검색 시 O(N)의 시간복잡도를 가집니다.

2) 삽입 및 삭제

배열처럼 연속적으로 데이터가 저장된 것이 아니라 포인터를 사용했기에, 삽입과 삭제에 O(1)의 시간복잡도를 가집니다.

그러나 특정 데이터를 삭제하려는 경우, 이 데이터를 찾는 데 O(N)의 비용이 발생합니다.

3) 메모리 할당

새로운 노드가 추가될 때마다 추가로 할당됩니다. 즉, 런타임에 할당되며, 동적 메모리 할당이라고도 합니다.

3. 구현

class LinkedList<E> {

    private var head : Node<E>? = null
    // 데이터와 다음 노드의 위치를 갖는 노드 클래스
    inner class Node<E>(
        var data: E,
        var next: Node<E>? = null
    )

    fun addFirst(item: E) {
        head = Node(item, null)
    }
    // 마지막에 삽입
    fun add(item: E) {
        if (head == null) {
            addFirst(item)
        }
        else {
            var node = head
            // 현재 노드의 다음 노드가 null 이 아닐 때까지(즉, 마지막 노드까지 탐색)
            while (node?.next != null) {
                node = node?.next
            }
            // 가장 마지막 노드의 다음 노드로 아이템 추가
            node?.next = Node(item, null)
        }
    }
    // 중간에 삽입
    fun add(preNode: Node<E>?, item: E) {
    	if (preNode == null) {
        	return println("이전 노드가 null이면 안 됩니다.")
        }
        val newNode = Node(item, null)
        newNode.next = preNode.next
        preNode.next = newNode
    }
	// 삭제
    fun delete(item: E) {
        if (head == null) return println("값이 존재하지 않습니다.")
        else {
            // 만약 지우려는 데이터가 head 의 데이터라면, head 의 next 는 next 의 next 값이 되도록 한다.
            if (head?.data == item) {
                head = head?.next
            } else {
                var node = head
                // node 의 다음 노드의 데이터가 item 이 아니라면 계속 반복해서 찾는다.
                // 또한 현재 node 의 next 의 data 가 null 이라면 더 이상 다음 노드는 없는 것이므로, 탐색을 종료하도록 한다.
                while (node?.next?.data != item && node?.next?.data != null) {
                    node = node?.next
                }
                // 찾았다면 해당 node 의 next 는 next 의 next 가 된다.(없다면 null)
                node?.next = node?.next?.next
            }
        }
    }
    // 전부 출력
    fun desc() {
        if (head == null) return println("값이 존재하지 않습니다.")
        else {
            var node = head
            while (node?.next != null) {
                println("${node?.data}")
                node = node?.next
            }
            println("${node?.data}")
            println()
        }
    }

4. 다른 자료구조와 비교

1) Array 와 LinkedList

a. 탐색

Array의 경우 Random Access 가 가능하므로 탐색의 시간복잡도는 O(1)입니다.

반면 LinkedList의 경우 탐색의 시간복잡도는 O(N)이므로, 탐색이 빈번하다면 Array를 사용하는 것이 더 효율적입니다.

b. 삽입 / 삭제

Array의 경우 삽입 및 삭제를 한다면 해당 작업을 완료한 뒤 배열 크기를 재할당한 후 복사해야 할 수 있으므로 최악의 경우 O(N)의 시간복잡도를 가집니다.

반면 LinkedList의 경우 삽입 및 삭제 자체는 O(1)의 시간복잡도를 가지므로, 삽입 및 삭제가 빈번하다면 LinkedList 를 사용하는 것이 효율적입니다.

2) ArrayList 와 LinkedList

a. 탐색

ArrayList는 index를 통해 Random Access가 가능하므로 탐색의 시간복잡도가 O(1)입니다.

따라서 검색이 빈번한 경우 ArrayList를 사용하는 것이 더 효율적입니다.

b. 삽입, 삭제

ArrayList의 경우 삽입 및 삭제를 한 후 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성해 복사합니다. 따라서 시간복잡도가 O(N)이 소요됩니다.

따라서 삽입 및 삭제의 경우 LinkedList를 사용하는 것이 더 효율적입니다.