연결 리스트(Linked List)에서 요소를 제거하는 작업은 생각보다 간단합니다. 핵심은 제거하고 싶은 노드에 대한 참조(reference)를 끊어버리는 것입니다. 참조가 끊긴 노드는 더 이상 리스트에 접근할 수 없게 되어 자연스럽게 제거된 것과 같아집니다.
이중 연결 리스트에서 요소를 제거할 때는 다음의 세 가지 경우를 고려해야 합니다.
요소 제거의 3가지 경우
1. 헤드(Head)에서 제거
첫 번째 요소를 제거하는 경우입니다. head = head.next로 헤드 포인터를 다음 노드로 옮기고, 새로운 헤드가 된 노드의 prev 링크를 null로 설정하면 됩니다. 이렇게 하면 기존 첫 번째 노드에 대한 참조가 사라지고, 헤드는 두 번째 요소부터 시작하게 됩니다.
2. 테일(Tail)에서 제거
마지막 요소를 제거하는 경우입니다. 뒤에서 두 번째 노드의 next 값을 null로 설정하면 마지막 노드와의 연결이 끊어집니다. 그리고 tail 포인터를 새로운 마지막 노드(기존의 뒤에서 두 번째 노드)로 업데이트해 주어야 합니다.
3. 중간에서 제거
리스트 중간에 있는 요소를 제거하는 경우가 가장 까다롭습니다. 이때는 제거하려는 노드의 이전 노드가 제거하려는 노드의 다음 노드를 직접 가리키도록 연결을 재구성해야 합니다. 즉, prevNode.next = node.next와 node.next.prev = prevNode 두 줄의 코드로 앞뒤 노드를 서로 연결해 주면 해당 노드는 리스트에서 빠지게 됩니다.
다음 그림은 이 과정을 시각적으로 보여줍니다.
구현 예제
위 내용을 바탕으로 remove 메서드를 구현한 코드입니다. 위치 값(position)에 따라 헤드 제거, 테일 제거, 중간 제거를 분기 처리합니다.
remove(data, position = 0) {
if (this.length === 0) {
console.log("List is already empty");
return;
}
this.length--;
let currNode = this.head;
if (position <= 0) {
// 헤드 제거
this.head = this.head.next;
this.head.prev = null;
}
else if (position >= this.length - 1) {
// 테일 제거
this.tail = this.tail.prev;
this.tail.next = null;
}
else {
// 중간 제거
let iter = 0;
while (iter < position) {
currNode = currNode.next;
iter++;
}
currNode.next = currNode.next.next;
currNode.next.prev = currNode;
}
return currNode;
}실행 예시
실제로 동작을 확인해 보겠습니다. 리스트에 요소를 삽입한 후 특정 위치의 요소를 제거하고 결과를 출력합니다.
let list = new LinkedList(); list.insert(10); list.insert(20); list.insert(30); list.remove(1); list.display(); list.insert(15, 2); list.remove(); list.display();
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
20 <-> 30 <-> 30 <-> 15 <->
이처럼 이중 연결 리스트는 양방향 포인터(prev, next)를 모두 관리해야 한다는 점만 유의하면, 단일 연결 리스트와 마찬가지로 O(1)~O(n) 시간 안에 손쉽게 요소를 제거할 수 있습니다.