Algorithm - 단일 연결 리스트(Single Linked List), 이중 연결 리스트(Doubly Linked List)

안녕하세요. Diana 입니다.

요즘 회사가 바빠서 야근을 하다보니 자꾸 할일이 밀려서 걱정입니다...

알고리즘도 문제만 풀지 정리가 계속 밀리네요.🥲

(그래도 해야지 어쩌겠어)

 

아무튼! 오늘은 단일 연결 리스트(Single Linked List)와 이중 연결 리스트(Doubly Linked List)에 대해 알아보려고 합니다.

 

 

바로 시작할게요~

 

 

---

 

✅ 배열(Array)

Linked List에 대해 알아보기 전 유사한 개념인 배열에 대해 간단하게 알아보려고 합니다.

 

배열은 동일한 타입의 데이터들의 묶음으로 Index를 통한 데이터의 접근이 가능합니다.

탐색에서의 시간 복잡도는 O(1)으로 굉장히 유용하죠.

 

하지만 배열 내부에서 맨 마지막의 데이터가 아닌 중간 데이터를 삭제 또는 삽입하는 경우 비워진 인덱스 또는 채워진 인덱스를 기점으로 재배치의 과정이 필요하다는 점에서 시간 복잡도는 O(N)의 특징을 가지고 있습니다.

 

✅ 노드(Node)란?

Linked List에 대해 공부하기 위해서는 노드의 개념에 대해 알고 있어야 합니다.

노드는 Linked List를 구성하는 데이터로 아래와 같은 형태를 띄고 있습니다.

(단일 연결 리스트인 경우)

 

노드에는 실질적인 데이터와 내 앞(Prev) 또는 뒤(Next) 데이터의 주소값이 포함되어 있습니다.

Swift의 경우 Node를 코드로 나타내면 아래와 같습니다.

 

class Node<T>{
    var next: Node?
    var data: T 

    init(data: T){
        self.data = data
    }
}

 

 

 

그럼 이제 Linked List에 대해 알아봅시다.

 

 

Linked List는 서로 연결된 노드들로 이루어진 데이터 묶음입니다.

데이터들음 연속되지 않아도 되며 리스트 맨 앞의 노드를 Head, 맨 뒤의 노드를 Tail이라고 부릅니다.

 

 

Linked List의 데이터인 노드는 다른 노드에 대한 주소 값을 가지고 있다고 했습니다.

이렇게 노드는 주소 값을 통해 다른 노드와 연결되어 List 를 형성하게 되는데 이 연결이 단방향으로 되어있느냐, 또는 양방향으로 되어있느냐에 따라 단방향 연결 리스트(Singly Linked List)와 양방향 연결 리스트(Doubly Linked List)로 구분됩니다.

 

 

✅ 단방향 연결 리스트(Singly Linked List)

 

단방향 연결 리스트는 각각의 노드들이 한 방향으로만 연결된 링크드 리스트를 말합니다.

말그대로 단방향으로만 연결된 탓에 앞의 노드는 뒤의 노드로 회귀할 수 없고 따라서 Garbage collector가 없는 스위프트에서는 Head 를 nil 처리 해버리면 한번에 링크드 리스트를 해제할 수 있습니다.

 

너무 급하게 시작해버렸는데 단방향 링크드 리스트를 그림으로 표현하면 아래와 같습니다.

 

 

위와 같이 노드는 데이터와 Next(다음 노드 주소값)으로 구성되어 있습니다.

 

이런 단방향 연결 리스트에서 특정 위치의 값을 탐색하기 위해서는 처음부터 N번째까지의 데이터를 하나씩 타고가며 확인해야 하기 때문에 O(N)의 시간복잡도를 갖습니다.

 

 

그럼 삽입과 삭제의 시간복잡도는 어떨까요?

삽입의 경우 단일 연결 리스트는 O(1)의 시간복잡도를 갖습니다.

Next의 연결고리만 해당 노드로 변경해주면 되니까요.

 

 

하지만 삭제에 있어서는 단일 연결 리스트는 그닥 효율적이지 못합니다.

삭제를 했을 때 빈 자리의 앞과 뒤를 연결해주어야 하는데 노드는 다음 노드만을 가리키고 있기 때문에 앞의 연결을 변경해주기 위해서는 HEAD부터 다시 타고와야하기 때문입니다.

결국 시간복잡도가 O(N)이 되죠.

 

 

