[Data Structure / Algorithms] Doubly Linked List

전성훈·2023년 10월 31일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

4/35

주제: 이중 연결 리스트

Doubly Linked List

Doubly Linked List의 핵심은 노드와 노드가 서로 연결되어 있다는 점입니다. 아래 그림을 보면 단순 연결 리스트와는 다르게 이전 노드와 다음 노드로 구성되어 있습니다.
이것의 가장 큰 장점은 양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능하다는 것입니다.

장점

양방향 탐색의 가장 큰 장점은 특정 인덱스 위치의 엘리먼트를 가져올 때마다 반복자를 이용해서 탐색할 때 드러납니다.

인덱스의 데이터 가져오기

아래 그림을 보면 아시겠지만 노드가 6개일 때 3번째 엘리먼트 이전은 처음부터 시작해서 next를 이용해서 탐색하고, 4번째 이후의 엘리먼트는 마지막 노드부터 previous를 이용해서 조회합니다. 단순 연결 리스트가 최악의 경우 노드 전체를 탐색해야 했던 것에 비해서 양방향 연결 리스트는 탐색해야하는 엘리먼트가 반으로 줄어 듭니다.

노드 탐색하기

단방향 연결 리스트는 다음 노드의 탐색만 가능했던 것에 비해서 이중 연결 리스트의 경우 앞뒤로 탐색이 가능합니다. 상황에 따라 탐색의 방향이 바뀌어야 하는 경우라면 이중 연결 리스트를 사용합니다.

단점

단점도 있습니다. 우선 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 합니다. 메모리를 더 많이 사용한다는 의미입니다. 또 구현이 조금 더 복잡해진다는 단점도 있습니다. 하지만 장점이 크기 때문에 현실에서 사용하는 연결 리스트는 대부분 이중 연결 리스트입니다.

코드

노드 만들기

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

extension Node: CustomStringConvertible { 
	public var description: String { 
		String(describing: value)
	}
}

이중 연결 리스트 구현하기

public class DoublyLinkedList<T> { 
	private var head: Node<T>? 
	private var tail: Node<T>?
	
	public init() { }
	
	public var isEmpty: Bool { 
		head == nil
	}
	
	public var first: Node<T>? { 
		head
	}
	
	public func node(at index: Int) -> Node<T>? { 
		var currentIndex = 0
		var currentNode = head
		
		while currentNode != nil && currentIndex < index { 
			currentNode = currentNode!.next
			currentIndex += 1 
		}
		return currentNode
	}
	
	public func push(_ value: T) { 
		let newNode = Node(value: value) 
		
		guard tail != nil else { 
			haed = newNode
			tail = newNode
			return 
		}
		
		newNode.next = head 
		head?.prev = newNode
		head = newNode
	}
	
	public func append(_ value: T) { 
		let newNode = Node(value: value)
		
		guard let tailNode = tail else { 
			push(value)
			return
		}
		
		newNode.prev = tailNode
		tailNode.next = newNode
		tail = newNode
	}
	
	public func insert(_ value: T, after node: Node<T>)  { 
		let newNode = Node(value: value, next: node.next, prev: node)
		
		node.next?.prev = newNode
		node.next = newNode
	}
	
	public func removeFirst() -> T? { 
		if isEmpty { 
			return nil
		}
		
		let nextNode = head?.next
		
		defer { 
			nextNode?.prev = nil
			head?.next = nil
			head = nextNode
		}
		
		return head!.value
	}
	
	public func removeLast() -> T? { 
		if isEmpty { 
			return nil
		}
		
		let prevNode = tail?.prev
		
		defer { 
			prevNode?.next = nil 
			tail?.prev = nil 
			tail = prevNode
		}
		
		return tail!.value 
	}
	public func remove(_ node: Node<T>) -> T { 
		let prev = node.prev 
		let next = node.next
		
		if let prev = prev { 
			prev.next = next 
		}  else { 
			head = next 
		}
		
		next?.prev = prev 
		
		if next == nil { 
			tail = prev
		}
		
		node.prev = nil 
		node.next = nil
		
		return node.value
	}
}

extension DoublyLinkedList: CustomStringConvertible {
    public var description: String {
        var string = ""
        var current = head
        while let node = current {
            string.append("\(node.value) -> ")
            current = node.next
        }
        return string + "end!"
    }
}

extension DoublyLinkedList: Collection {
    public struct Index: Comparable {
        public var node: Node<T>?
        
        public static func == (lhs: Index, rhs: Index) -> Bool {
            switch (lhs.node, rhs.node) {
            case let (left?, right?) :
                return left.next === right.next
            case (nil,nil):
                return true
            default:
                return false
            }
        }
        
        public static func < (lhs: Index, rhs: Index) -> Bool {
            guard lhs != rhs else { return false }
            let nodes = sequence(first: lhs.node) { $0?.next }
            return nodes.contains { $0 === rhs.node }
        }
    }
    
    public var startIndex: Index {
        Index(node: head)
    }
    
    public var endIndex: Index {
        Index(node: tail?.next)
    }
    
    public func index(after i: Index) -> Index {
        Index(node: i.node?.next)
    }
    
    public subscript(position: Index) -> T {
        position.node!.value
    }
}

var doubly = DoublyLinkedList<Int>() // end!
doubly.removeFirst()  // nil 
doubly.append(5) // 5 -> end! 
doubly.append(3) // 5 -> 3 -> end! 
doubly.append(2) // 5 -> 3 -> 2-> end!
doubly.removeFirst() // 5
doubly //  3 -> 2-> end!
doubly.insert(1, after: doubly.node(at: 0)!) // 3 -> 1 -> 2 -> end!
doubly.append(6) // 3 -> 1 -> 2 -> 6 -> end!
doubly.removeLast() // 6
doubly // 3 -> 1 -> 2 -> end!
doubly.remove(doubly.node(at: 2)!) // 2 
doubly // 3 -> 1 -> end!
doubly.count // 2