배열과 같이 데이터가 연결되어 나열하는 구조 하지만 노드라는 데이터 저장 단위로 연결한다.
노드에는 데이터와 다음 노드를 가리키는 공간이 있다.

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
}
}
아이템을 리스트의 맨 앞에 붙인다
fun addFirst(item: T) {
val newNode = Node<T>().apply {
this.item = item
this.next = head
}
head = newNode
if (head?.next == null) {
tail = head
}
size++
}
아이템을 리스트의 맨 뒤에 붙인다
fun addLast(item: T) {
if (size == 0) {
addFirst(item)
} else {
val newNode = Node<T>().apply {
this.item = item
}
tail?.next = newNode
tail = newNode
size++
}
}
아이템을 해당 인덱스에 추가해준다.
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++
}
}
리스트의 첫번째 노드를 삭제하고 삭제된 노드의 데이터를 리턴해준다.
fun removeFirst(): T {
val node = head
head = node?.next!!
size--
return node?.item ?: error("invalid item")
}
해당 인덱스의 노드를 리턴해준다.
fun find(index: Int): Node<T>? {
var node = head
for (i in 0 until index) {
node = node?.next ?: error("invalid node")
}
return node
}
해당 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")
}
}