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

들어가기 전에 - Why Linked List

다수의 데이터를 쉽고 효과적으로 처리할 수 있는 집합, 그룹 등을 의미하는 Collection이 존재한다.

크게 Collection에는 List와 Set으로 나누어져 있으며(map은..) 이는 순서의 유무에 따라 사용을 결정한다.

 

List를 다루기 위해 가장 쉬운 방법이자 잘 알려져있는 개념은 Array라고 생각한다.

 

"그렇다면 Array만 사용하면 될 것이지 왜 Linked List가 나왔을까?"

 

Array에 대하여 잠깐 생각해보자면 고정된 크기를 갖는다는 특징이 있다.
위 특징으로 단점을 생각해보자면,

크기가 유동적일때 불편하겠구나,

그렇다고 크기를 많이 잡게되면 낭비가 될테고.

특정 위치에 삽입을 하는 것도 자리를 만들기 위해서 다른 요소들을 뒤로 밀어내야하구나. 등등

 

이러한 단점을 보완하기 위한 대안으로 Linked List가 제시되고 있다.

(무조건적인 선택이 아니라 use case에 따라 선택적으로 사용해야 할 것.)

 

---

Linked List란? - Array와 비교하여

메모리 공간에 값이 한 번에 나열되어 있는 Array와 달리,

Linked List는 각 요소 내에 다음 요소를 가리키는 Pointer가 존재하여 연결되는 구조이다.

즉, 메모리 공간에 모여있지 않고 산재되어질 수 있다(non-continuous).

Kotlin에서는 Reference를 통해 서로를 연결한다.

 

다음 코드는 Java에 구현되어 있는 LinkedList의 각 요소인 Node class이다.

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;
        }
}

 

첫 설명에서 각 요소 내에 다음 요소를 가리키는 Pointer가 존재한다고 설명하였는데, next 뿐 아니라 prev 도 존재한다.

Java에서는 이전 요소까지 가리키는 LinkedList를 사용한다는 것이고, 해당 내용은 뒷 부분에서 설명하겠다.

 

다음 요소만 가리키는(일방향) Linked List는 Singly Linked List라고 하며, 일반적으로 Linked List는 이를 의미한다.

 

고정적인 공간을 갖는 Array와 달리, 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다. (단, memory가 허용하는 한)

 

빈 요소가 존재하여 메모리가 낭비되는 Array와 달리, 메모리 공간을 낭비하지 않는다.

하지만 Pointer를 위한 추가의 메모리는 필요로 한다.

 

다음 그림과 같이 Array와 Linked List가 도식화된다.

Array와 Linked List의 도식화

Linked List 도식화 그림으로 설명을 하자면 Linked List의 Head에는 첫 요소의 Reference가 존재할 것이다.

위 그림에서는 Head가 5라는 원소의 Node를 참조하고 있으며, 해당 노드(5)에서는 다음 노드의 Reference를 갖고 있을 것이다.

마지막 Node의 next reference는 null로 처리하여 마지막임을 알린다.

---

Linked List 구조 및 탐색과 삽입

Kotlin(*Java)에는 LinkedList(java.util.LinkedList)가 구현되어 있다.

