연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드에 대한 참조(포인터)를 함께 가지는 선형 자료구조입니다. 이번 글에서는 자바스크립트로 구현한 연결 리스트의 특정 위치에 새로운 요소를 삽입하는 insert(data, position) 함수를 만들어 보겠습니다.
삽입 동작의 단계별 흐름
- 새 노드 생성: 삽입할 데이터를 담은 새로운 Node 객체를 만듭니다.
- 빈 리스트 확인: 리스트가 비어 있다면(head === null) 새 노드를 head로 지정하고 바로 반환합니다.
- 위치까지 순회: 리스트가 비어 있지 않다면 currElem(현재 노드)을 따라 삽입하려는 위치까지 이동합니다. 연결 리스트는 currElem = currElem.next 방식으로 한 칸씩 순회합니다.
- 다음 노드 연결 유지: 새 노드가 기존의 다음 노드를 가리키도록 설정해, 뒤쪽 리스트가 끊기지 않도록 합니다.
- 연결 재설정: 마지막으로 현재 노드(currElem)와 나머지 리스트 사이의 링크를 끊고, 현재 노드가 새로 만든 노드를 가리키도록 합니다. 이렇게 하면 새 노드가 지정된 위치에 자연스럽게 들어갑니다.
아래 그림은 이 과정을 시각적으로 보여 줍니다.
그럼 실제 구현 코드를 살펴보겠습니다.
구현 예제
insert(data, position = this.length) {
let node = new this.Node(data);
if (this.head === null) {
this.head = node;
this.length++;
return this.head;
}
let iter = 1;
let currNode = this.head;
while (currNode.next != null && iter < position) {
currNode = currNode.next; iter++;
}
node.next = currNode.next;
currNode.next = node;
this.length++;
return node;
}
여기서 position 매개변수의 기본값을 this.length, 즉 마지막 위치로 지정했습니다. 덕분에 position 값을 전달하지 않으면 요소가 자동으로 리스트 맨 끝에 추가됩니다.
실제로 테스트해 보겠습니다.
실행 예제
let list = new LinkedList(); list.insert(10); list.insert(20); list.insert(30); list.insert(15, 2); list.display();
출력 결과
10 -> 30 -> 15 -> 20 ->
실행 결과를 보면 모든 요소가 의도한 순서대로 배치되었으며, 2번째 위치 뒤에 15를 삽입한 것을 확인할 수 있습니다.