Linked List

Linked List

• 메모리 상에 원소들을 불연속적으로 배치한 선형 자료구조
• 불연속적인 대신 이전이나 다음 노드의 위치를 알고 있음
• 리스트의 각 원소를 노드라고 부름
  • 노드는 데이터와 다른 노드에 대한 참조를 가짐
  • 맨 앞/뒤 노드를 head/tail 노드라고 부름
• 어떤 노드에 대한 참조를 갖느냐에 따라 크게 3가지 종류로 나눌 수 있음

 

Singly Linked List

각 노드는 데이터와 다음 노드에 대한 링크(참조)를 가짐

 

Doubly Linked List

각 노드는 이전, 다음 노드에 대한 링크(참조)를 가짐

 

Circular Linked List

마지막 노드가 헤드 노드에 대한 링크(참조)를 가짐

 

 

성질

1. 헤드 노드에 대한 참조만 가지고 있기 때문에 임의의 원소에 접근/변경하려면 O(n)의 시간이 소요

2. 다른 노드의 주소 값을 가지고 있어야 하므로 O(n)의 메모리 오버헤드(공간 복잡도) 존재

3. 원소들이 메모리 상에 연속해있지 않아도 되어 할당은 쉽지만, cache hit rate는 낮음

 

 

시간 복잡도

임의의 노드에 접근

• 헤더부터 순차적으로 탐색해야 하기 때문에 O(n)의 시간이 소요

 

임의의 위치에 노드 변경, 추가, 제거

• 이미 노드에 접근해 있는 상태를 가정
• 노드 참조 값만 수정하면 되기 때문에 O(1)의 시간이 소요

 

배열과 연결 리스트

	배열	연결 리스트
종류	선형	선형
메모리 상의 배치	연속	불연속
임의의 원소에 접근	O(1)	O(n)
임의의 위치에 원소 추가/제거	O(n)	O(1)
메모리 오버헤드	-	O(n)

 

구현

• Class로 구현한 doubly linked list

Node

• 이전/다음 노드 없을 수 있으므로 → 옵셔널
• reference cycle 방지를 위해 next나 prev 중 하나를 weak 하게 선언

class Node<T> {
    var value: T
    var next: Node?
    weak var prev: Node?
    
    init(value: T, next: Node? = nil, prev: Node? = nil) {
        self.value = value
        self.next = next
        self.prev = prev
    }
}

 

Linked List

final class LinkedList<T> {
    private(set) var head: Node<T>?
    private(set) var tail: Node<T>?
    
    var isEmpty: Bool { head == nil }
    
    var size: Int {
        guard var node = head else { return 0 }
        
        var count = 1
        while let next = node.next {
            node = next
            count += 1
        }
        
        return count
    }
    
    subscript(index: Int) -> Node<T> {
        guard index >= 0 && index < size else { fatalError("Index out of range") }
        
        var node = head
        for _ in 0 ..< index { node = node?.next }
        
        return node!
    }
    
    
    func append(_ newElement: T) {
        let newNode = Node(value: newElement, next: nil, prev: tail)
        
        if let tail { tail.next = newNode }
        else { head = newNode }
        
        tail = newNode
    }
    
    func insert(_ newElement: T, at index: Int) {
        guard index >= 0 && index <= size else { fatalError("Index out of range") }
        
        guard !isEmpty else {
            self.append(newElement)
            return
        }

        if index == 0 {
            let newNode = Node(value: newElement, next: self[index], prev: nil)
            self[index].prev = newNode
            head = newNode
        } else if index == self.size {
            let newNode = Node(value: newElement, next: nil, prev: self[index - 1])
            self[index - 1].next = newNode
            tail = newNode
        } else {
            let newNode = Node(value: newElement, next: self[index], prev: self[index - 1])
            self[index - 1].next = newNode
            self[index].prev = newNode
        }
    }
    