(Josh Bloch(https://ko.wikipedia.org/wiki/조슈아_블로치) 대가님께서 Java 1.2에 구현해두셨다.)

 

실제로 사용할 때에는 Java의 LinkedList를 import하여 사용하면 되겠지만 이해를 위해 간단한 Linked List를 구현해보고자 한다.

 

구조

노드의 item 과 다음 node 를 포함하는 data class를 선언한다.

data class Node<T>(
        var item: T?,
        var next: Node<T>?,
) // singly linked list

이제부터 LinkedList 클래스에 탐색/삽입/삭제 function들을 채워나가보자.

headNode는 LinkedList 클래스(인스턴스) 내에서 삽입/삭제 될 때마다 관리한다.

class LinkedList<T> {

    private var headNode: Node<T>? = null

}

---

탐색

단번에 Linked List에 특정 값을 찾아내고 싶지만,

해당 값의 참조를 알 수 있는 방법은 Linked List의 Head부터 해당하는 값까지 모두 이동해야 알 수 있다.

 

특정 Position에 있는 Node를 찾는 함수를 구현해보자.

for loop를 통하여 Position까지 이동, 그리고 해당 node를 return한다. 존재하지 않으면 null을 뱉어낼 것이다.

(성능은 고려하지 않는다. 작동하는 방식(?)을 보고자 만든 것이니. Josh Bloch 대가님것을 쓰자.)

 

리스트의 사이즈는 객체 내에서 size라는 variable를 통해 삽입/삭제될 때마다 관리해주고 이를 return해주면 문제 없지만,

관리하지 않는 경우에는 loop를 통해 모든 Node를 거쳐 사이즈를 알 수 있을 것이다.

class LinkedList<T> {

// ...

    fun findItemByPosition(position: Int): Node<T>? {
        var currentNode = headNode

        repaet(position) {
            currentNode = currentNode?.next
        }

        return currentNode
    }

    fun getSizeByCalculating(): Int {
        var currentNode = headNode
        var count = 0

        while (currentNode != null) {
            count++
            currentNode = currentNode.next
        }

        return count
    }
}

---

삽입

삽입은 어디에 넣느냐에 따라 방식이 달라진다. 총 3가지. 처음과 끝, 그리고 특정 위치에 삽입하는 경우가 있다.

 

1. 마지막(last)에 삽입

처음에 삽입하는 방법부터 설명하는 것이 일반적이나 인스턴스 내의 lastNode를 설명을 위하여 마지막 삽입부터 설명하겠다.

 

size는 [탐색]에서 설명한 것처럼 삽입/삭제마다 관리를 위해 사용한다.

 

(0) 마지막에 삽입하기 위해서는 head부터 마지막까지 탐색 과정을 모두 거쳐야한다.

      하지만, lastNode를 선언(≈헤드노드 개념)하여 관리해준다면 탐색 과정을 생략해줄 수 있다.

 

(1) 새로운 노드는 마지막 노드일테니(마지막에 삽입하기 때문) next node는 null로 선언한다.

 

(2) 기존의 lastNode의 next를 새로운 노드로 변경한다.

 

(3) lastNode를 새로운 노드로 변경한다.

 

(4) 빈 LinkedList에서 마지막에 추가하는 function을 호출했다면, 새로운 노드는 헤드 노드이자 마지막 노드일 것이다.

     하지만 이를 처리를 해주지않는다면 헤드 노드는 그대로 null로 남아 제대로 작동하지 않을 것이다.  

    (size를 확인하여 처음에 삽입하는 함수를 호출하는 것도 방법이겠다.)

class LinkedList<T> {

	private var size = 0
	private var lastNode: Node<T>? = null // (0)

// ...

	fun linkNodeAtLast(item: T) {
		val newNode = Node(item, null) // (1)
		lastNode?.next = newNode // (2)
		lastNode = newNode // (3)
		size++
        
		if (headNode == null) { // (4)
			headNode = newNode
		}
	}
}

 

---

2. 처음(head)에 삽입

 

1. 새로운 노드의 next를 기존 head node로 생성

2. headNode를 새로운 노드로 변경

3. 빈 LinkedList에 추가하는 경우 처리

class LinkedList<T> {

// ...

	fun linkNodeAtHead(item: T) {
            val newNode = Node(item, headNode) // 1
            headNode = newNode // 2
            size++

            if (lastNode == null) { // 3
                lastNode = headNode
            }
	}
}

 

---

3. 특정 위치에 삽입

 

1. 새로운 노드의 next를 삽입하고자 하는 위치의 다음 노드로 생성

2. 삽입하고자 하는 위치의 이전 노드의 next를 새로운 노드로 변경

 

* 이를 위해서는 previous node와 next node를 모두 알아야 가능하다.

   예를 들어 index 3에 삽입하고자 한다면 삽입 전 리스트의 index 2와 3의 node를 알아야한다.
* 처음과 마지막에 삽입하는 경우는 이전 함수를 호출하고 position이 size를 초과하는 경우 에러를 발생시키도록 작성했다.

* 효율을 고려하지 않는다. position이 0이 아닐 경우 findItem()을 한 번만 호출할 수 있도록 짤 수 있었다. 등등

class LinkedList<T> {

// ...
	fun linkNodeAtPosition(item: T, position: Int) {
    
            if (position > size) { throw error("out of index") }

            var prevNode: Node<T>? = null

            if (position != 0) {
                prevNode = findItem(position - 1)
            }
            val nextNode: Node<T>? = findItem(position)

            when {
                prevNode == null -> {
                    linkNodeAtHead(item)
                }
                nextNode == null -> {
                    linkNodeAtLast(item)
                }
                else -> {
                    val newNode = Node(item, nextNode)
                    prevNode.next = newNode
                    size++
                }
            }
   }

	fun findItem(position: Int): Node<T>? {
              var currentNode = headNode

              repeat(position) {
                  currentNode = currentNode?.next
              }

              return currentNode
	 }
}

 

---

다음 포스팅에선 Singly Linked List의 삭제와 Doubly Linked List의 개념/삽입/삭제에 대하여 알아보겠다.

 

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