[자료구조] 배열, 연결리스트(Swift)

배열(Array)

index를 이용하여 한 메모리 공간 안에 데이터들이 "나란히" 저장되어 있음

배열의 장점은 index만 알면 값에 대한 접근이 매우 빠른 것이 배열의장점

하지만 마지막 index 가 아닌 배열요소를 삭제하거나 삽입할 경우에는 배열 재배치하는 작업 때문에 오버헤드가 발생하는 단점이 존재한다

 

 

연결 리스트(LinkedList)

배열의 단점을 보완하기 위해 데이터들을 배열과 같이 보관 하는 것이 아닌

각각 떨어진 공간에 존재하는 데이터를 연결해 놓은것

 

[이미지 출처] geeksforgeeks

배열처럼 중간에 element 삽입이나 삭제 시 재배치에 발생하는 오버헤드가 발생하지 않는다

하지만 데이터에 접근하려면 첫 번째 데이터부터 원하는 데이터까지 순차적으로 찾아가야 해서 접근 속도가 느리다

 

 

[이미지 출처] https://babbab2.tistory.com/86

 

탐색(search) - O(N)

특정한 노드에 접근하기 위해서는 처음 노드부터 내가 찾는 노드까지 재귀적으로 탐색을 해야하기 때문에 O(N)의 시간복잡도를 가집니다.

 

삽입(insert) - O(1) or O(N)

시간복잡도가 가장 적은 경우는 Head Tail 노드인경우 새로운 노드를 삽입하면은 탐색 과정이 없기 때문에 O(1)을 가집니다.

그 외의 경우에는 목표 노드를 찾기 위한 탐색 O(N)과 포인터 변경 O(1) 가 되어 시간복잡도는 O(N)입니다.

 

삭제(delete) - O(1) or O(N)

삽입 과정과 비슷하게 맨앞 맨뒤 노드인경우 삭제후 포인터 변경하면 되기때문에 O(1)을 가집니다.

그 외의 경우네느 노드를 찾기위한 탐색과 삭제후 포인터 변경 O(N) O(1) 가 되어 시간복잡도는 최대 O(N)입니다.

 

연결 Node 구현

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

struct LinkedList<T: Equatable> {
    var head: Node<T>?
    var tail: Node<T>?
    
    mutating func add(node: Node<T>) {
        // head node does not exist
        if head == nil {
            head = node
            tail = node
            return
        }
        
        // search for last node and attatch new
        tail?.next = node
        tail = node
    }
    
    func searchNode(with data: T) -> Node<T>? {
        var now = head
        while now?.data != data && now != nil {
            now = now?.next
        }
        return now
    }
    
    mutating func insert(node: Node<T>, after id: Int) {
        var now = head
        while now?.id != id && now?.next != nil {
            now = now?.next
        }
        
        node.next = now?.next
        now?.next = node
    }
    
    mutating func insert(node: Node<T>, before id: Int) {
        var now = head
        
        if now?.id == id {
            head = node
            node.next = now
            return
        }
        
        while now?.next?.id != id && now?.next != nil {
            now = now?.next
        }
        
        node.next = now?.next
        now?.next = node
    }
    
    mutating func delete(node: Node<T>) -> Bool {
        var now = self.head
        
        // if target node is at head
        if now === node {
            if self.head === self.tail { self.tail = nil }
            self.head = now?.next
            return true
        }
        
        while now?.next !== node && now?.next != nil {
            now = now?.next
        }
        
        // no matching node to delete
        if now == nil { return false }
        
        if now?.next === tail {
            tail = now
        }
        
        // delete node
        now?.next = now?.next?.next
        return true
    }
    
    func showList() {
        var now = head
        print("===== Linked List ======")
        while now != nil {
            now?.next == nil
            ? print("id: \(now?.id) | data: \(now?.data)")
            : print("id: \(now?.id) | data: \(now?.data) -> ")
            now = now?.next
        }
        print("========================")
    }
}

 

왜 사용해야할까 or 나만의 고민

배열을 사용해야 하는 이유는 index를 통한 데이터 접근속도가 매우 빠르다 ( O(1) )

연결리스트를 사용해야 하는 이유는 데이터 삽입 삭제 속도가 매우 빠르다 ( O(1) )