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
