swift 자료구조 - 연결리스트 코드로 정리 - 2

swift 자료구조 - 연결리스트 코드로 정리 - 2

 

지난 포스팅에서 swift로 연결리스트를 구현하고 Node들을 추가하는 기능까지 구현을 했습니다.

Node들을 추가하는 함수에는 push, append, insert 를 각각 구현했죠.

 

push는 연결리스트에서 새 노드를 연결리스트 제일 앞에 추가하는 함수입니다.

append 는 연결 리스트에서 새 노드를 연결리스트 제일 뒤에 추가하는 함수 입니다.

insert는 연결 리스트에서 새 노드를 특정 위치에 삽입하는 함수입니다.

 

위의 내용인 swift 자료구조 - linkdedlist 연결리스트 코드로 정리 - 1 이 포스팅에 모두 자세히 적어 놓았습니다.

이 포스팅을 읽기전에 위의 포스팅을 먼저 읽고 오셔야 이해가 됩니다.

 

그럼 이번 포스팅에서는 swift로 연결 리스트의 노드들을 삭제하는 기능을 구현 해보도록 하겠습니다.

 

삭제 함수에는 3가지가 있습니다.

 

1.pop 함수 : 연결리스트의 제일 앞에 있는 노드의 값을 리턴 후 삭제 합니다.

2.removeLast 함수 : 연결 리스트의 제일 끝에 있는 값을 리턴후 제거 합니다.

3.remove(at:) : 특정 위치의 노드를 리턴 후 삭제 합니다.

 

먼저 pop 함수를 구현해보도록 하겠습니다.

 

✅ pop

pop 함수는 연결 리스트의 제일 앞에 있는 노드의 값을 리턴후 삭제하므로 먼저 제일 앞의 노드는 head가 가리키고 있습니다.

