[스위프트 : 자료구조] 큐 (2 / 4): Queue: #연결리스트: #더블연결리스트: #DoublyLinkedList

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

Doubly LinkedList 를 이용한 큐 구현

• 구성
• Queue 에서는 4가지 다른 특성의 큐를 구현할 예정입니다. 다룰 것들은 다음과 같습니다.
• Queue 프로토콜 구현 (1 / 4)
• 아래 4 가지 큐를 구현할 때 Queue 프로토콜을 채택해서 구현하려고 이 프로토콜을 정의합니다.
• Array 를 사용해서 큐 구현. (1 / 4)
• Doubly Linked List  이용해서 큐 구현. (2 / 4)
• doubly linked list 구현 (2 / 4)
• Two Stack 을 이용해서 큐 구현.(3 / 4)
• Ring Buffer 를 이용해서 큐 구현. (4 / 4)
• 이렇게 여러가지 방법으로 큐를 구현하는 이유는 성능차이 ( Performance )  가 있기 때문입니다.
• '성능을 조금 씩 개선하면서 똑같은 큐를 빠르고 효율적으로 만들어 보자는 것'이 4가지 큐를 구현하는 목적 입니다.

• 구현 ( QueueLinkedList, DoublyLinkedList )
• QueueLinkedList 먼저 구현 하고 DoublyLinkedList 내부를 살펴볼 예정입니다.

public class QueueLinkedList<T>: Queue {
    private var list = DoublyLinkedList<T>() 
    // Doubly 연결리스트의 인스턴스 생성하기!
    public init() {}
}

• QueueLinkedList 에 DoublyLinkedList 의 인스턴스를 먼저 생성하고 시작하기 때문에 ( 연결리스트로 큐를 구현할 것이니까요! ) 더블 연결리스트의 특징만 먼저 보고 갑니다!
• 더블 연결리스트 ( Doubly LinkedList )
• 연결리스트의 확장된 개념입니다.
• 연결리스트는 자기 자신의 노드의 값과 다음 노드를 가리키는 '참조정보' 로 구성되지만 여기서 더 나아가서 현재노드가 다음노드의 '참조정보' 뿐만 아니라 이전노드의 '참조정보'도 가지고 있는 것이 더블 연결리스트 입니다.
• 연결리스트의 개념이 없다면 연결리스트 에서 먼저 학습하시고 오시거나 , 이 장을 그냥 넘어가세요^^.

• QueueLinkedList 이어서!

 
public class QueueLinkedList<T>: Queue {
    private var list = DoublyLinkedList<T>() // 연결리스트 인스턴스 생성
    public init() {}
    
    //MARK: - Comform to Queue protocol
    public func enQueue(_ element: T) -> Bool { // 큐에 값 추가하기.
        list.append(element) // 연결리스트의 append 메소드로 큐에 값을 추가합니다.
        return true
    }
    public func deQueue() -> T? { // 큐애 값 제거하기.
        guard !list.isEmpty, let element = list.first else {
            // 연결리스트 비어있지 않고
            // 연결리스트의 first 프로퍼티는 옵셔널로 선언되었으므로 바인딩으로 해제시킵니다.
            return nil
        }
        return list.remove(element) // 연결리스트의 remove 메소드로 첫 번째 값을 제거시킵니다.
    }
    
    public var peek: T? { // 큐의 가장 앞의 값을 반환해서 얻습니다.
        return list.first?.value
    }
    
    public var isEmpty: Bool{ // 연결리스트의 isEmpty 를 읽습니다.
        return list.isEmpty
    }
}
 
extension QueueLinkedList: CustomStringConvertible {
    public var description: String {
        return String(describing: list)
    }
}
 

• 배열로 구현한 큐랑 비슷하죠? 큐를 단지 연결리스트로 구현한 것 뿐입니다.
• 그러므로 연결리스트의 메소드와 프로퍼티들을 활용하면 간단하게 구현할 수 있습니다.

• 실행

• 결과
• 연결리스트 처럼 "->" 로 이어지죠? 이것은 DoublyLinkedList 에서 CustomStringConvertible 프로토콜을 활용해서 따로 설정해 주어서 가능한 것!

• 성능 (Performance)

• ArrayQueue 와 비교했을 때
• 장점
• 이제 deQueue 메소드의 수행속도가 O(1) 로 빠릅니다. ( ArrayQueue 는 Q(n)임. )
• 이는 연결리스트의 특징인 아이템이 제거되도 나머지 요소들이 재정렬하지 않아도 되기 때문입니다.
• 단점
• 연결리스트를 추가할 때 수행하는 동적할당이 상대적으로 큰 메모리를 소모합니다.
• 값, 이전노드 참조, 다음노드 참조 이렇게 3개를 포함하기 때문입니다.

