[Algorithm] 연결 리스트 값 제거 하기( LinkedList ) [3/3] _자료구조(DataStructure_Swift)

연결 리스트 값 제거 하기( LinkedList ) [3/3]

 

연결 리스트 제거 종류?

1. Pop : 연결리스트의 맨 앞의 노드를 제거
2. RemoveLast : 연결리스트의 맨 뒤의 노드 제거
3. Remove(at:) : 연결리스트의 특정 노드를 제거

---

• Pop 구현 -> pop() 리스트의 맨 앞의 노드를 제거함

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

• 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 구현 : 마지막 노드 제거 하기
  : 마지막 노드는 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 ()하든 똑같다.
        }
        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 // 탐색했던 마지막 노드를 제거한 것이니 반환.
    }

• Pop 실행

  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:) 구현 -> 특정 노드를 매개변수에 넣으면 그 노드의 다음 노드를 삭제 하는 것.

    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!))
  }

• 결과

전체 코드

LinkedList.zip

0.01MB

---

출처 : 스위프트 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: ): #swift :: 씩이 머릿속