    func remove(at index: Int) {
        guard !isEmpty || index >= 0 && index < size else { fatalError("Index out of range") }
        
        if index == 0 {
            head = self[1]
            head?.prev = nil
        } else if index == self.size - 1 {
            tail = self[index - 1]
            tail?.next = nil
        } else {
            self[index + 1].prev = self[index - 1]
            self[index - 1].next = self[index + 1]
        }
    }
}

 

 

 

코딩 테스트를 위한 Linked List 유형 파악하기

• 이 장을 시작하기 전에 클래스, 객체, 속성 등을 포함한 객체 지향 프로그래밍 개념에 대한 기본적인 이해가 필요.

 

노드

• 하나의 정수나 문자열과 같은 단일 데이터 이상의 정보를 가진 요소
• 예를 들어, [1, 2, 3]이라는 배열이 있다고 가정했을 때, 각 요소를 1. 정수, 2. 인덱스 두 개의 정보를 가진 노드로 볼 수 있음

data: 2   // 정수
index: 1  // 인덱스

 

 

배열은 요소들이 메모리에 연속적으로 저장됩니다. 따라서 인덱스를 통해 배열의 요소에 접근할 수 있습니다.

연결 리스트는 배열과 유사하게 데이터를 순서대로 저장하지만, 노드 객체를 사용하여 구현됩니다. 각 노드는 Next에 대한 포인터를 가지고 있으며, 시퀸스에서 다음 요소를 나타내는 노드를 가리킵니다.

 

예제

1 ->  2 -> 3 데이터를 나타내는 연결 리스트를 생성하는 예제 코드입니다.

class ListNode {
    var data: Int
    var next: ListNode?

    init(_ data: Int) {
        self.data = data
        self.next = nil
    }
}

let one = ListNode(1)
let two = ListNode(2)
let three = ListNode(3)
one.next = two
two.next = three
let head = one

print(head.data)
print(head.next!.data)
print(head.next!.next!.data)

 

연결 리스트의 시작 노드를 Head 라고 부릅니다. 또한, Head는 연결 리스트의 모든 요소에 도달할 수 있는 유일한 노드이기 때문에 참조를 유지해야 합니다. 

 

 

배열과 비교한 장단점

알고리즘 문제에서 장단점은 크게 중요하지 않습니다. 연결 리스트의 문제 대부분은 입력으로 연결 리스트가 주어지기 때문에 사용 여부를 결정할 필요가 없습니다. 하지만 최적의 알고리즘이나, 면접에서 관련 질문을 받을 수 있기 때문에 알고 있는 것이 중요합니다.

 

연결 리스트의 주요 장점은 임의의 위치에 요소를 추가하고 제거할 때, O(1)의 시간이 소요되는 것입니다. 단, 이 작업을 수행할 위치의 노드에 대한 참조를 가지고 있어야 합니다. 그렇지 않을 경우, head부터 원하는 위치까지 순차 탐색이 이루어져야 하기 때문입니다. 이는 O(n)의 시간이 소요됩니다. 하지만 배열에서 임의 위치 추가 및 제거에 소요되는 O(n)보다는 효율적입니다.

 

연결리스트의 주요 단점은 랜덤 액세스가 불가능 하다는 거죠. 따라서 head부터 시작하여 순차 탐색을 해야 합니다. 이는 O(n)의 시간이 소요됩니다.

 

알고리즘 문제에서는 덜 중요하지만, 면접 토론에서 나올 수 있는 몇 가지 추가 사항이 있습니다. 연결 리스트는 고정 크기가 없다는 장점을 가지고 있습니다. 배열은 연속적이기 때문에 크기가 초과되면, 새로운 배열로 다시 할당하여 크기를 조절합니다. 이는 비용이 많이 듭니다. 반면, 연결리스트는 비 연속적이기 때문에 이러한 문제가 필요 없죠. 하지만 연결리스트는 포인터를 위한 추가 저장 공간을 필요로 하기 때문에 배열보다 오버헤드가 더 큽니다. 

 

 

 

