자료 구조 · 알고리즘
[자료 구조/알고리즘] 연결 리스트 구현
2025. 7. 25.
단일 연결 리스트
더미 노드 미사용
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
}
}