• 이제 이 모든것을 가능하게 해주는 Doubly LinkedList 의 내부를 볼까요?
• 더블 연결리스트 ( DoublyLinkedList )
• 위에서 사용했던 DoublyLinkedList 를 소스코드로 설명하겠습니다.
• 연결리스트에서 설명한 부분은 생략하므로 연결리스트를 꼭 먼저 보고 오시기 바랍니다~

public class Node<T> { // 연결리스트가 가지는 기본적인 노드 클래스 입니다.
    
    public var value: T // 값
    public var next: Node<T>? // 다음 노드 참조
    public var previous: Node<T>? // 이전 노드 참조 : 여기가 단순연결리스트와 차이.
    
    public init(value: T) {
        self.value = value
    }
}
 
extension Node: CustomStringConvertible {
    
    public var description: String {
        return String(describing: value)
    }
}
 
public class DoublyLinkedList<T> { // 더블연결리스트 클래스
    
    private var head: Node<T>? // 헤드 노드
    private var tail: Node<T>? // 테일 노드
    
    public init() { }
    
    public var isEmpty: Bool { // 헤드노드가 비었으면 연결리스트가 비어있는 거쥬?
        return head == nil
    }
    
    public var first: Node<T>? { 
        // head 노드는 항상 가장 앞에 있으므로 first 프로퍼티로 설정하면 됩니다.
        // 옵셔널임을 유의 (리스트가 비어있으면 nil 이니까요^^)
        return head
    }
    
    public func append(_ value: T) {
        let newNode = Node(value: value) // 새로 들어올 노드 초기화하고 newNode 에 저장.
        
        guard let tailNode = tail else { // tail 이 nil 인지 검사 = 리스트가 비어있는지 검사.
            head = newNode // 비어있으면 head, tail 모두 설정해줌.
            tail = newNode
            return
        }
        // 비어있지 않다면 실행.
        newNode.previous = tailNode // 새로 들어올 노드의 '이전 참조' 에 현재 tail 노드로.
        tailNode.next = newNode // 현재 tail 노드의 '다음 참조' 를 새로 들어올 노드로.
        tail = newNode // 연결정보 완료했으면 마지막으로 새로운 테일노드 설정해줌.
        // 정리하면 새로 들어올 노드를 들어올 당시의 'tail 노드' 와 연결을 서로 해주고 
        // 들어올 당시의 'tail 노드' 는 그 당시에는 마지막 노드지만 이제는 마지막 노드의 '이전노드' 가 되므로
        // 새로 들어온 노드가 진짜 'tail' 노드가 되는 것이쥬.
    }
    
    public func remove(_ node: Node<T>) -> T {
        let prev = node.previous // 제거할 노드의 이전참조
        let next = node.next // 제거할 노드의 다음참조
        
        if let prev = prev { // 가장 앞의 노드면 prev 가 nil 이쥬?
            prev.next = next 
            // 가장 앞의 노드가 아니면 제거되는 노드의 이전노드의 다음노드가 제거되는 노드의 다음노드가 되쥬?
        } else {
            head = next // 가장 앞의 노드면 head 노드 새로 설정, 제거되는 노드 다음노드가 새로운 head 노드 됨.
        }
        
        next?.previous = prev // 제거 하는 노드의 다음노드의 이전노드 참조가 제거하는 노드의 이전노드로 설정.
        
        if next == nil { // 제거하는 노드가 마지막 노드라면
            tail = prev // tail 노드 새로 설정해줌.
        }
        
        // 마지막에 할일을 다 한 참조정보들 메모리에서 없애기.
        node.previous = nil 
        node.next = nil
        
        return node.value
    }
}
 
extension DoublyLinkedList: CustomStringConvertible {
    
    public var description: String {
        var string = ""
        var current = head // head 노드에서 시작!
        while let node = current {
            string.append("\(node.value) -> ") 
            // 문자열 메소드인 append 사용해서 노드의 값을 연결리스트 처럼 -> 로 이어 붙인다.
            current = node.next
            // 다음 반복을 위해 current 가 next 가지게 하기.
        }
        return string + "end"  // 마지막에 end 를 붙여서 리스트의 끝이라는 것을 표현.
    }
}
 

• Swift4: 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음

전체 소스 파일