연결 리스트의 작동 원리

노드와 포인터를 코드로 조작하는 방법을 이해하는 것인 필수적입니다. 또한 포인터를 다루는 개념은 소프트웨어 엔지니어에게 기본적입니다.

 

할당 (=)

기존의 연결 리스트 노드에 포인터를 할당하면, 포인터는 메모리의 객체를 참조합니다.

예를 들어, head라는 노드가 있다고 합시다.

let head = ListNode(1)
head.next = ListNode(2)

var ptr = head
head = head.next!
head = nil

 

이 코드 라인들 이후에도 ptr은 여전히 원래의 헤드 노드를 참조합니다. 헤드 변수는 변경되었지만요. 

이것이 첫 번째 중요한 개념입니다. 변수는 수정되지 않는 한 노드에 남아있습니다.

 

체이닝 .next

여러 개의 .next를 사용하는 것입니다.

예를 들어, 1 -> 2 -> 3의 연결 리스트가 주어지고, head가 첫 번째 노드를 가리키고 있다고 가정합시다. 

여기서 head.next.next 는? = 2.next인 3을 가리킵니다.

 

순회

연결 리스트를 앞으로 순회하는 것은 간단한 루프로 가능합니다.

예를 들어, 정수 연결 리스트의 모든 값의 합을 구하는 코드입니다.

func getSum(_ head: ListNode?) -> Int {
    var ans = 0
    var current = head
    
    while let node = current {
        ans += node.data
        current = node.next
    }
    return ans
}

let head = ListNode(1)
head.next = ListNode(2)
head.next?.next = ListNode(3)

print(getSum(head))  // 출력: 6

 

마지막 노드에서 next 포인터는 null이죠? 따라서 마지막 노드까지 연산을 수행하고, while 문이 종료됩니다.

 

재귀

head.next로 이동하는 것은 배열에서 다음 요소로 반복하는 것과 같습니다.

순회는 재귀적으로도 수행할 수 있습니다.

func getSum(_ head: ListNode?) -> Int {
    guard let node = head else { return 0 }
    return node.data + getSum(node.next)
}

let head = ListNode(1)
head.next = ListNode(2)
head.next?.next = ListNode(3)

print(getSum(head))  // 출력: 6

 

 

 

연결 리스트의 종류

1. 단일 연결 리스트

• 가장 일반적인 유형이며, 위 코드에서 사용된 것
• 각 노드가 다음 노드에 대한 포인터만 가짐
• 이는 순회할 때, 앞으로만 이동할 수 있음을 의미
• 다음 노드를 참조하는 데 사용되는 포인터는 next라고 부름

 

삽입 

요소를 추가하여, 위치 i에 해당하는 요소로 만들고 싶다면?

 

1. 현재 위치 i - 1에 있는 요소에 대한 포인터가 필요

2. 다음 요소(현재 i에 있는 기존 요소)를 x라고 부르면, 삽입 후에 위치는 i + 1로 밀려남

3. x가 새로 추가되는 노드의 next가 되어야 하고, i - 1에 있는 노드의 next노드가 새롭게 추가되는 노드가 되어야 함.

class ListNode {
    var data: Int
    var next: ListNode?

    init(_ data: Int) {
        self.data = data
        self.next = nil
    }
}

// 위치 i - 1에 있는 노드를 prev_node로 가정
func addNode(_ prevNode: ListNode?, _ nodeToAdd: ListNode) {
    guard let prevNode = prevNode else { return }
    
    nodeToAdd.next = prevNode.next  // 추가될 노드의 next는 원래 위치에 있는 노드로 설정 (밀려나기 때문)
    prevNode.next = nodeToAdd       // 이전 노드의 next는 새롭게 추가될 노드로 설정
}

 

참고로 연산을 수행하려는 위치의 이전 노드에 대한 포인터를 가지고 있는 경우는 거의 없습니다.

일반적으로는 원하는 위치에 도달할 때까지 head부터 순회해야 합니다.

