[자료구조] 연결 리스트 (양방향)

단방향 연결 리스트의 경우 아래와 같이 원하는 데이터를 찾고 싶으면 head부터 순회해야 하므로 만약 찾고자 하는 데이터가 마지막에 있다면 모든 연결 리스트를 순회해야 하는 단점이 있다. (마지막 노드가 무엇인지 모르기 때문에)

 

이를 보완한 것이 양방향 리스트이다.

 

양방향 연결 리스트

가장 첫 노드를 가리키는 head와 가장 마지막 노드를 가리키는 tail을 두고 하나의 노드에 대해서 이전 노드와 다음 노드를 모두 연결해서 양방향으로 탐색이 가능한 것이 양방향 연결 리스트이다.

 

그러므로 위의 단방향의 경우 마지막 노드와 가까운 데이터를 찾는 경우 head부터 하나씩 순회해야 하는 단점이 있었지만,

양방향의 경우 찾고자하는 데이터가 연결 리스트의 마지막 노드와 가깝다면 tail을 이용해서 찾으면 되고 찾고자 하는 데이터가 연결 리스트의 처음과 가깝다면 head를 이용해서 찾으면 된다.

 

구조

 

양방향 연결 리스트의 노드 

prev

data

next

 

위의 모습에서 볼 수 있는 것처럼 이전 노드와 다음 노드를 모두 저장해야 하므로

• prev : 이전 노드의 주소값을 저장하는 것
• data : 데이터를 저장하는 것
• next : 다음 노드의 주소값을 저장하는 것

 

구현

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

단방향과 비슷하지만 이전의 노드를 가리킬 수 있기 때문에 prev를 추가한다.

 

// 노드 간의 데이터를 비교할 수 있어야 하므로 Equatable 프로토콜을 채택한다.
class DoublyLinkedList<T: Equatable> {
    
}

양방향 연결 리스트 클래스는 위와 같이 만들 수 있다.

 

1. head 노드와 tail 노드

양방향 연결 리스트의 경우 가장 처음 노드인 head 뿐 아니라 tail도 갖고 있기 때문에 head/tail을 만들 수 있다.

 

class DoublyLinkedList<T: Equatable> {
    private var head: Node<T>?
    private var tail: Node<T>?
}

 

2. append(data:) 연결 리스트 마지막에 노드 추가하기

단방향 연결 리스트의 경우 head부터 순회하여 node.next가 nil인 노드를 찾아, 추가를 해야했다.

그러나 양방향 연결 리스트의 경우 tail이라는 마지막 노드를 알고 있기 때문에 처음부터 순회하는 과정이 필요없다.

 

func append(data: T) {
	// head 또는 tail이 없다면 새로운 노드를 만들어서 head이자 tail 노드로 지정 (노드가 하나이므로)
    if head == nil || tail == nil {
        head = Node.init(data: data)
        tail = head
        return
    }
    
    // 새로운 노드를 만들고 
    let newNode = Node.init(data: data)
    // 기존의 마지막 노드의 next가 새로운 노드를 가리키고 
    tail?.next = newNode
    // 새로운 노드의 prev가 기존의 마지막 노드를 가리키고 
    newNode.prev = tail
    // 마지막 노드를 새로 지정한다.
    tail = newNode
}

 

3. removeLast 연결 리스트의 가장 마지막 노드 삭제하기 

삭제할 노드의 바로 이전 노드의 next를 nil로 바꿔서 tail의 위치를 바꾸면 된다.

func removeLast(data: T) {
    // head 또는 tail이 없는 경우
    if head == nil || tail == nil {
        return
    }
    
    // head를 삭제하는 경우(연결 리스트에 노드가 1개밖에 없는 경우)
    if head?.next == nil {
        head = nil
        tail = nil
        return
    }
    
    // 마지막 노드의 앞 노드의 next를 nil로 설정하고
    tail?.prev?.next = tail?.next
    // 그 노드(앞 노드)를 tail로 설정한다. 
    tail = tail?.prev
}

 

🟢 양방향 리스트의 장점 

양방향 리스트의 장점은 탐색이 head/tail 두 방향에서 가능하다는 것이다.

 

4. 탐색 

4-1. searchNode(from:) data로 head에서부터 노드 찾기 

특정 데이터가 연결 리스트의 앞 쪽에 위치할 경우에 사용하면 된다.

func searchNode(from data: T?) -> Node<T>? {
    
    if head == nil || tail == nil { return nil }
    
    var node = head
    while node?.next != nil {
        if node?.data == data { break }
        node = node?.next
    }
    
    return node
}

-> 단방향 연결 리스트와 동일하다.

 

4-2. searchNodeFromTail(from:) data로 tail에서부터 노드 찾기 

특정 데이터가 연결 리스트의 뒤 쪽에 위치할 때 사용하면 된다. 

 

위의 head를 찾는 코드와 거의 유사하고 몇가지 부분만 조금 다른데,

✔️ 탐색의 시작점이 tail이라는 것과

✔️ next가 아닌 prev로 head에서 찾는 것과는 반대로 거꾸로 가면서 찾아야 한다는 것이다.

 

func searchNodeFromTail(from data: T?) -> Node<T>? {
    if head == nil || tail == nil { return }
    
    var node = tail
    while node?.prev != nil {
        if node?.data == data { break }
        node = node?.prev
    }
    
    return node
}