[자료구조] LinkedList

LinkedList란?

연결리스트(LinkedList)는 노드가 데이터와 포인터를 가지고 한 줄로 연결 되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

이름 그대로 연결리스트는 위에 그림과 같은 노드들이 연결된 리스트를 말한다. 노드는 두 영역으로 나누어지는데 바로 데이터 영역과 포인터이다. 데이터 영역에는 당연히 데이터를 담는 영역이며, 포인터는 다음이나 이전의 노드의 참조값을 가지고 있어 다른 노드와의 연결을 담당한다.

LinkedList 특징

LinkedList의 첫번째 특징으로는 하나의 메모리 공간에 순차적으로 데이터를 보관하는(정적할당) 배열과는 달리 연결리스트는 각각 떨어진 공간에 존재하는 데이터를 참조값을 통해 연결해 놓은 것(동적할당)이라는 점이다.

• 그림1

또 배열처럼 중간에 요소를 삽입 또는 삭제 시 재배치에 발생하는 오버헤드도 발생하지 않는다.(배열의 경우는 마치 일자로 된 교회의자에 앉아 있는 사람들 사이에 앉으려는 행위와 같다: 한명 때문에 많은 사람이 한칸씩 당겨 안거나 한칸씩 비켜줘야함)

• 연결리스트 재배치 예시

그림1의 연결리스트 3,8,5에서 3과 8사이에 6을 집어 넣으려면 3의 포인터 참조값을 8->6으로 6의 참조값을 8로만 설정해주면 된다.

단점으로는 배열처럼 Index값을 가지고 있는 것이 아니기 때문에 데이터에 접근하려면 첫 번째 데이터부터 원하는 데이터까지 순차적으로 찾아가야만 한다는 것이다(8을 찾아가려면 각 노드의 포인터를 따라 3->6->8). 결과적으로 접근 속도가 느리다는 단점을 가지게 된다.

또한 연결 정보(포인터)를 저장하는 별도의 영역이 필요하기 때문에 저장공간의 효율이 높지 않다.

head

• head: 가장 첫 노드를 가르키는 프로퍼티를 뜻함

그림1의 경우 3이란 data를 가지고 있는 노드를 head라 할 수 있음

Swift에서 LinkedList와 Node 구현하기

• Node

class Node<T: CalculateItem> {
    private var data: T?
    var next: Node<T>?
    // 다음 노드의 참조값을 담는 영역이기때문에 Node자체를 타입으로 가지고 있다.
    init(data: T, next: Node?) {
        self.data = data
        self.next = next
    }
}

extension Node: Equatable {
    static func == (lhs: Node<T>, rhs: Node<T>) -> Bool {
        lhs === rhs
    }
}
// 제네릭 타입은 무슨 형태의 타입이 대입 될지 모르기 때문에 Equatable 프로토콜을 채택하고 있지 않다(Int, String등은 채택하고 있음). 그렇기 때문에 추후 값을 비교 하고 싶다면 채택을 별도로 해주어야 한다.

• LinkedList

struct LinkedList<T: CalculateItem> {
    private(set) var head: Node<T>?

    var isEmpty: Bool {
            return head == nil
        }

    mutating func append(data: T) {
        if head == nil {
            head = Node(data: data)
            return
        }

        var node = head
        while node?.next != nil {
            node = node?.next
        }
        node?.next = Node(data: data)
    }

   mutating func removeFirst() -> T? {
        if head == nil {
            return nil
        }

        let firstElement = head?.data
        head = head?.next
        return firstElement
    }

    mutating func removeAll() {
        head = nil
    }
    //ARC의 의해 자신을 가르키는 참조값이 없을 경우 데이터영역에서 자동 해제 됨, 그러므로 head만 nil로 만들어 주면 모든 값이 삭제됨
}