Swift: 연결리스트 (Linked List)

오늘 다룰 내용

연결 리스트는 데이터들의 모음인 기본적인 자료구조입니다. 연속적인 메모리 블록을 할당하는 배열과 달리, 연결 리스트는 참조(포인터)를 통해 연결된 개별 노드로 구성됩니다. 스위프트에서 이들이 어떻게 작동하고 구현되는지 살펴보겠습니다

연결 리스트(Linked List) 기본 개념

연결 리스트는 각 노드가 데이터와 다음 노드에 대한 참조(포인터)를 포함하는 자료구조입니다. 배열과 달리 메모리 상에서 연속적으로 위치하지 않고, 각 노드는 독립적으로 존재하며 서로 연결됩니다.
연결 리스트는 크게 두 가지 유형이 있습니다:

• 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드에 대한 참조만 가집니다.
• 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드에 대한 참조를 모두 가집니다.

리스트의 시작점을 추적하기 위해 head 포인터를 사용하고, 종종 리스트의 끝을 가리키는 tail 포인터도 함께 사용합니다.

연결 리스트의 성능

연결 리스트는 대부분의 연산이 O(n) 시간이 소요되어 일반적으로 배열보다 느립니다. 하지만 메모리를 복사할 필요 없이 포인터만 변경하면 되므로 더 유연합니다.
특정 노드에 접근하려면 head에서 시작하여 next 포인터를 따라가야 하기 때문에 연산 시간이 O(n)입니다.

그러나 한 번 노드에 대한 참조를 얻으면 삽입 및 삭제와 같은 작업은 매우 빠릅니다.

이런 특성 때문에 연결 리스트를 다룰 때는 가능하면 리스트의 앞부분에 새 항목을 삽입하는 것이 좋습니다. 이는 O(1) 연산입니다.
*tail 포인터를 유지한다면 뒤에 삽입하는 것도 마찬가지로 빠릅니다.

Swift로 구현한 간단한 연결 리스트

먼저 노드를 정의하는 클래스를 만들어 보겠습니다:

public class LinkedListNode<T> {
  var value: T
  var next: LinkedListNode?
  weak var previous: LinkedListNode?

  public init(value: T) {
    self.value = value
  }
}

이는 제네릭 타입으로, T는 노드에 저장하고 싶은 어떤 종류의 데이터도 될 수 있습니다.
이제 LinkedList 클래스를 구현해 보겠습니다:

public class LinkedList<T> {
  public typealias Node = LinkedListNode<T>

  private var head: Node?

  public var isEmpty: Bool {
    return head == nil
  }

  public var first: Node? {
    return head
  }
}

리스트가 비어있는지 확인하는 isEmpty 프로퍼티와 첫 번째 노드를 반환하는 first 프로퍼티를 구현했습니다. last 프로퍼티는 head에서 시작하여 다음 노드가 nil일 때까지 리스트를 따라가서 마지막 노드를 찾습니다.

리스트에 노드 추가하기

리스트 끝에 새 노드를 추가하는 append 메서드를 구현해 보겠습니다:

  public func insert(_ node: Node, atIndex index: Int) {
   let newNode = node
   if index == 0 {
     newNode.next = head                      
     head?.previous = newNode
     head = newNode
   } else {
     let prev = self.node(atIndex: index-1)
     let next = prev.next

     newNode.previous = prev
     newNode.next = prev.next
     prev.next = newNode
     next?.previous = newNode
   }
}

이 메서드는 새 Node 객체를 생성한 다음, last 프로퍼티를 사용해 마지막 노드를 찾습니다. 마지막 노드가 없다면 리스트가 비어있는 것이므로 head가 새 노드를 가리키도록 합니다. 마지막 노드가 있다면 next와 previous 포인터를 연결하여 새 노드를 연결합니다.

노드 삭제하기

노드를 삭제하는 remove 메서드를 구현해 보겠습니다:

  public func remove(node: Node) -> T {
    let prev = node.previous
    let next = node.next

    if let prev = prev {
      prev.next = next
    } else {
      head = next
    }
    next?.previous = prev

    node.previous = nil
    node.next = nil
    return node.value
  }

이 메서드는 노드를 리스트에서 제거할 때, 이전 노드와 다음 노드 사이의 연결을 재구성합니다. 제거하려는 노드가 첫 번째 노드라면 head 포인터를 업데이트해야 합니다.

리스트 뒤집기

연결 리스트를 뒤집는 알고리즘은 다음과 같습니다

  public func reverse() {
    var node = head
    tail = node // If you had a tail pointer
    while let currentNode = node {
      node = currentNode.next
      swap(&currentNode.next, &currentNode.previous)
      head = currentNode
    }
  }

이 메서드는 전체 리스트를 순회하면서 각 노드의 next와 previous 포인터를 교환합니다. 또한 head 포인터를 가장 마지막 요소로 이동시킵니다.

고급 기능: map과 filter

배열처럼 연결 리스트에도 map과 filter 함수를 구현할 수 있습니다:

  public func map<U>(transform: T -> U) -> LinkedList<U> {
    let result = LinkedList<U>()
    var node = head
    while node != nil {
      result.append(transform(node!.value))
      node = node!.next
    }
    return result
  }

  public func filter(predicate: T -> Bool) -> LinkedList<T> {
    let result = LinkedList<T>()
    var node = head
    while node != nil {
      if predicate(node!.value) {
        result.append(node!.value)
      }
      node = node!.next
    }
    return result
  }

이러한 함수를 사용하면 연결 리스트의 값을 변환하거나 필터링할 수 있습니다.

왜 연결 리스트를 사용할까?

연결 리스트가 유용한 대표적인 예는 큐를 구현할 때입니다. 배열로 큐를 구현하면 앞에서 요소를 제거할 때 다른 모든 요소를 메모리에서 전부 이동시켜야 하므로 느립니다. 하지만 연결 리스트를 사용하면 head가 두 번째 요소를 가리키도록 바꾸기만 하면 되므로 훨씬 빠릅니다.