[자료구조] 연결 리스트

단일 연결 리스트

 

노드 구성 : 데이터 + link(다음 노드에 대한 연결 고리. 포인터 혹은 레퍼런스)

첫 번 째 노드 : 헤더 header

마지막 노드 : 꼬리 tail. link는 비워두거나 null로 지정함

노드의 link는 다음 노드를 가리키는 포인트나 레퍼런스로만 구성됨. 그래서 앞으로만 종주 가능

리스트를 완정 종주하려면 항상 첫 번째 원소부터 시작해야 한다.

리스트에 있는 모든 원소의 위치를 파악하려면 리스트의 첫 번째 원소에 대한 포인터나 레퍼런스가 있어야 한다.

첫 번재 원소의 포인터나 레퍼런스는 보통 별도의 자료구조에 저장함.

 

 노드. 코틀린으로 작성

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

typealias ListElement<T> = SinglyLinkedListElement<T>

 

헤더에 삽입

//헤더에서 실행
fun <T> ListElement<T>?.insertInFront(data: T) : ListElement<T>
        = ListElement(value = data, next = this)

 

삽입

//헤더에서 실행
fun <T> ListElement<T>?.insert(data: T) : ListElement<T> {
    if (this == null) return this.insertInFront(data)

    var thisNode : ListElement<T> = this
    var nextNode : ListElement<T>? = this.next
    while(nextNode != null) {
        thisNode = nextNode
        nextNode = thisNode.next
    }
    thisNode.next = ListElement(value = data, next = null)
    return this
}

 

전체 리스트 읽기

//헤더에서 실행
fun <T> ListElement<T>?.readAll() {
    var node : ListElement<T>? = this
    println("----- singly linked list read -----")
    while(node != null) {
        println("node data : ${node.value}")
        node = node.next
    }
    println("----- node read done -----")
}

 

검색

//헤더에서 실행
fun <T> ListElement<T>?.search(data: T) : ListElement<T>? {
    var node : ListElement<T>? = this
    while (node != null && node.value != data) {
        node = node.next
    }
    return node
}

 

삭제

헤더 노드를 삭제할 경우, 리스트 전체를 잃어버릴 수 있다는 문제에 봉착. 고민하다가 삭제 작업 결과 값으로 Pair를 쓰기로 함. 삭제 결과 연결 리스트의 헤더 레퍼런스와 삭제 실행 결과 Boolean 값을 넣고 반환하기로 함.

fun <T> ListElement<T>?.deleteListElement(data : T?) : Pair<ListElement<T>?, Boolean> {
    if(this == null || data == null) return this to false

    var preNode : ListElement<T>? = null
    var node = this
    while(node != null && node.value != data) {
        preNode = node
        node = node.next
    }
    if (node == null) return this to false

    if (preNode == null) return node.next to true
    preNode.next = node.next
    return this to true
}

 

테스트

un testSinglyLinkedList() {
    var head : ListElement<Int>? = ListElement(5, null).insertInFront(3).insert(4).readAll()

    println()
    (1..4).forEach {
        println("단일 연결 리스트에 $it 값이 있는지 확인")
        println("결과 : ${head.search(it) != null}")
    }

    println()
    head.deleteListElement(2).let {
        println("2 삭제 시도: ${it.second}")
        it.first.readAll()
        head = it.first
    }

    println()
    head.deleteListElement(3).let {
        println("3 삭제 시도: ${it.second}")
        it.first.readAll()
        head = it.first
    }

    println()
    head.deleteListElement(4).let {
        println("4 삭제 시도: ${it.second}")
        it.first.readAll()
        head = it.first
    }

    println()
    head.deleteListElement(5).let {
        println("5 삭제 시도: ${it.second}")
        it.first.readAll()
        head = it.first
    }

    println()
    head = head.insert(8)
    head.readAll()
}

 

Q. 단일 연결 리스트의 마지막에서 m번째 원소

단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번 째 원소를 찾아내는 알고리즘. "맨 뒤에서 m번 째 원소"는 m = 0일 때 리스트의 마지막 원소를 반환하는 것

시간, 공간 효율을 모두 고려해서, O(n) 알고리즘으로 구현하기 위해서, 리스트를 한 번 종주할 때 현재의 위치와, 현재로부터 m만큼 떨어진 위치를 같이 이동시키면서 리스트의 마지막에 도달해서 값을 구하는 것

fun <T> ListElement<T>?.findMeToLastElement(numOfGap : Int) : ListElement<T>? {

    var current : ListElement<T>? = this ?: return null

    for(index in 0 until numOfGap) {
        if (current?.next != null)
            current = current.next
        else return null
    }

    var behind : ListElement<T>? = this

    while (current?.next != null) {
        current = current.next
        behind = behind?.next
    }

    return behind
}

 

테스트

fun test() {
    val head = ListElement<Int>(value = 1).insert(2).insert(3).insert(4).insert(5)
    println("${head.findMeToLastElement(0)?.value}")
}

 

이중 연결 리스트

 

노드 구성 : link(앞에 있는 노드에 대한 포인터나 레퍼런스) + 데이터 + link(뒤에 오는 노드에 대한 포인터나 레퍼런스)
첫 번 째 노드 : 머리 header. 이전 노드에 대한 link는 비워두거나 null로 지정.

마지막 노드 : 꼬리 tail. 다음 노드에 대한 link는 비워두거나 null로 지정.
리스트 어느 방향이든 종주 가능하다.

어떤 원소에서 시작하든 리스트 전체를 종주하는 것이 가능하다.

노드. 코틀린으로 작성

class DoubleyLinkedListElement<T>(
        val value: T,
        var previous: DoubleyLinkedListElement<T>? = null,
        var next: DoubleyLinkedListElement<T>? = null)

 

원형 연결 리스트

단일 연결 리스트로 된 것도 있고, 이중 연결 리스트로 있는 것도 있다.
머리나 꼬리가 없다.
모든 노드에서 다음 노드를 가리키는 포인터나 레퍼런스에는 반드시 null이 아닌 어떤 원소가 들어간다. 이중 연결 리스트라면 이전 포인터/레퍼런스도 마찬가지이다.
노드가 하나 밖에 없는 리스트라면 그냥 자기 자신을 가리킨다.
종주 시 무한루프가 생기지 않게 주의해야 한다. 시작점을 제대로 파악하지 않으면 리스트를 한없이 돌게 된다.