[자료 구조/알고리즘] 연결 리스트 구현

단일 연결 리스트

더미 노드 미사용

data class Node<T>(
    var data: T,
    var next: Node<T>? = null
)

class SinglyLinkedList<T> {
    var head: Node<T>? = null
    var size: Int = 0

    // 리스트가 비어 있는지 확인
    fun isEmpty(): Boolean = head == null

    // 리스트 맨 앞에 노드 추가
    fun addFirst(data: T) {
        val newNode = Node(data)
        newNode.next = head
        head = newNode
        size++
    }

    // 리스트 맨 뒤에 노드 추가
    fun addLast(data: T) {
        val newNode = Node(data)
        if (isEmpty()) {
            head = newNode
            size++
            return
        }

        var current = head
        while (current?.next != null) {
            current = current.next
        }
        current?.next = newNode
        size++
    }

    // 특정 노드 삭제
    fun remove(node: Node<T>) {
        if (isEmpty()) {
            return
        }

        // 헤드 노드 삭제
        if (node === head) {
            head = head?.next
            size--
            return
        }

        // 중간 또는 마지막 노드 삭제
        var current = head
        while (current?.next != null && current.next !== node) {
            current = current.next
        }

        if (current?.next === node) {
            current.next = node.next
            size--
        }
    }
}

더미 노드 사용

data class Node<T>(
    var data: T? = null,
    var next: Node<T>? = null
)

class SinglyLinkedList<T> {
    // 더미 헤드 노드
    val head: Node<T>

    init {
        head = Node()
    }

    // 리스트 맨 앞에 노드 추가
    fun addFirst(data: T) {
        val newNode = Node(data)

        newNode.next = head.next
        head.next = newNode
    }

    // 리스트 맨 뒤에 노드 추가
    fun addLast(data: T) {
        val newNode = Node(data)

        var current = head
        while (current?.next != null) {
            current = current.next
        }
        current?.next = newNode
        size++
    }

    // 특정 노드 삭제
    fun remove(node: Node<T>) {
        var current = head
        while (current.next != null && current.next !== node) {
            current = current.next!!
        }

        // 삭제할 노드를 찾았을 경우
        if (current.next != null && current.next === node) {
            current.next = node.next
        }
    }
}

이중 연결 리스트

더미 노드 미사용

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

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

    // 리스트가 비어 있는지 확인
    fun isEmpty(): Boolean = size == 0

    // 리스트의 맨 앞에 노드 추가
    fun addFirst(data: T) {
        val newNode = Node(data)
        if (isEmpty()) {
            head = newNode
            tail = newNode
        } else {
            newNode.next = head
            head?.prev = newNode
            head = newNode
        }
        size++
    }

    // 리스트의 맨 뒤에 노드 추가
    fun addLast(data: T) {
        val newNode = Node(data)
        if (isEmpty()) {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            newNode.prev = tail
            tail = newNode
        }
        size++
    }

    // 리스트 중간에 노드 삽입
    fun insertAfter(node: Node<T>, data: T) {
        if (node === tail) {
            addLast(data)
            return
        }

        val newNode = Node(data)
        newNode.prev = node
        newNode.next = node.next
        node.next?.prev = newNode
        node.next = newNode
        
        size++
    }

    // 특정 노드 삭제
    fun remove(node: Node<T>) {
        if (isEmpty()) {
            return
        }

        // 헤드 노드 삭제
        if (node === head) {
            head = node.next
            if (head != null) {
                head!!.prev = null
            }
        // 테일 노드 삭제
        } else if (node === tail) {
            tail = node.prev
            if (tail != null) {
                tail!!.next = null
            }
        // 중간 노드 삭제
        } else {
            node.prev?.next = node.next
            node.next?.prev = node.prev
        }

        size--
    }
}

더미 노드 사용

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

class DoublyLinkedList<T> {
    // 더미 헤드 노드
    var head: Node<T>
    // 더미 테일 노드
    var tail: Node<T>

    init {
        head = Node()
        tail = Node()
        head.next = tail
        tail.prev = head
    }

    // 리스트의 맨 앞에 노드 추가
    fun addFirst(data: T) {
        val newNode = Node(data)
        val firstNode = head.next

        newNode.prev = head
        newNode.next = firstNode

        head.next = newNode
        firstNode?.prev = newNode
    }

    // 리스트의 맨 뒤에 노드 추가
    fun addLast(data: T) {
        val newNode = Node(data)
        val lastNode = tail.prev

        newNode.prev = lastNode
        newNode.next = tail

        tail.prev = newNode
        lastNode?.next = newNode
    }

    // 리스트 중간에 노드 삽입
    fun insertAfter(node: Node<T>, data: T) {
        if (node === tail) {
            return
        }

        val newNode = Node(data)
        val nextNode = node.next

        newNode.prev = node
        newNode.next = nextNode

        nextNode?.prev = newNode
        node.next = newNode
    }

    // 특정 노드 삭제
    fun remove(node: Node<T>) {
        // 더미 노드는 삭제하지 않는다.
        if (node === head || node === tail) {
            return
        }

        node.prev?.next = node.next
        node.next?.prev = node.prev
    }
}

LRU(least recently used) 캐시 구현

data class Node<K, V>(
    var key: K,
    var value: V,
    var prev: Node<T>? = null,
    var next: Node<T>? = null
)

class LRUCache(private val capacity: Int) {
    val cache = HashMap<Int, Node<Int, Int>>()
    var head: Node<Int, Int> = Node()
    var tail: Node<Int, Int> = Node()

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = cache[key]
        if (node != null) {
            // 캐시 히트
            // 가장 최근 사용 노드로 이동
            remove(node)
            addFirst(node)
            return node.value ?: -1
        }
        // 캐시 미스
        return -1
    }

    fun put(key: Int, value: Int) {
        // 캐시가 이미 존재하는 경우 (캐시 값 갱신, 가장 최근 사용 노드로 이동)
        // 가득 차더라도 LRU 제거가 필요하지 않음
        if (cache[key] != null) {
            cache[key]!!.value = value
            remove(cache[key]!!)
            addFirst(cache[key]!!)
        // 캐시가 없는 경우 (캐시 값 추가, 가장 최근 사용 노드로 이동)
        // 가득찬 경우 LRU 제거, 가득 차지 않은 경우 LRU 제거하지 않고 캐시만 처리
        } else {
            // 가득찬 경우 LRU 제거
            if (cache.size >= capacity) {
                if (tail.prev != null) {
                    val lru = tail.prev!!
                    remove(lru)
                    cache.remove(lru.key)
                }

                cache[key] = Node(key, value)
                addFirst(cache[key]!!)
            // 가득 차지 않은 경우 LRU 제거하지 않고 캐시만 처리
            } else {
                cache[key] = Node(key, value)
                addFirst(cache[key]!!)
            }
        }
    }

    private fun addFirst(node: Node<Int, Int>) {
        val newNode = node
        val firstNode = head.next

        newNode.prev = head
        newNode.next = firstNode

        head.next = newNode
        firstNode?.prev = newNode
    }

    private fun addLast(node: Node<Int, Int>) {
        val newNode = node
        val lastNode = tail.prev

        newNode.prev = lastNode
        newNode.next = tail

        tail.prev = newNode
        lastNode?.next = newNode
    }

    private fun remove(node: Node<Int, Int>) {
        val prevNode = node.prev
        val nextNode = node.next
        prevNode?.next = nextNode
        nextNode?.prev = prevNode
    }
}