Image
Kotlin/Kotlin 자료구조

[Kotlin] Kotlin의 LinkedList 내부 구현 알아보고 사용법 한 번에 정리하기

Kotlin의 LinkedList 알아보기

Kotlin은 Java의 LinkedList를 사용하며 다음의 특징을 가진다.

 

1. 첫 노드와 마지막 노드에 대한 포인터를 가지고 있다.

/**
 * Pointer to first node.
 */
transient Node<E> first;

/**
 * Pointer to last node.
 */
transient Node<E> last;

2. 크기에 대한 정보를 가지고 있어서 크기에 접근하기 위한 시간 복잡도가 O(1)이다.

transient int size = 0;

3. Node는 이전 노드와 다음 노드에 대한 참조를 모두 가진다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

 

즉, Kotlin은 Doubly Linked List를 사용한다.

위의 특징을 가진 Kotlin의 LinkedList는 Doubly Linked List(양방향 연결 리스트)이다.

즉 각 연산에 대해 아래와 같은 시간 복잡도를 가진다.

연산 시간 복잡도
 접근 O(N)
특정 노드 삭제 O(N)
양 끝 노드 삭제 O(1)
특정 위치 노드 삽입 O(N)
양 끝 노드 삽입 O(1)

 

LinkedList 사용하기

자 이제 어떻게 구현되어 있는지 알았으면 한 번 사용해 보도록 하자.

 

LinkedList 생성하기

빈 LinkedList 생성하기

LinkedList를 생성하기 위해서는 LinkedList의 빈 constructor을 사용하면 된다. 그러면 빈 LinkedList가 생성된다.

val linkedList = LinkedList<Int>()

 

원소가 있는  LinkedList 생성하기

만약 초기화 시 원소를 같이 추가하고 싶다면 아래의 constructor을 사용하면 된다.

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

1, 2, 3을 원소로 가지는 LinkedList는 다음과 같이 생성이 가능하다.

val linkedList = LinkedList<Int>(listOf(1,2,3))

 

LinkedList에 원소 추가하기

맨 뒤에 원소 추가하기

LinkedList의 맨 뒤에 원소를 추가하기 위해서는 List 인터페이스의 add 메서드나 LinkedList의 addLast를 사용하면 된다. 맨 뒤 노드에 대한 참조가 있으므로, 시간 복잡도는 O(1)이다.

val linkedList = LinkedList<Int>()

linkedList.add(1)
linkedList.add(2)
linkedList.addLast(3)

println(linkedList) // [1, 2, 3]

 

맨 앞에 원소 추가하기

LinkedList의 맨 앞에 원소를 추가하기 위해서는 addFirst를 사용하면 된다. 맨 앞 노드에 대한 참조가 있으므로, 시간 복잡도는 O(1)이다.

val linkedList = LinkedList<Int>()

linkedList.add(1)
linkedList.add(2)
linkedList.addFirst(3)

println(linkedList) // [3, 1, 2]

 

특정 위치에 원소 삽입하기

특정 위치에 원소를 삽입하고 싶으면 add(index, element)를 사용하면 된다. index 크기가 N이라 했을 때, 특정 위치까지 탐색하는 데 걸리는 시간이 O(N) 이므로, 시간 복잡도는 O(N)이다.

val linkedList = LinkedList<Int>()

linkedList.add(1)
linkedList.add(2)
linkedList.add(1,3)

println(linkedList)

 

LinkedList 원소 삭제하기

맨 앞 원소 삭제하기

맨 앞에 원소를 삭제하고 싶다면 removeFirst를 사용하면 된다. 첫 노드에 대한 참조가 있으므로, 시간 복잡도는 O(1)이다.

val linkedList = LinkedList<Int>()

linkedList.add(1)
linkedList.add(2)
linkedList.add(3)

linkedList.removeFirst()

println(linkedList) // [2, 3]

 

맨 뒤 원소 삭제하기

맨 뒤의 원소를 삭제하고 싶다면 removeLast를 사용하면 된다. 마지막 노드에 대한 참조가 있으므로, 시간 복잡도는 O(1)이다.

val linkedList = LinkedList<Int>()

linkedList.add(1)
linkedList.add(2)
linkedList.add(3)

linkedList.removeLast()

println(linkedList) // [1, 2]

 

특정 위치 원소 삭제하기

특정 위치의 원소를 삭제하고 싶다면 removeAt(index)를 사용하면 된다. index까지 탐색해야 하므로, index 크기가 N이라 했을 때, 시간 복잡도는 O(N)이다.

val linkedList = LinkedList<Int>()

linkedList.add(1)
linkedList.add(2)
linkedList.add(3)

linkedList.removeAt(1)

println(linkedList) // [1, 3]

 

 

LinkedList 원소에 접근하기

LinkedList 원소에 접근하기 위해서는 get(index)를 사용하면 된다.

    val linkedList = LinkedList<Int>()

    linkedList.add(1)
    linkedList.add(2)
    linkedList.add(3)

    println(linkedList.get(0)) // 1
    println(linkedList[1]) // 2
반응형

 

이 글의 저작권은 '조세영의 Kotlin World' 에 있습니다. 글, 이미지 무단 재배포 및 변경을 금지합니다.

 

 

Kotlin, Android, Spring 사용자 오픈 카톡

오셔서 궁금한 점을 질문해보세요!
비밀번호 : kotlin22

open.kakao.com