연결 리스트에서 요소를 제거하는 것은 생각보다 매우 간단합니다. 핵심은 제거하려는 노드의 참조(reference)를 끊어버리는 것입니다. 즉, 해당 노드를 가리키는 링크를 없애면 자연스럽게 리스트에서 분리됩니다.
요소를 제거할 때는 크게 세 가지 경우를 고려해야 합니다.
연결 리스트에서 요소를 제거하는 세 가지 경우
1. 헤드(Head)에서 요소 제거
첫 번째 요소를 제거하는 경우에는 head = head.next로 간단히 할당해 주면 됩니다. 이렇게 하면 첫 번째 노드에 대한 참조가 사라지고, 헤드가 두 번째 요소를 가리키게 됩니다.
2. 꼬리(Tail)에서 요소 제거
마지막 요소를 제거하는 경우에는 뒤에서 두 번째 노드의 next 값을 null로 설정하면 됩니다. 그러면 마지막 노드와의 연결이 끊어져 리스트에서 제거됩니다.
3. 중간에서 요소 제거
중간에 있는 요소를 제거하는 것이 가장 까다롭습니다. 이 경우에는 제거하려는 노드의 이전 노드가 제거하려는 노드의 다음 노드를 직접 가리키도록 만들어야 합니다. 즉, prevNode.next = node.next 한 줄로 처리할 수 있습니다.
아래 그림은 이 과정을 시각적으로 보여줍니다.
그럼 실제 구현 코드를 살펴보겠습니다.
구현 예제
remove(data, position = 0) {
if (this.length === 0) {
console.log("List is already empty");
return;
}
this.length--;
let currNode = this.head;
// 조건 1: 헤드 제거
if (position <= 0) {
this.head = this.head.next;
}
// 조건 2: 꼬리 제거
else if (position >= this.length - 1) {
while (currNode.next.next != null) {
currNode = currNode.next;
}
currNode.next = null;
}
// 조건 3: 중간 제거
else {
let iter = 0;
while (iter < position) {
currNode = currNode.next; iter++;
}
currNode.next = currNode.next.next;
}
}위 메서드는 position 인자를 기준으로 세 가지 경우를 모두 처리합니다. 리스트가 비어 있는 경우도 먼저 확인하여 안정성을 확보했습니다.
테스트 코드
실제로 동작을 확인해 보겠습니다.
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 ->
먼저 remove(1)로 인덱스 1의 요소(20)가 제거되고, 이후 insert(15, 2)로 15가 삽입된 뒤, remove()로 헤드 요소가 제거되는 과정을 결과에서 확인할 수 있습니다.