Linked List (링크드리스트)

링크드 리스트는 이름과 같이 하나하나의 요소가 연결되어 리스트를 이루는 구조입니다. 그리고 보통 싱글 링크드 리스트 (Single Linked List)와 더블 링크드 리스트 (Double Linked List)로 나뉩니다.

 

링크드 리스트를 사용하게 되면, 새로운 요소를 넣을 때 그 요소와 원래의 요소들을 연결하기 때문에 미리 데이터 공간을 할당할 필요가 없어집니다. 하지만 연결을 위한 별도 데이터 공간이 필요하기 때문에 저장공간 효율이 높지는 않습니다. 중간 데이터를 삭제할 때도 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하죠.

 

하지만 만약 데이터를 얼마나 집어넣을지 모르는 상태라면 링크드리스트를 사용해보는 게 좋습니다. 애초에 많은 데이터 공간을 할당하고 시작하는 것보다 리스트에 추가해야 할 요소가 생길 때마다 리크드리스트로 연결하면 되니까요! 저는 처음 학교에서 자료구조를 배울 때, 싱글 링크드 리스트와 더블 링크드 리스트를 Java로 구현해보는 게 과제였습니다. 그 때는 더블 링크드 리스트 중간에서 데이터를 삭제하는 과정이 왜 그리 복잡하게 느껴졌는지 모르겠어요ㅋㅋ 지금 생각해보면 당연히 중간을 삭제하면 앞뒤를 연결하는게 당연한 과정인데 말이죠. 그래서 링크드 리스트가 갑자기 생각난 김에 오늘은 Swift로 싱글 링크드 리스트와 더블 링크드 리스트를 구현해보려 합니다. :)

 

먼저 링크드 리스트를 이루는 하나의 요소를 Node라고 합니다. 그리고 리스트 가장 앞에 있는 Node를 head라고 하겠습니다. 인덱스로 구분하는 일반 리스트와 다르게 링크드 리스트는 이 Head부터 시작해서 요소를 찾기 시작합니다. 그렇기 때문에 삽입/수정/삭제에 요소를 찾는 시간이 추가적으로 발생할 수 있습니다.

 

 

Single Linked List (싱글 링크드 리스트)

Node는 자신이 가지는 값 value와 다음에 오는 node에 대한 정보를 가지고 있습니다. 그리고 각 node를 연결하면 아래와 같은 그림이 나오게 됩니다.

 

 

 

따라서 요소를 삽입할 때는 아래와 같이 삽입할 위치를 먼저 찾고, 마지막 노드의 node가 삽입하려는 노드를 가리키도록 합니다.

func insert(_ value: T) {
    size += 1
    guard var current = self.head else {
        self.head = Node(value)
        return
    }
        
    while current.node != nil { current = current.node! }
    current.node = Node(value)
}

 

 

요소를 수정할 때는 인덱스에 해당하는 위치를 먼저 찾고, 해당 노드의 value를 수정해줍니다.

func update(index: Int, value: T) {
    if index >= size {
        print("index가 리스트의 범위를 초과합니다.")
        return
    }
    var current = head
    for _ in 0..<index { current = current?.node }
    current?.value = value
}

 

 

요소를 삭제할 때에는 인덱스에 해당하는 위치를 먼저 찾고, 삭제할 노드의 앞에 있는 노드의 node가 삭제할 노드의 뒤에 있던 노드를 가리키도록 합니다.

👉아니 그럼 그 삭제된 노드는 그냥 메모리에 둥둥 떠다니게 되는건가??? 하는 생각이 들 수도 있지만, 이렇게 아무도 삭제할 노드를 참조하지 않게 되면 참조 카운팅이 0이 되기 때문에 ARC가 정리해주겠죠?

func remove(index: Int) {
    if index >= size {
        print("index가 리스트의 범위를 초과합니다.")
        return
    }
    if index == 0 {
        head = head?.node
        return
    }
    
    var pre = head
    var current = head
    for _ in 0..<index {
        pre = current
        current = current?.node
    }
    pre?.node = current?.node
    current = nil
}

 

 

따라서 싱글 링크드 리스트의 전체 코드는 아래와 같습니다.

import Foundation

class Node<T> {
    var value: T
    var node: Node? = nil
    
    init (_ value: T) {
        self.value = value
    }
}

class SingleLinkedList<T> {
    var head: Node<T>? = nil
    var size: Int = 0
    
    func insert(_ value: T) {
        size += 1
        guard var current = self.head else {
            self.head = Node(value)
            return
        }
        
        while current.node != nil { current = current.node! }
        current.node = Node(value)
    }
    
