[Swift] 단방향 Linked List 구현해보기

[Swift] 단방향 Linked List

---

 단방향 링크드 리스트는 데이터를 갖고 있는 노드들을 포인터로 선형적으로 연결해 사용하는 자료구조
 삭제와 삽입에 O(1)의 시간 복잡도가 걸리기 때문에 빈번하게 삽입/삭제가 필요한 상황에 유용
 하지만 원하는 노드까지의 '탐색'은 O(N)이 걸림
 따라서 배열처럼 동시에 인덱스를 통한 Random Access는 불가능하고, 처음부터 원하는 데이터가 나올 때까지 탐색을 진행해야 하기 때문에 O(N)의 시간 복잡도가 요구된다는 단점이 있음

///
/// data: 실제로 저장할 데이터
/// next: 현재 노드의 다음 노드를 저장할 데이터
///

class Node<T: Equatable> {
    let data: T
    var next: Node?
    
    init(data: T, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

 

///
/// head: 연결 리스트는 특정 데이터에 연결하려면 첫 번째 노드부터 순차적으로 접근해야 함
///
class LinkedList<T: Equatable> {
    private var head: Node<T>?

    /*
     append의 경우 연결 리스트의 가장 마지막 노드를 찾아내서 그 뒤에 추가해주면 되는데,
     노드의 가장 마지막을 찾아내는 방법은 head 노드부터 순회하며 node.next가 nil인 경우를 찾으면 됨
     */
    /// append(data: ) - 연결 리스트 맨 마지막에 노드 추가
    public 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)
    }

    /*
     연결 리스트의 경우 중간에 노드를 추가할 수 있지만, 배열과 달리 index가 없기 때문에
     만약 index를 추가하고 싶은 경우의 구현
     (연결 리스트는 추가/삭제 구현이 번거로움)
     */
    /// insert(data: at: ) - 연결 리스트 중간에 노드 추가
    public func insert(data: T, at index: Int) {
        if head == nil {
            head = Node(data: data)
            return
        }
        
        var node = head
        for _ in 0..<(index-1) {
            if node?.next == nil { break }
            node = node?.next
        }
        
        let nextNode = node?.next
        node?.next = Node(data: data)
        node?.next?.next = nextNode
    }
    
    public func removeLast() {
        if head == nil { return }
        
        //head를 삭제하는 경우
        if head?.next == nil {
            head = nil
            return
        }
        
        var node = head
        while node?.next?.next != nil {
            node = node?.next
        }
        node?.next = node?.next?.next // 맨 마지막 노드의 next는 nil이므로! (nil 직접 넣어도 OK)
    }
    
    /// remove(at: ) - 연결 리스트 중간 노드 삭제
    public func remove(at index: Int) {
        if head == nil { return }
        
        //head를 삭제하는 경우
        if index == 0 || head?.next == nil {
            head = head?.next
            return
        }
        
        var node = head
        for _ in 0..<(index-1) {
            if node?.next?.next == nil { break }
            node = node?.next
        }
        
        node?.next = node?.next?.next
    }
    
    /// 노드에 저장된 데이터를 직접 검색해서 해당 노드를 반환하는 기능
    /// head에서부터 순차적으로 찾아야 함
    public func searchNode(from data: T) -> Node<T>? {
        if head == nil { return nil }
        
        var node = head
        while node?.next != nil {
            if node?.data == data { break }
            node = node?.next
        }
        return node
    }
}

---

테스트 결과

let list = LinkedList(head: Node(data: 1))
print(list.printAll())
list.append(data: 2)
print(list.printAll())
list.insert(data: 5, at: 1)
print(list.printAll())
list.removeLast()
print(list.printAll())
print(list.searchNode(from: 5)?.data ?? 0)
list.remove(at: 1)
print(list.printAll())

node.data = Optional(1) //init
node.data = Optional(1) //append(2)
node.data = Optional(2) //append(2)
node.data = Optional(1) //insert(5, 1)
node.data = Optional(5) //insert(5, 1)
node.data = Optional(2) //insert(5, 1)
node.data = Optional(1) //removeLast()
node.data = Optional(5) //removeLast()
5 //searchNode(from: 5)
node.data = Optional(1) //remove(at: 1)

다음에는 순차적으로 원하는 데이터를 찾을 때 O(N)이 걸리는 단방향 링크드 리스트를 보완할

양방향 링크드 리스트에 대해 알아보자.