[Kotlin/자료구조] Linked List에 대하여(2) - Singly Linked List 삭제와 Doubly Linked List

노드 삭제 (in Singly Linked List)

 Singly Linked List내에 있는 노드를 삭제하는 방법은 삽입하는 것과 마찬가지로 3가지 방식으로 가능하다.

 

1️⃣ Head (첫 노드) 삭제하기

 - Head를 두 번째 항목으로 Pointer나 Reference를 옮긴다.

 - 기존 노드 Component를 모두 null로 변경한다.

 C에서는 OS 메모리에 직접 접근하기 때문에 삭제할 노드를 메모리에서 삭제(free) 해줘야하지만, 코틀린(자바)은 JVM에서 알아서 처리해준다.(Java GC)

 하지만 기존 노드를 그대로 유지시킨다면 GC가 콜렉팅하지 않을 수 있기에 기존 항목을 null로 변경해서 GC를 도와주자.

 C에서는 임시 노드를 생성하여 기존 노드를 기억하고 있다가 Pointer를 변경한 후 삭제해줄 수 있겠다.

 

 

2️⃣ Last (마지막 노드) 삭제하기

 - 삭제하고자 하는 항목의 하나 전 노드의 Reference를 NULL로 만든다. (last item도 변경)

 - 삭제하고자 하는 노드의 Component를 모두 null로 변경한다.

 

 

3️⃣ 특정 위치의 노드 삭제하기

 - 삭제하고자 하는 특정 위치 전 노드의 Reference를 다음 노드로 옮기고 특정 위치의 노드를 삭제한다.

 - 삭제하고자 하는 노드의 Component를 모두 null로 변경한다.

 

 

⚠️ 공통적으로 삭제하고자 하는 노드의 전 노드 또는 Head의 Reference를 변경시켜주는 작업이 필요하다.

 

---

리스트 전체 삭제 (in Singly Linked List)

 

 노드 사이의 링크들을 모두 제거하는 것은 불필요할 수 있지만 메모리에서 확실하게 제거하기 위하여(GC를 위하여) 작업을 해준다.

 

 - Linked List를 모두 탐색하여 null로 만들어주는 작업이 필요하다.

class LinkedList<T> {

	//..
	fun clear() {
    	var x: Node<T>? = headNode 
        while (x != null) {
        	val next = x.next
            x.item = null
            x.next = null
            x = next
        }
        
        headNode = null.also { lastNode = it }
        size = 0
    }
}

---

Linked List와 Array, Dynamic Array 비교

Parameter	Linked List	Array	Dynamic Array
Indexing	O(n)	O(1)	O(1)
Insertion/deletion at beginning	O(1)	O(n) - array is not full	O(n)
Insertion at ending	O(n)	O(1) - array is not full	O(1) - array is not full O(n) - array is full
Deletion at ending	O(n)	O(1)	O(n)
Insertion in middle	O(n)	O(n) - array is not full	O(n)
Deletion in middle	O(n)	O(n)	O(n)
Wasted space	O(n)	0	O(n)

출처 : Book - Data structures and algorithms made easy

 

위 표에서 볼 수 있듯이 처음에 항목을 삽입/삭제하는 경우에 LinkedList의 시간 복잡도가 상수로, 빠른 것을 알 수 있다.

 

자신이 구현하고자 하는 데이터의 특성에 맞게 자료구조를 선택, 활용하는 것이 중요하다고 생각한다.

---

Doubly Linked List란?

 - Singly Linked List는 next item에 대한 Pointer만 존재했으나, Doubly Linked List는 prev item에 대한 Pointer도 존재하여 양방향 탐색이 가능한 Linked List이다.

 

 - 양방향 탐색 가능의 특징으로 Singly Linked List에 비해 효율적인 탐색이 가능하다.

   예를 들자면 마지막 전 노드(n-1)를 탐색하기 위해서 Singly Linked List는 Head로부터 n-1번의 탐색이 필요했으나, Doubly Linked List는 마지막 노드에서 1 번의 탐색으로 마지막 노드를 탐색할 수 있다. 즉, 최대 탐색 시간을 절반으로 줄일 수 있다.

 

 - Pointer가 하나 더 생겼기 때문에 해당 메모리 공간이 더 필요하다는 단점이 있긴하다.

 

Singly Linked List vs Doubly Linked List

 - 구조는 기존 Singly Linked List에 prev variable만 추가해주면 된다.

data class Node<T>(
	var item: T?,
	var prev: Node<T>?,
	var next: Node<T>?
)

---

노드 삽입 (in Doubly Linked List)

 Doubly Linked List에서도 처음과 끝, 특정 위치 삽입으로 방법이 나뉘어져있다.

 

1️⃣ Head에 삽입하기

 1) 삽입하고자 하는 노드의 next pointer를 기존 Head 노드로 옮긴다.

 2) 삽입하고자 하는 노드의 prev pointer는 null로 한다.

 3) 기존 Head 노드의 prev pointer를 삽입하고자 하는 노드로 옮긴다.

 4) Head를 삽입하고자 하는 노드로 옮긴다.

 

 

2️⃣ Last에 삽입하기

 1) 삽입하고자 하는 노드의 next pointer를 null로 한다.

 2) 삽입하고자 하는 노드의 prev pointer는 기존 마지막 노드로 한다.

 3) 기존 마지막 노드의 next pointer를 새로운 노드로 옮긴다.

 

 

3️⃣ 특정 위치에 삽입하기

 1) 삽입하고자 하는 노드의 next pointer를 특정 위치의 다음 노드로 한다.

 2) 삽입하고자 하는 노드의 prev pointer를 기존 특정 위치 노드로 한다.

 3) 특정 위치 다음 노드의 prev pointer를 삽입하고자 하는 노드로 옮긴다.

 4) 기존 특정 위치의 next pointer를 삽입하고자 하는 노드로 옮긴다.

 

---

노드 삭제 (in Doubly Linked List)

 삭제의 방법도 처음과 끝, 특정 위치로 나뉘어져있다.

 

1️⃣ Head (첫 노드) 삭제하기

 - Head를 기존 두 번째 노드로 변경한다.

 - 기존 두 번째 노드(첫 번째가 될 노드)의 prev pointer를 null로 변경한다.

 - 삭제할 노드의 Component를 모두 null로 변경한다.

 

 

2️⃣ Last (마지막 노드) 삭제하기

 - 삭제하고자 하는 노드의 이전 노드 next pointer를 null로 만든다.

 - LastNode를 이전 노드로 변경한다.

 - 삭제하고자 하는 노드의 Component를 모두 null로 변경한다.

 

 

3️⃣ 특정 위치의 노드 삭제하기

 - 삭제하고자 하는 특정 위치 이전 노드의 next pointer를 다음 노드로 옮긴다.

 - 삭제하고자 하는 특정 위치 다음 노드의 prev pointer를 특정 위치 이전 노드로 옮긴다.

 - 삭제하고자 하는 노드의 Component를 모두 null로 변경한다.

---

 

[Kotlin/자료구조] Linked List에 대하여(1) - 개요 및 삽입