따라서 return은 head.value 라고 해주면 제일 앞의 노드의 값이 리턴이 됩니다. 그 후 함수가 종료될때 swift의 defer 함수를 이용해서 head를 기존 head의 next를 가리키도록 합니다. 그럼 기존의 head를 참조하는 곳이 없기 때문에 자동으로 nil이 됩니다. 또 연결 리스트가 비어 있을 수 있기 때문에 리턴 타입은 Value? 옵셔널 타입으로 지정해 놓았습니다.

 

    //MARK: 제일 앞 요소 삭제
    @discardableResult
    public mutating func pop() -> Value? {
        print("pop 함수 시작")
        //[2] 함수가 끝나고 head의 위치를 변경해 준다.
        defer {
            print("defer. head 위치 변경")
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        
        print("head.value : \(head?.value)")
        //[1]제일 첫번째 요소의 값을 리턴하고
        return head?.value
    }

 

✅ pop 테스트

연결 리스트에 숫자 3개를 넣고 (1->2->3)

pop함수를 1회 실행 했습니다.

함수의 결과 값으로 1이 리턴이 되고 연결 리스트는 2->3이 됩니다.

var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("list: \(list)")
let poppedValue = list.pop()
print("pop 함수 이후 list: \(list)")
print("리턴된 값 : " + String(describing: poppedValue)) 

/*
출력
list: 1 -> 2 -> 3  
pop 함수 시작
head.value : Optional(1)
defer. head 위치 변경
pop 함수 이후 list: 2 -> 3 
리턴된 값 : Optional(1)
*/

 

 

✅ removeLast

이어서 연결 리스트에서 제일 마지막에 있는 노드를 제거하는 함수를 구현해보도록 하겠습니다.

여기서 여러가지 조건이 있는데 

 

[1] head 가 비어 있으면 nil을 리턴하는 것입니다. head가 비어있다는 것은 삭제할 리스트가 없다는 뜻이기 때문입니다.

[2] head.next 가 nil 이면 pop 함수를 호출하는 것입니다. head의 next가 nil 이라는 뜻은 연결 리스트의 노드가 head 하나뿐인것을 의미하기 때문에 단순하게 연결 리스트의 제일 앞에 있는 노드를 반환 후 삭제하는 pop을 호출해도 되기 때문입니다.

 

위의 두 조건을 통과한 후에 제일 마지막에 있는 요소를 삭제하는 로직을 작성합니다.

먼저 연결 리스트는 배열과 다르게 제일 마지막에 있는 노드를 한번에 찾을 수 없습니다. 배열은 arr[length-1] 이런식으로 제일 마지막의 요소에 접근이 가능한데 연결 리스트는 node.next 를 이용해서 자신의 다음 노드를 찾고, 또 node.next를 이용해서 다음 노드를 찾고... 이런 식으로 node.next가 nil 이 나올때까지 찾은 다음 해당 노드를 리턴 후 삭제 합니다. 

 

    @discardableResult
    public mutating func removeLast() -> Value? {
        // 1.헤드가 비어 있는지 체크 합니다.
        guard let head = head else {
            return nil
        }
        // 2.헤드의 다음 노드가 있는지 체크 합니다.
        // 헤드의 다음 노드가 없으면 pop()으로 head만 제거합니다.
        guard head.next != nil else {
            return pop()
        }
        
        // 3.current.next가 nil이 될 때까지 다음 노드를 검색합니다.
        var prev = head
        var current = head
        
        while let next = current.next {
            //while 문 종료시 prev는 마지막노드 바로 이전노드가 할당되고
            prev = current
            //current는 마지막 노드가 할당됩니다.
            current = next
        }
        // 4.마지막 노드에 nil을 할당하고
        // 꼬리에는 마지막 노드 바로 이전 노드를 할당합니다.
        prev.next = nil
        tail = prev
        
        //current는 삭제된 제일 마지막 node이므로
        //제일 마지막 노드였던 값을 리턴해줍니다.
        return current.value
    }

 

✅ removeLast 테스트

숫자 3개로 (1 -> 2 -> 3) 연결 리스트를 만든 다음에 removeLast 함수를 이용해서 제일 마지막 노드를 삭제해 주었습니다.

 

var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("last node: \(list)")
let removedValue = list.removeLast()

print("마지막 노드 삭제후 : \(list)")
print("삭제된 노드: " + String(describing: removedValue))

 

✅ remove(at:) 

마지막으로 특정 위치의 노드를 리턴 후 삭제하는 함수를 알아보겠습니다. 

특정 위치의 노드를 삭제하려면 먼저 삭제할 노드(2)의 바로 앞에 있는 노드(1)을 찾습니다. 그리고 해당 노드(1)의 next(2)를 제거해주고, 해당 노드(1)의 next에 삭제된 노드의 next(3)를 할당해 줍니다.

 

 

먼저 아래 주석 //[1] 을 보면 인자로 들어온 노드의 next 의 value를 리턴합니다. 위의 예제에서는 인자로 들어온 노드가 값이 1인 노드가 되며, node의 next는 값이 2인 노드가 됩니다.

그리고 //[2] 에서 인자로 들어온 노드(1)의 next를 노드(1)의 다음(2), 다음(3) 과 연결해줍니다. 즉 값이 3인 노드와 연결이 됩니다.

 

    //MARK: 특정 위치 노드 제거
    @discardableResult
    public mutating func remove(after node: Node<Value>) -> Value? {
        defer {
            //[2] 타켓 노드의 next가 꼬리라면
            if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
        }
        
        //[1]타겟 노드의 next의 값을 리턴해줍니다.
        return node.next?.value
    }

 

✅ remove(at:)  테스트

참고로 삭제할 노드의 앞 노드를 찾는 함수 node는 이전 포스팅(swift 자료구조 - linkdedlist 연결리스트 코드로 정리 - 1 )에서 정리해 놓았습니다.

 

var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("list: \(list)")
let index = 1
let node = list.node(at: index - 1)!
let removedValue = list.remove(after: node)

print("삭제후 index, list :  \(index)번째 노드 삭제됨 : \(list)")
print("삭제된 value: " + String(describing: removedValue))

/*
출력
list: 1 -> 2 -> 3  
삭제후 index, list:  1번째 노드 삭제됨 : 1 -> 3 
삭제된 value: Optional(2)
*/

 

✅ 성능

제일 앞의 노드를 삭제하는 pop과 특정 위치의 노드를 제거하는 remove(after:) 함수는 O(1)의 속도로 처리가 되고 연결 리스트의 제일 마지막에 있는 노드를 삭제하는 함수인 removeLast 는 O(n) 만큼 시간이 걸린다고 볼 수 있습니다. 왜냐면 node 의 개수(n) 만큼 while문을 돌아야 하기 때문입니다.

 

 

LinkdedList.zip

0.04MB

 

 

 

참고

코딩퀴즈 - ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9%ED%80%B4%EC%A6%88/id1625309702

코딩퀴즈 - aos

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication

 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/