JavaScript 단일 연결 리스트에서 특정 값의 노드 제거하기

문제 소개

다음과 같이 객체 리터럴로 표현한 단일 연결 리스트(singly linked list)가 있다고 가정해 보겠습니다. 각 노드는 데이터(value)와 다음 노드를 가리키는 참조(next)로 구성되며, 마지막 노드의 next는 null입니다.

const list = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: {
                    value: 5,
                    next: {
                        value: 6,
                        next: {
                            value: 7,
                            next: null
                        }
                    }
                }
            }
        }
    }
};

요구 사항

연결 리스트를 첫 번째 인수로, 숫자를 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 리스트 전체를 탐색하여 해당 값을 가진 노드가 존재하는지 확인하고, 존재한다면 그 노드를 리스트에서 제거한 뒤 true를 반환해야 합니다. 값을 찾지 못하거나 리스트가 비어 있으면 false를 반환합니다.

구현 코드

재귀 호출을 활용한 구현 예시는 다음과 같습니다.

const list = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: {
                    value: 5,
                    next: {
                        value: 6,
                        next: {
                            value: 7,
                            next: null
                        }
                    }
                }
            }
        }
    }
};

// 값이 val인 노드를 찾아 리스트에서 제거하는 재귀 함수
const removeNode = (list = {}, val, prev = null) => {
    // 리스트 끝에 도달했지만 값을 찾지 못한 경우
    if (!list) {
        return false;
    }
    // 삭제할 노드를 발견한 경우
    if (list.value === val) {
        if (prev) {
            // 중간 또는 마지막 노드: 이전 노드가 다음 노드를 곧바로 가리키도록 변경
            prev.next = list.next;
        } else if (list.next) {
            // 첫 번째(헤드) 노드 삭제: 다음 노드의 값을 현재 노드로 복사 후 연결 조정
            list.value = list.next.value;
            list.next = list.next.next;
        } else {
            // 노드가 하나뿐인 리스트인 경우
            list.value = undefined;
        }
        return true;
    }
    // 아직 찾지 못했다면 현재 노드를 prev로 넘기며 다음 노드 탐색
    return removeNode(list.next, val, list);
};

console.log(removeNode(list, 3)); // true
console.log(JSON.stringify(list, undefined, 4));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다. 값이 3인 노드만 제거되고 나머지 노드들의 연결은 그대로 유지됩니다.

true
{
    "value": 1,
    "next": {
        "value": 2,
        "next": {
            "value": 4,
            "next": {
                "value": 5,
                "next": {
                    "value": 6,
                    "next": {
                        "value": 7,
                        "next": null
                    }
                }
            }
        }
    }
}

동작 원리

removeNode 함수는 세 개의 매개변수를 사용합니다.

list – 현재 검사 중인 노드
val – 삭제하려는 값
prev – 바로 앞 노드에 대한 참조(초기값은 null)

현재 노드의 값이 목표 값과 일치하면, 이전 노드의 next 참조를 현재 노드의 다음 노드로 변경해 연결고리에서 제외시킵니다. 이것이 연결 리스트에서 노드를 삭제하는 핵심 원리로, 배열과 달리 뒤따르는 모든 요소를 이동시킬 필요가 없습니다.

삭제 대상이 첫 번째 노드라면 이전 노드가 존재하지 않으므로, 다음 노드의 값을 현재 노드로 복사하고 연결을 한 칸 앞당기는 방식으로 처리합니다. 값이 일치하지 않으면 현재 노드를 prev로 전달하면서 다음 노드를 대상으로 재귀 호출을 이어가고, 리스트 끝(null)에 도달할 때까지 찾지 못하면 false를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)입니다. 재귀 대신 while 반복문으로 구현하면 호출 스택을 사용하지 않으므로 공간 복잡도를 O(1)로 개선할 수 있습니다.