배열과 같이 데이터가 연결되어 나열하는 구조 하지만 노드라는 데이터 저장 단위로 연결한다.

노드란?


노드에는 데이터와 다음 노드를 가리키는 공간이 있다.

구현


기본 구조

class LinkedList<T> {
    var size: Int = 0
    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    fun printAll() {
        var node = head
        while (node != null) {
            println(node.item)
            node = node.next
        }
    }

    inner class Node<T> {
        var next: Node<T>? = null
        var item: T? = null
    }
}

addFirst

아이템을 리스트의 맨 앞에 붙인다

fun addFirst(item: T) {
        val newNode = Node<T>().apply {
            this.item = item
            this.next = head
        }
        head = newNode
        if (head?.next == null) {
            tail = head
        }
        size++
    }

addLast

아이템을 리스트의 맨 뒤에 붙인다

fun addLast(item: T) {
        if (size == 0) {
            addFirst(item)
        } else {
            val newNode = Node<T>().apply {
                this.item = item
            }
            tail?.next = newNode
            tail = newNode
            size++
        }
    }

addAt

아이템을 해당 인덱스에 추가해준다.

fun addAt(index: Int, item: T) {
        if (index > size - 1) {
            error("invalid index")
        }

        if (index == 0) {
            addFirst(item)
        } else {
            val newNode = Node<T>().apply {
                this.item = item
            }
            val node = find(index)!!
            val temp = node.next
            newNode.next = temp
            node.next = newNode

            if (newNode.next == null) {
                tail = newNode
            }
            size++
        }
    }

removeFisrt

리스트의 첫번째 노드를 삭제하고 삭제된 노드의 데이터를 리턴해준다.

fun removeFirst(): T {
        val node = head
        head = node?.next!!
        size--
        return node?.item ?: error("invalid item")
    }

find

해당 인덱스의 노드를 리턴해준다.

 fun find(index: Int): Node<T>? {
        var node = head
        for (i in 0 until index) {
            node = node?.next ?: error("invalid node")
        }
        return node
    }

removeAt

해당 Index의 값을 삭제하고 삭제된 노드의 데이터를 리턴해준다.

fun removeAt(index: Int): T {
        if (index > size - 1) {
            error("invalid position")
        }

        return if (index == 0) {
            removeFirst()
        } else {
            val node = find(index - 1)
            val deletedNode = node?.next
            node?.next = node?.next?.next
            size--
            deletedNode?.item ?: error("invalid item")
        }
    }