단방향 연결 리스트를 Swift 코드로 구현하면 아래와 같습니다.

 

 

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

struct SinglyLinkedList {
    private(set) var head: Node<T>?
    private(set) var tail: Node<T>?
    private(set) var size: Int = 0
    
    mutating func push_front(value: T) {
        let newNode = Node(data: value)
        
        if size == 0 {
            head = newNode
            tail = head
        } else {
        	head.next = head
            head = newNode
        }
        
        size += 1
    }
    
    mutating func push_back(value: T) {
        let newNode = Node(data: value)
        
        if size == 0 {
            head = newNode
            tail = head
        } else {
            tail?.next = newNode
            tail = newNode
        }
        
        size += 1
    }
    
    mutating func pop_front() -> T? {
        let result = head?.data
        
        if size == 0 { return nil }
        
        if size == 1 {
            head = nil
            tail = nil
        } else {
            head = head?.next
        }
        
        size -= 1
        
        return result
    }
    
    mutating func pop_back() -> T? {
        let result = tail?.data
        
        if size == 0 { return nil }
        
        if size == 1 {
            head = nil
            tail = nil
        } else {
            //맨 뒤 노드를 탐색한 뒤 해당 노드를 tail로 변경
        }
        size -= 1
        
        return result
    }
    
    func empty() -> Bool {
        return size == 0
    }
    
    mutating func front() -> T? {
        if size == 0 { return nil }
        
        return head?.data
    }
    
    func back() -> T? {
        if size == 0 { return nil }
        
        return tail?.data
    }
}

 

 

✅ 양방향 연결 리스트(Doubly Linked List)

 

그럼 이번엔 양방향 연결 리스트에 대해 알아보도록 하겠습니다.

양방향 연결 리스트의 노드는 말그대로 양방향 연결을 위해 데이터와 Prev(이전 노드 주소값), Next(다음 노드 주소값)으로 구성되어 있습니다.

그림으로 표현하면 아래와 같죠.

 

단방향 연결 리스트와 달리 양방향 연결 리스트는 앞뒤의 노드와 연결되어 있기 때문에 이전 노드로의 회귀가 가능합니다.

 

 

아무튼 양방향 연걸 리스트에서의 시간복잡도를 알아보면 탐색에 있어서는 양방향 연결 리스트 또한 처음부터 N개의 노드를 훝어야하기 때문에 O(N)의 시간복잡도를 갖습니다.

 

 

그리고 삽입, 삭제의 경우 해당 위치의 노드의 연결을 끊어야한다는 특징이 있는데 단방향과 달리 양방향은 앞뒤의 노드와 전부 연결되어있기 때문에 삭제의 경우 해당 위치의 노드를 탐색할 필요 없이 바로 재설정이 가능하므로 O(1)의 시간복잡도를 갖게 됩니다.

 

 

Swift에서 양방향 링크드 리스트를 구현하면 아래와 같이 됩니다.

 

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

struct DoublyLinkedList {
    private(set) var head: Node<T>?
    private(set) var tail: Node<T>?
    private(set) var size: Int = 0
    
    mutating func push_front(value: T) {
        let newNode = Node(data: value)
        
        if size == 0 {
            head = newNode
            tail = head
        } else {
            head?.prev = newNode
            head = newNode
        }
        
        size += 1
    }
    
    mutating func push_back(value: T) {
        let newNode = Node(data: value)
        
        if size == 0 {
            head = newNode
            tail = head
        } else {
            tail?.next = newNode
            tail = newNode
        }
        
        size += 1
    }
    
    mutating func pop_front() -> T? {
        let result = head?.data
        
        if size == 0 { return nil }
        
        if size == 1 {
            head = nil
            tail = nil
        } else {
            head = head?.next
        }
        
        size -= 1
        
        return result
    }
    
    mutating func pop_back() -> T? {
        let result = tail?.data
        
        if size == 0 { return nil }
        
        if size == 1 {
            head = nil
            tail = nil
        } else {
            tail = tail?.prev
        }
        size -= 1
        
        return result
    }
    
    func empty() -> Bool {
        return size == 0
    }
    
    mutating func front() -> T? {
        if size == 0 { return nil }
        
        return head?.data
    }
    
    func back() -> T? {
        if size == 0 { return nil }
        
        return tail?.data
    }
}

 

오늘은 이렇게 단방향 그리고 양방향 연결 리스트에 대해 알아보았습니다.