    func update(index: Int, value: T) {
        if index >= size {
            print("index가 리스트의 범위를 초과합니다.")
            return
        }
        var current = head
        for _ in 0..<index { current = current?.node }
        current?.value = value
    }
    
    func remove(index: Int) {
        if index >= size {
            print("index가 리스트의 범위를 초과합니다.")
            return
        }
        if index == 0 {
            head = head?.node
            return
        }
        
        var pre = head
        var current = head
        for _ in 0..<index {
            pre = current
            current = current?.node
        }
        pre?.node = current?.node
        current = nil
    }
    
    func printList() {
        guard var current = self.head else {
            print("[]")
            return
        }
        print("[", terminator: "")
        while current.node != nil {
            print(current.value, terminator: ", ")
            current = current.node!
        }
        print(current.value, terminator: "]\n")
    }
}

 

 

Double Linked List (더블 링크드 리스트)

싱글 링크드 리스트와 다르게 더블 링크드 리스트는 자신의 앞 뒤 요소와 연결을 해야하기 때문에 앞에 오는 요소를 가리키는 pre와 뒤에 오는 요소를 가리키는 next를 가집니다.

 

싱글 링크드 리스트와 마찬가지로 요소를 삽입할 때는 아래와 같이 삽입할 위치를 먼저 찾고, 마지막 노드의 next가 삽입하려는 노드를 가리키도록 합니다. 그리고 삽입하려는 노드의 pre가 마지막 노드를 가리키게 합니다.

func insert(_ value: T) {
    size += 1
    guard var current = self.head else {
        self.head = Node(value)
        return
    }
    let newNode = Node(value)
    while current.next != nil { current = current.next! }
    current.next = newNode
    newNode.pre = current
}

 

 

요소를 수정할 때는 인덱스에 해당하는 위치를 먼저 찾고, 해당 노드의 value를 수정해줍니다.

func update(index: Int, value: T) {
    if index >= size {
        print("index가 리스트의 범위를 초과합니다.")
        return
    }
    var current = head
    for _ in 0..<index { current = current?.next }
    current?.value = value
}

 

 

요소를 삭제할 때에는 인덱스에 해당하는 위치를 먼저 찾고, 삭제할 노드의 앞에 있는 노드의 next가 삭제할 노드의 뒤에 있던 노드를 가리키도록 합니다. 그리고 삭제할 노드의 뒤에 있던 노드의 pre가 삭제할 노드의 앞에 있던 노드를 가리키도록 하여 삭제할 노드의 앞 뒤 노드를 연결해줍니다.

func remove(index: Int) {
    if index >= size {
        print("index가 리스트의 범위를 초과합니다.")
        return
    }
    if index == 0 {
        head?.next?.pre = nil
        head = head?.next
        return
    }
    
    var pre = head
    var current = head
    for _ in 0..<index {
        pre = current
        current = current?.next
    }
    pre?.next = current?.next
    current?.next?.pre = pre
    current = nil
}

 

 

따라서 더블 링크드 리스트의 전체 코드는 아래와 같습니다.

class Node<T> {
    var value: T
    var pre: Node? = nil
    var next: Node? = nil
    
    init (_ value: T) {
        self.value = value
    }
}

class DoubleLinkedList<T> {
    var head: Node<T>? = nil
    var size: Int = 0
    
    func insert(_ value: T) {
        size += 1
        guard var current = self.head else {
            self.head = Node(value)
            return
        }
        let newNode = Node(value)
        while current.next != nil { current = current.next! }
        current.next = newNode
        newNode.pre = current
    }
    
    func update(index: Int, value: T) {
        if index >= size {
            print("index가 리스트의 범위를 초과합니다.")
            return
        }
        var current = head
        for _ in 0..<index { current = current?.next }
        current?.value = value
    }
    
    func remove(index: Int) {
        if index >= size {
            print("index가 리스트의 범위를 초과합니다.")
            return
        }
        if index == 0 {
            head?.next?.pre = nil
            head = head?.next
            return
        }
        
        var pre = head
        var current = head
        for _ in 0..<index {
            pre = current
            current = current?.next
        }
        pre?.next = current?.next
        current?.next?.pre = pre
        current = nil
    }
    
    func printList() {
        guard var current = self.head else {
            print("[]")
            return
        }
        print("[", terminator: "")
        while current.next != nil {
            print(current.value, terminator: ", ")
            current = current.next!
        }
        print(current.value, terminator: "]\n")
    }
}