이는 O(n)의 시간이 소요됩니다.

 

 

삭제

위치 i에 있는 요소를 삭제하고 싶다고 가정해 봅시다. 다시 말하지만, 현재 위치 i - 1에 있는 요소에 대한 포인터가 필요합니다. i - 1에 대한 노드의 next를 i의 next로 설정하면 됩니다.

class ListNode {
    var data: Int
    var next: ListNode?

    init(_ data: Int) {
        self.data = data
        self.next = nil
    }
}

// 위치 i - 1에 있는 노드를 prev_node로 가정
func deleteNode(_ prevNode: ListNode?) {
    guard let prevNode = prevNode, 
          let nodeToDelete = prevNode.next else { return }
          
    prevNode.next = nodeToDelete.next
}

 

 

이중 연결 리스트

• 각 노드가 이전 노드에 대한 포인터, 다음 노드에 대한 포인터 두 가지를 가지고 있음
• 양 방향으로 순회가 가능

 

단일 연결 리스트에서는 i 위치에서 추가나 삭제를 하려면 i - 1 위치의 노드에 대한 참조가 필요했습니다. 

이중 연결 리스트에서는 i 위치의 노드에 대한 참조만 필요합니다. 해당 노드의 prev 포인터가 i - 1 위치의 노드의 참조이기 때문입니다.

class ListNode {
    var data: Int
    var next: ListNode?
    var prev: ListNode?

    init(_ data: Int) {
        self.data = data
        self.next = nil
        self.prev = nil
    }
}

// 위치 i에 있는 노드를 node로 가정
func addNode(_ node: ListNode?, _ nodeToAdd: ListNode) {
    guard let node = node, let prevNode = node.prev else { return }
    nodeToAdd.next = node      // 추가될 노드의 다음 노드로 위치 i에 있는 노드를 설정
    nodeToAdd.prev = prevNode  // 추가될 노드의 이전 노드로 위치 i에 있는 노드의 이전 노드를 설정
    prevNode.next = nodeToAdd  // 이전 노드의 다음 노드로 추가될 노드를 설정
    node.prev = nodeToAdd      // 위치 i에 있는 노드의 이전 노드로 추가될 노드를 설정
}

// 위치 i에 있는 노드를 node로 가정
func deleteNode(_ node: ListNode?) {
    guard let node = node, let prevNode = node.prev, let nextNode = node.next else {
        return
    }
    prevNode.next = nextNode  // 이전 노드의 다음 노드로 i+1 노드를 설정
    nextNode.prev = prevNode  // i+1 노드의 이전 노드로 이전 노드를 설정
}

 

 

 

 

Linked lists with sentinel nodes

센티넬 노드는 연결 리스트의 시작과 끝에 위치하며, 연산을 수행하고, 연산에 필요한 코드를 더 깔끔하게 만들기 위해 사용됩니다. 이 아이디어는 연결 리스트에서 노드가 하나도 없더라도 head와 tail에 대한 포인터를 유지하는 것입니다. 연결 리스트의 실제 head는 head.next 이고, 실제 tail은 tail.prev입니다. 센티넬 노드 자체는 우리 연결 리스트의 일부가 아닙니다.

 

앞서 살펴본 코드는 에러에 약합니다. 예를 들어 리스트의 마지막 노드를 삭제하려고 할 때, nextNode는 Null이 되어 nextNode.next에 접근하려고 하면 오류가 발생합니다. 센티넬 노드를 사용하면, 마지막 노드의 next가 센티넬 tail을 가리키므로 걱정할 필요가 없습니다. 

 

또한 센티넬 노드는 연결 리스트의 앞이나 뒤에서 쉽게 추가하고 제거할 수 있도록 해줍니다. 특정 위치에서 연산을 수행할 노드에 대한 참조가 있는 경우, 추가 및 제거는 O(1)의 시간이 소요되었었져? 이것처럼 센티넬 tail 노드를 사용하면 리스트의 끝에서 O(1) 시간 내에 연산을 수행할 수 있습니다.

