[Swift:자료구조] LinkedList 2편 : LinkedList 에 노드 삭제하기

Newon·2022년 7월 7일

Pop linkedlist remove(after:)removeLast swift

스위프트 자료구조

목록 보기

3/3

LinkedList - 노드 삭제하기

노드 추가와 마찬가지로 3개의 방법으로 노드를 추가할 수 있습니다.

pop : 링크드리스트 내 가장 첫번째 노드를 삭제합니다.
removeLast: 링크드리스트 내 가장 마지막 노드를 삭제합니다.
remove(at:) : 특정 인덱스의 노드를 삭제합니다.

pop

struct LinkedList<T> {
	...
    mutating func pop() -> T? {
    	defer {
        	head = head?.next
            if isEmpty{
            	tail = nil
            }
        }
        return head?.value
    }
}
// 출력 예제
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("pop 이전의 링크드리스트 : \(list)")
let poppedValue = list.pop()
print("pop 이후의 링크드리스트 : \(list")
print("pop 한 값 : " + String(poppedValue))

// pop 이전의 링크드리스트 : 1 -> 2 -> 3
// pop 이후의 링크드리스트 : 2 -> 3
// pop 한 값 : Optional(1)

pop 는 링크드리스트의 head 를 삭제하고 리턴하며,
head.next 를 새로운 head 로 설정하는 메소드입니다.

이때 리턴되는 값은 nil 일 수 있기에 (비어있는 링크드리스트를 pop 하는 경우) optional 값으로 주어지게 됩니다.

TMI
특기할 점이 2가지 입니다.

첫번째로 defer 의 사용입니다. defer 키워드는 의도적으로 return 바로 전에 실행하도록, 실행 순서를 가장 뒤로 설정하는 키워드입니다.
만약 defer 키워드를 사용하지 않는다면,
기존의 값, 즉 삭제되는 값인 head?.value 를 담을 변수가 필요하게 됩니다. 하지만 defer 를 통해서 return 이후에 head = head?.next 를 할당하므로 오직 리턴만을 위해 새로운 변수를 인스턴스할 필요가 없어지게 됩니다.
* 리턴 뒤에 어떻게 함수가 작동하냐구요 ?
이렇다고 하네요. 감사합니다 :)

두번째는 메모리 정리에 관한 내용입니다.
pop 메소드를 자세히보면 기존의 head Node 에 대해서는 nil 을 선언도 안하고, 바로 함수를 빠져나가는 것을 확인할 수 있습니다.
그러면 메모리는 계속해서 예전 head Node 를 계속해서 갖고 있을까요?

Swift 의 ARC(Auto Reference Calculator) 는 특정 객체가 메모리를 참조하는지 확인해주는 기능이 있습니다. 이때 특정 객체를 그 누구도 참조하지 않는다면 자동으로 메모리를 정리해주게 됩니다.

head Node 의 경우가 이에 해당됩니다.
기존의 LinkedList struct 에서 head 변수를 head?.next 로 변경하게 되면, 기존의 head 는 그 누구도 참조하지 않게 됩니다. 곧 참조 카운트가 0 이 되며, 참조 카운트가 0 인 객체는 함수 종료 시 ARC 가 자동으로 정리해줍니다.

removeLast

removeLast 메소드는 tail 을 삭제하고, tail 앞의 노드를 tail 로 만드는 메소드입니다. 말로는 간단하지만, 사실 여기에는 맹점이 하나 있습니다.

Node 에는 next 만 있고, prev(이전) 가 없기때문에 무슨 노드가 tail 의 앞의 노드인지 알 수 없습니다. 즉, 링크드리스트를 처음부터 끝까지 돌면서 tail 의 앞 노드가 어떤 노드인지 알아내야 합니다.

struct LinkedList<T> {
	...
    mutating func removeLast() -> T? {
    	guard let head = head else {
        	return nil   // 1️⃣
        }
        
        guard head.next != nil else {
        	return pop() // 2️⃣
        }
        
        // 3️⃣
        var prev = head
        var current = head
        
        while let next = current.next {
        	prev = current
            current = next
        }
        
        // 4️⃣
        prev.next = nil
        tail = prev
        return current.value
    }
}

// 출력 예제
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("removeLast 이전 링크드리스트 : \(list)")

let removedValue = list.removeLast()
print("removeLast 이후 링크드리스트 : \(list)")
print("removeLast 값 : " + String(removedValue)

// removeLast 이전 링크드리스트 : 1 -> 2 -> 3
// removeLast 이후 링크드리스트 : 1 -> 2
// removeLast 값 : optional(3)

만약 head 가 nil 이였다면, nil 을 리턴해줍니다.
만약 head 의 next 가 없다면, 즉 head == tail 인 상황이라면 pop 과 동일하므로 pop 을 리턴합니다.
위의 두 상황이 아니라면, tail 이전의 노드가 어떤 노드인지 찾기 위해 while 로 탐색합니다.
tail 이전의 노드를 찾았다면 해당 노드의 next 를 없애고, tail 을 해당 노드로 바꾼 후 이전 tail 을 리턴합니다.

remove(after:)

remove(after:) 메소드는 특정 노드의 next 를 삭제하는 메소드입니다. 이때 next 의 next 를 특정 노드와 연결해주게 됩니다.
굳이

링크드리스트가 1 -> 2 -> 3 이였지만,
remove(after:1) 을 통해 1 -> 3 으로 바꾼 모습입니다.
물론 연결 안해줄 수도 있습니다.

struct LinkedList<T> {
	...
    mutating func remove(after node: Node<T>) -> T? {
    	defer {
        	if node.next === tail {
            	tail = node
            }
            node.next = node.next?.next // ⭐️
        }
        return node.next?.value
    }    
}

// 출력 예제
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("remove(after:0) 이전 링크드리스트 : \(list)")
let removedValue remove(after: node)

print("remove(after:0)" 이후 링크드리스트 : \(list)")
print("삭제된 노드값 : " + String(removedValue))
// remove(after:0) 이전 링크드리스트 : 1 -> 2 -> 3
// remove(after:0)" 이후 링크드리스트 : 1 -> 3
// "삭제된 노드값 : Optional(2)"