LinkedList 구현[코틀린 - Kotlin]

실제 LinkedList는 훨씬 더 복잡하게 이루어져있지만.. 링크드 리스트의 원리를 간단히 파악해보기 위하여 삽입, 추가, 삭제 정도의 기능만 간단하게 구현해보았다.

LinkedList란?

연결리스트(LinkedList)란 노드로 구성된 리스트 이다! 
노드에는 데이터와 다음 노드를 가리키는 포인터가 존재한다. 코틀린에서는 포인터가 존재하지 않으므로 객체를 참조하도록 하였다.

 

시간복잡도

• 탐색
  
  • 특정값을 찾기 위해서는 첫 노드(헤드)부터 순차 탐색을 해야하므로 시간복잡도가 O(N)
• 삽입
  • 연결리스트는 노드로 이루어져있기 때문에 삽입을 할 때 시간복잡도가 O(1)
  • 포인터를 사용하여 노드에서 포인터만 변경해주면 되기 때문.
• 삭제
  • 데이터를 삭제하기 위해선 검색과 해당 값을 찾기 위하여 마찬가지로 시간복잡도가 O(N)

연결리스트는 새로운 노드가 추가될 때마다 메모리가 새로 할당되므로 동적 메모리 할당이다.

 

 Array와 LinkedList의 차이

• 탐색
  • Array는 Random Access가 가능하므로 시간복잡도 O(1)
  • LinkedList는 탐색의 시간복잡도 O(N)
• 삽입 / 삭제
  • Array는 삽입, 삭제 작업을 한 후 배열의 크기를 재할당한 후 복사해야 할 수도 있기 때문에
    시간복잡도 O(N)
  • LinkedList는 삽입 삭제의 시간복잡도 O(N)

따라서 탐색이 많이 사용된다면 array를, 삽입 / 삭제가 많이 사용된다면 linkedList를 사용하는 것이 효율적이다.

 

ArrayList와 LinkedList의 차이

• 탐색
  • ArrayList는 index를 사용하여 Random Access가 가능하므로 시간복잡도가 O(1)
  • LinkedList는 탐색의 시간복잡도 O(N)
• 삽입 / 삭제
  • ArrayList는 삽입 / 삭제를 할 후 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성 후 복사함.
    시간복잡도 O(N)
  • LinkedList는 삽입 삭제의 시간복잡도 O(N)

따라서 탐색이 많이 사용된다면 arrayList를, 삽입 / 삭제가 많이 사용된다면 linkedList를 사용하는 것이 효율적이다.

구현

Node 데이터 클래스

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

MyLinkedList 클래스

class MyLinkedList<E>{

    // head는 가장 첫 번째 노트를 뜻함. 없다면 리스트가 비어있다는 뜻.
    private var head: Node<E>? = null

    // 처음으로 삽입.(private)
    private fun addHead(item: E){
        head = Node(item, null)
    }

    // 맨 마지막에 삽입.
    fun add(item: E){
        // 헤드 노드가 비어있으면 처음으로 삽입.
        if(head == null) addHead(item)
        else {
            var curNode = head
            // 마지막 노드까지 탐색 (다음 노드가 null이면 마지막 노드)
            while (curNode?.next != null){
                // 다음 노드로 갱신.
                curNode = curNode?.next
            }
            // 가장 마지막 노드의 다음으로 아이템 추가
            curNode?.next = Node(item,null)
        }
    }

    // 원하는 인덱스에 삽입.
    fun add(index: Int, item: E){
        if (index == 0) {
            if (head == null) addHead(item)
            else {
                val newNode = Node(item,head)
                head = newNode
            }

        }
        var curIndex = 0
        var curNode = head
        var preNode: Node<E>? = null
        while (curIndex < index){
            preNode = curNode
            curNode = curNode?.next
            curIndex++
        }
        // 중간에 추가할 노드
        val newNode = Node(item, null)
        newNode.next = preNode?.next
        preNode?.next = newNode

    }

    // 아이템 삭제.
    fun remove(item: E){
        if(head == null) return println("값이 존재하지 않습니다.")
        else {
            // 만약 첫 번째 노드를 지워야 한다면
            // 새로운 head는 head의 next
            if (head?.data == item){
                head = head?.next
            } else {
                var curNode = head
                // curNode의 다음 노드의 데이터가 item일 때까지 순차 탐색
                // 만약 현재 node의 다음 노드의 next가 null이라면 해당 값이 존재하지 않는다는 뜻.
                while (curNode?.next?.data != item && curNode?.next?.next != null){
                    curNode = curNode.next
                }
                // 삭제할 노드를 건너뛰고(삭제) 연결.
                curNode?.next = curNode?.next?.next
            }
        }
    }

    // 리스트의 모든 값 출력.
    fun printAll(){
        if(head == null) return println("리스트가 비어있습니다.")
        else {
            var curNode = head
            // 현재 노드의 다음 노드가 null이 아닐 때까지
            while (curNode?.next != null){
                println("${curNode?.data}")
                curNode = curNode?.next
            }
            println("${curNode?.data}")
        }
    }
}

메인 함수 및 출력 결과

fun main(){

    val myLinkedList = MyLinkedList<Int>()

    myLinkedList.add(1)// 1 삽입
    myLinkedList.add(2)// 2 삽입
    myLinkedList.add(4)// 4 삽입
    myLinkedList.add(5)// 5 삽입
    myLinkedList.add(0,0) // 0번째 인덱스(맨앞)에 0 삽입
    myLinkedList.add(3,3) // 3번째 인덱스에 3 삽입
    myLinkedList.printAll() // 전체 출력
    myLinkedList.println("---") // --- 출력
    myLinkedList.remove(4) // 4라는 값 제거
    myLinkedList.remove(2) // 2라는 값 제거
    myLinkedList.printAll() // 전체 출력

}

// 출력 결과
0
1
2
3
4
5
---
0
1
3
5