스위프트 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: ): #swift

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

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

같은 분야를 공부하는 분들에게 조금이라도 도움이 됬으면 좋겠습니다.

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

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

---

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

• 씩이 Github

( 제 깃허브에 iOS, Swift 관련 정보들 정리되어 있습니다!!    )

• 스위프트로 구현한 자료구조 : 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: #쌓기
  
  
  

• 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 : #메모리 누수

연결리스트에 값 제거하기 (3 / 3)

• 어떤 종류가 있어?   
• pop : 연결리스트의 맨 앞의 노드를 제거합니다.
• removeLast : 연결리스트의 맨 뒤의 노드를 제거합니다.
• remove(at: ) : 연결리스트의 특정 노드를 제거합니다.

• pop 구현
• pop() : 리스트의 맨 앞의 노드를 제거함.

public mutating func pop() -> Value? { // 제거할 맨 앞의 노드 반환하고, 그 노드 없애서 제거 구현!
        defer{ // 삭제하기 전에, 데이터가 남아있을 때 삭제할 노드 반환해줘야 겠죠? 그러므로 defer 
               // 노파심에.. defer 는 함수에서 제일 나중에 실행되게 만드는 키워드 입니다.
            head = head?.next 
            // 현재의 head 를 제거할 목적이니까 현재의 head 에 다음 노드를 넣어줍니다. head 를 옮기는 과정인 것이죠.
            // 헤드 노드는 모든 참조가 떨어지므로 ARC 에 의해 참조 해제된다.
            // 스위프트는 메모리를 헤제하는 과정을 자동으로 해줍니다 . 그것이 Automatic Reference Counting 임
            if isEmpty { 
                tail = nil // 모두 제거 했다면 tail 도 메모리 필요 없으니 nil 할당해서 비워줍니다.
            }
        }
        return head?.value // 여기서 반환하는 값은 삭제되기 전 헤드노드의 값. defer 가 맨 나중에 실행하므로.
}

( ARC (Automatic Reference Counting ) 은 자동으로 사용하지 않는 참조들을 스위프트가 메모리 해제하는 기능입니다. 이 개념을 모르면 메모리가 연관이 깊은 자료구조와 알고리즘을 이해하기 어렵습니다. ARC 는 여기에서 먼저 학습 하고 오세요! )

• pop 실행

example(of: "pop") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)// 1, 2, 3 인 연결리스트
    
    print("pop 전 리스트 \(list)")
    let poppedValue = list.pop() 
    // 제거할 값 반환받은거 poppedValue 에 먼저 저장한 후, 노드 제거를 수행합니다. (defer 썻었죠?)
    print("pop 된 value = \(poppedValue)")
    print("pop 후 리스트 \(list)")
}

• 결과

• removeLast 구현
• removeLast() : 마지막 노드를 제거하기
• 이 부분에는 마지막 노드는 tail 노드로 알 수 있지만, 제거하고 난 후의 tail 노드를 설정할, 그 전의 노드를 모르기 때문에 탐색 실행할 예정.

public mutating func removeLast() -> Value? { 
        guard let head = head else { 
            // 현재 연결리스트의 head 가 nil 인지 확인 : 빈 리스트 인지 확인하는 것,.
            return nil // 빈 리스트면 nil 반환
        }
        guard head.next != nil else {// 노드가 하나 뿐이라면 
            return pop() // 마지막 노드를 제거하든, pop() 하든 똑같쥬? pop() 으로 실행함.
        }
        var prev = head // 마지막 노드의 이전노드를 찾아야 해! 그 이전노드를 prev 라고 하자!
        var current = head // 탐색 시작할 현재노드.
        
        while let next = current.next { // 현재 노드의 다음 노드가 nil 이 아니면 계속 반복.
        // 반복이 나오면 성능이 저하됨이 예상되죠? 한번 반복할 때마다 실행 시간이 오래 걸린답니다!
        // insert 에서 특정 노드 찾을 때도 반복이 나와서 실행시간이 상대적으로 오래 걸립니다.
            prev = current
            current = next // 마지막 반복에서 current 는 제일 마지막 노드가 되겠쥬? 그럼 prev 는 이전노드.
        }
        prev.next = nil // 마지막 노드의 이전 노드가 마지막이 되도록 next 에 nil 할당.
        tail = prev // 현재 연결리스트 인스턴스의 tail 이 그 이전노드로 변화되죠?
        return current.value // 탐색했던 마지막 노드를 제거한 것이니 반환.
}

• removeLast 실행

example(of: "removing the last node") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1) // 1, 2, 3 연결리스트
    
    print("Before removing last node: \(list)")
    let removedValue = list.removeLast() // 제거한 노드 출력하기 위해.
    print("after removing last node: \(list)")
    print("Removed value \(removedValue!) " )
}

• 결과

• remove(after: ) 구현
• remove(after: ) : 특정 노드를 매개변수에 넣으면 그 노드의 다음 노드를 삭제하는 것.

public mutating func remove(after node: Node<Value>) -> Value? {
        // 매개변수에는 내 맘대로 특정 리스트의 특정 노드를 넣으면 된다.
        // insert 할 때 특정 인덱스의 노드 반환받는 메소드를 사용하면 되겠쥬?
        defer { // 제거할 값 먼저 반환하고 제거 수행하려고 defer 씁니다.
            if node.next === tail { // node 가 tail 의 이전 노드이면.
                tail = node // tail 에 node 할당하면 그냥 끝나쥬?
            }
            node.next = node.next?.next 
            // 가운데 에 있는 노드 제거하려면. next 가 바뀌게 되쥬? 중간에 구멍 뚫리는 거니까요.
            // 마지막 노드의 이전노드라서 tail 을 변경해 주는 경우에도 next 에 nil 이 할당되니까. 문제없이 실행되쥬.
        }
        return node.next?.value
}

• remove 실행

example(of: "removing a node after a particular node") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1) // 1, 2, 3 인 연결리스트
    
    print("Before removing at particular index: \(list)")
    let node = list.node(at: 0) 
    // 인덱스가 0 인 노드 찾고 (첫 번째 노드) 
    // 정확히 말하면 인덱스가 0 인 노드의 인스턴스 메모리 주소를 알아내는 거쥬?
    let removedValue = list.remove(after: node!) // 제거한 값 출력할 예정이니 
    print("After removing at index \(0): \(list)")
    print("Removed value : " + String(describing: removedValue!))
}

• 결과

전체 소스 파일