이중 연결 리스트(Doubly Linked List)에서 주어진 위치에 데이터를 삽입하는 함수 insert(data, position)를 만들어야 합니다. 구현은 다음 단계로 진행됩니다.
- 새로운 노드(Node)를 생성합니다.
- 리스트가 비어 있는지 확인합니다. 비어 있다면 노드를 head와 tail에 연결한 후 반환합니다.
- 비어 있지 않다면
currElem을 사용해 삽입하려는 위치까지 순회합니다. 연결 리스트는currElem을currElem.next로 갱신해가며 탐색합니다.
원하는 위치에 도달했다면, 이제 포인터(링크)를 다음과 같이 재구성합니다.
- 새 노드의 next가 리스트상의 다음 노드를 가리키도록 합니다.
- 다음 노드의 prev가 새 노드를 가리키도록 합니다.
- 새 노드의 prev가 이전 노드를 가리키도록 합니다.
- 이전 노드의 next가 새 노드를 가리키도록 합니다.
마지막으로 기존 노드(currElem)와 나머지 리스트 사이의 연결을 끊고 새로 생성한 노드로 연결을 변경하면, 해당 노드가 지정된 위치에 성공적으로 삽입됩니다.
아래 그림은 이 과정을 시각적으로 보여줍니다.
그럼 실제 구현 코드를 살펴보겠습니다.
예제 코드
insert(data, position = this.length) {
let node = new this.Node(data);
this.length++;
// 리스트가 현재 비어 있는 경우
if (this.head === null) {
this.head = node;
this.tail = node;
return this.head;
}
// head 위치에 삽입하는 경우
if (position == 0) {
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
return this.head;
}
let iter = 1;
let currNode = this.head;
while (currNode.next != null && iter < position) {
currNode = currNode.next;
iter++;
}
// 새 노드가 다음 노드를 가리키도록 설정
node.next = currNode.next;
// 다음 노드의 prev가 새 노드를 가리키도록 설정
if (currNode.next != null) {
currNode.next.prev = node;
}
// 새 노드가 이전 노드를 가리키도록 설정
node.prev = currNode;
// 이전 노드의 next가 새 노드를 가리키도록 설정
currNode.next = node;
// 삽입된 요소가 tail이라면 tail 포인터를 갱신
if (this.tail.next != null) {
this.tail = this.tail.next;
}
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 <->
출력 결과를 보면 모든 요소가 의도한 순서대로 정렬되어 있습니다. 값 15를 2번째 위치 뒤에 삽입했고, 기존 요소들 사이에 정확히 들어간 것을 확인할 수 있습니다.