선형 리스트와 연결 리스트의 정의 (Kotlin 으로 연결 리스트 구현)

📌  선형 리스트(ArrayList)

선형 리스트란 배열과 같이 연속되는 기억 장소에 저장되는 리스트를 말한다. 선형 리스트는 논리적인 순서와 기억 장소에 저장되는 물리적 순서가 일치한다.

 

선형 리스트의 장점

• 간단한 자료구조이다.
• 접근 속도가 빠르다.
• 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.

선형 리스트의 단점

• 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
• 즉 삽입과 삭제를 위해서는 자료의 이동이 필요하기 때문에 번거롭다.
• 또한 배열의 크기보다 데이터의 수가 클 경우 데이터를 저장할 수 없는 경우가 생긴다.

 

 

 

 

 

📌  연결 리스트(LinkedList)

연결 리스트는 자료들을 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키면서, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

 

연결 리스트의 장점

• 노드의 삽입, 삭제 작업이 용이하다.
• 기억공간이 연속적으로 놓여 있지 않아도 지정이 가능하다.
• 트리를 표현할 때 적합하다.

연결 리스트의 단점

• 항목 접근이 오래 걸린다. (첫 항목부터 순차적으로 접근하므로 최악의 경우 시간 복잡도 O(n)이 소모된다.
• 물리적으로 인접한 메모리에 위치해 있지 않다. (선형 리스트에 비해 항목들이 물리적으로 인접해있지 않아 접근 시간 단축과 캐싱에 불리하다.)
• 참조 포인터를 위한 메모리 공간이 낭비된다. 

 

 

 

 

 

---

 

 

 

📖  Kotlin 코드로 연결 리스트 구현

LinkedList 클래스는 연결 리스트의 전체적인 로직이 구현된 클래스로 내부 클래스인 Node와 여러 가지 기능 메서드 함수를 포함하고 있다.

LinkedList 클래스

class LinkedList constructor(var videoList: ArrayList<Video>){
    inner class Node{
        var data: Any? = null // 데이터가 저장될 필드
        var next: Node? = null // 다음 노드를 가리키는 필드
    }

    var head: Node? = null
    var tail: Node? = null
    var size: Int = 0

    // 특정 위치의 노드를 찾아내는 함수
    fun find(index: Int): Node? {
        var node = head
        for (i in 0 until index) {
            node = node?.next ?: error("invalid node") // 엘비스 표현법
        }
        return node
    }

    // data 를 받아서 그 위치 index 를 찾아내는 함수
    fun findIndex(data: Any): Int{
        var index = 0
        var node = head
        for (i in 0 until 13){
            if (node?.data == data){
                index = i  // 찾던 id 값을 찾은 경우의 index
                break
            } else {
                node = node?.next
                continue
            }
        }
        return index // index 값 리턴
    }

    fun addFirst(data: Any){
        val newNode = Node().apply {
            this.data = data
            this.next = head // 새로운 노드의 다음 노드로 헤드를 지정
        }
        head = newNode // 헤드로 새로운 노드를 지정
        if(head?.next == null){
            tail = head
        }
        size++
    }

    fun addLast(data: Any){
        if(size == 0){
            addFirst(data) // 리스트에 노드가 없다면 addFirst 메서드 실행
        } else {
            val newNode = Node().apply{
                this.data = data
            }
            tail?.next = newNode // 마지막 노드의 다음 노드로 생성한 노드 지정
            tail = newNode // 마지막 노드 갱신
            size++
        }
    }

    fun addAt(index: Int, data: Any){
        if(index == 0){
            addFirst(data)
        } else {
            val newNode = Node().apply {
                this.data = data
            }
            val node = find(index)!!
            val temp = node.next
            newNode.next = temp // 집어 넣을 새로운 노드의 다음 노드에 temp
            node.next = newNode // 찾은 index 의 다음 노드에 새로운 노드 집어 넣기

            if (newNode.next == null){
                tail = newNode
            }
            size++
        }
    }

    fun removeFirst(): Any {
        val node = head
        head = node?.next
        size--
        return node?.data ?: error("invalid data")
    }

    fun removeAt(index: Int): Any {
        if (index == 0){
            return removeFirst()
        } else {
            val temp = find(index - 1)
            val deletedNode = temp?.next
            temp?.next = temp?.next?.next
            val returnData = deletedNode?.data ?: error("invalid data")
            if(deletedNode == tail){
                tail = temp
            }
            size--
            return returnData
        }
    }
}

 

 

 

 

 

대표로 addFirst, addAt, removeAt에 대해 간략히 설명해 보자면

 

 

addFirst 메서드는 Any 타입의 데이터를 매개변수로 받아와 헤드로 새로운 노드를 지정하고 만약 헤드의 다음 노드가 없다면 즉 링크드 리스트에 아무것도 없다면 헤드와 테일을 같게 만들어 준다.

 

addFirst 메서드

fun addFirst(data: Any){
        val newNode = Node().apply {
            this.data = data
            this.next = head // 새로운 노드의 다음 노드로 헤드를 지정
        }
        head = newNode // 헤드로 새로운 노드를 지정
        if(head?.next == null){
            tail = head
        }
        size++
    }

 

 

 

addAt 메서드는 Any 타입의 데이터와 Int 타입의 인덱스를 매개변수로 받아와 집어넣은 새로운 노드의 다음 노드를 temp로 지정하고 찾은 index의 다음 노드에 새로운 노드를 집어넣는 방식으로 구현한다.

 

addAt 메서드

fun addAt(index: Int, data: Any){
    if(index == 0){
        addFirst(data)
    } else {
        val newNode = Node().apply {
            this.data = data
        }
        val node = find(index)!!
        val temp = node.next
        newNode.next = temp // 집어 넣을 새로운 노드의 다음 노드에 temp
        node.next = newNode // 찾은 index 의 다음 노드에 새로운 노드 집어 넣기

        if (newNode.next == null){
            tail = newNode
        }
        size++
    }
}

 

removeAt 메서드는 만약 노드가 하나밖에 없다면 구현해 놓은 removeFirtst 함수를 실행시키고 그게 아니라면 index - 1 번째 노드를 temp라고 임시 지정하고 난 뒤 삭제할 노드의 앞 노드를 삭제할 노드의 뒤의 노드와 연결시켜 주어 노드가 삭제되더라도 연결 리스트가 유지되도록 한다.

 

removeAt 메서드 

fun removeAt(index: Int): Any {
    if (index == 0){
        return removeFirst()
    } else {
        val temp = find(index - 1) // k-1 번째 노드를 temp 의 값으로 지정한다.
        val deletedNode = temp?.next
        temp?.next = temp?.next?.next // 삭제할 노드의 앞의 노드를 삭제할 노드의 뒤의 노드와 연결시켜 준다.
        val returnData = deletedNode?.data ?: error("invalid data")
        if(deletedNode == tail){
            tail = temp
        }
        size--
        return returnData
    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference:

https://coding-factory.tistory.com/228

https://bluejake.tistory.com/44

https://2dubbing.tistory.com/53

https://supermemi.tistory.com/67