• 각 요소들을 노드 형태로 저장하며, 각 노드는 다음 노드를 가리키는 포인터를 포함한 구조

특징

• 동적인 크기 : 요소, 노드를 추가, 삭제함에 따라 크기를 변경할 수 있다
• 데이터 추가, 삭제 용이 : 포인터로 각 노드들을 연결하고 있기에, 중간에 추가, 삭제하는 과정이 간단하다
• 비연속적 메모리 할당 : 포인터가 있기 때문에 메모리상에선 연속적인 위치에 있지 않아도 된다

장점과 단점

• 연결 리스트는 포인터가 있기에 데이터를 추가, 삭제할 때 다른 데이터들을 이동할 필요가 없다
• 허나 특정 요소에 접근할 땐 시작점부터 순차적 탐색을 하기에, O(n) 이어서 Array보다는 접근이 빠르지 못하다

예시 코드

class ListNode<T>(var value: T, var next: ListNode<T>? = null)

fun <T> addNode(head: ListNode<T>?, value: T): ListNode<T> {
    if (head == null) return ListNode(value)
    var current = head
    while (current?.next != null) {
        current = current.next
    }
    current?.next = ListNode(value)
    return head
}

fun <T> printList(head: ListNode<T>?) {
    var current = head
    while (current != null) {
        print("${current.value} ")
        current = current.next
    }
    println()
}

var head: ListNode<Int>? = ListNode(1)
head = addNode(head, 2)
head = addNode(head, 3)
printList(head)