class ListNode {
    var data: Int?
    var next: ListNode?
    var prev: ListNode?

    init(_ data: Int?) {
        self.data = data
        self.next = nil
        self.prev = nil
    }
}

let head = ListNode(nil)
let tail = ListNode(nil)
head.next = tail
tail.prev = head

func addToEnd(_ nodeToAdd: ListNode) {
    nodeToAdd.next = tail        // 추가할 노드의 다음 노드를 tail로 지정
    nodeToAdd.prev = tail.prev   // 추가할 노드의 이전 노드는 tail의 이전 노드로 지정, 헤더가 추가될 헤더의 이전 노드로 등록됨
    tail.prev?.next = nodeToAdd  // tail의 이전 노드의 다음 노드는 추가할 노드로 설정, 헤더의 다음 노드가 추가될 노드로 등록됨
    tail.prev = nodeToAdd        // tail의 이전 노드를 추가할 노드로 설정
}

func removeFromEnd() {
    if head.next === tail { return }  // 헤더의 다음 노드가 tail일 경우, 제거할 노드가 없기 때문에 return
    
    // 만약 마지막 노드가 있을 경우
    if let nodeToRemove = tail.prev {
        nodeToRemove.prev?.next = tail  // i-1 노드의 다음 노드를 tail로 설정, i-1 노드가 마지막 노드로 설정됨
        tail.prev = nodeToRemove.prev   // 마지막 노드를 i-1 노드로 설정
    }
}

func addToStart(_ nodeToAdd: ListNode) {
    nodeToAdd.prev = head        // 추가될 노드의 이전 노드를 헤더로 -> 첫 번째 요소로 추가될 노드를 설정
    nodeToAdd.next = head.next   // 추가될 노드의 다음 노드를 첫번째 요소로
    head.next?.prev = nodeToAdd  // 첫 번째 요소의 이전 노드를 추가될 노드로 설정
    head.next = nodeToAdd        // 헤더의 다음 노드를 추가될 노드로 설정
}

func removeFromStart() {
    if head.next === tail { return }  // 첫 번째 요소가 없을 경우 return
    
    // 제거할 첫 번째 노드가 있을 경우
    if let nodeToRemove = head.next {
        nodeToRemove.next?.prev = head
        head.next = nodeToRemove.next
    }
}

 

 

 

 

더미 포인터

앞서 말했듯이, 헤드에 대한 참조를 유지하여 언제든지 어떤 요소에도 접근할 수 있도록 하는 것이 일반적입니다. 때로는 더미 포인터를 사용하여 순회하고, head는 헤드 위치에 유지하는 것이 더 좋습니다.

func getSum(_ head: ListNode?) -> Int {
    var ans = 0
    var dummy = head 
    
    while let node = dummy {
        ans += node.data
        dummy = node.next
    }
    
    // 이전과 동일하지만, 여전히 head에 대한 포인터를 유지합니다.
    return ans
}

 

이렇게 더미 포인터를 사용하면, 헤드에 대한 참조를 잃지 않고, 연결 리스트를 순회할 수 있습니다.

 

다음은 연습을 위해 1 <-> 2 <-> 3 이중 연결 리스트를 구현하는 예제입니다.

// 1 <-> 2 <-> 3 생성
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)

// 연결 설정
node1.next = node2
node2.next = node3

node3.prev = node2
node2.prev = node1

// 연결 리스트 출력
var current: ListNode? = node1
while let node = current {
    print(node.val, terminator: " <-> ")
    current = node.next
}
print("nil")

 

연결 리스트의 중요한 부분 중 하나는 포인터를 이동하는 것입니다. 포인터를 올바르게 재할당하는 방법과 재할당 순서를 이해하는 것이 중요합니다. 이를 가장 잘 이해하는 방법은 시각적으로 과정을 보고, 예제를 통해 연습하는 것입니다.