Javascript를 사용하여 이중 연결 목록에 요소 삽입

연결 리스트의 주어진 위치에 데이터를 삽입하는 insert(data, position) 함수를 만들어야 합니다. 다음 단계를 수행합니다 -

• 새 노드 생성
• 목록이 비어 있는지 확인합니다. 그러면 head와 tail에 노드를 추가하고 반환합니다.
• 그렇지 않은 경우 currElem을 사용하여 삽입하려는 위치로 반복합니다. currElem을 currElem.next와 동일하게 만들어 연결 목록을 반복합니다.

이제 다음과 같은 방식으로 링크를 변경합니다 -

• 목록의 다음 노드를 가리키는 새 노드 만들기
• 다음 노드의 이전 지점을 새 노드로 만들기
• 노드가 이전 노드를 가리키도록 합니다.
• 이전 노드의 다음 지점을 새 노드로 만들기

마지막으로 currElem에서 나머지 목록으로의 링크를 끊고 생성된 노드를 가리키도록 합니다. 이제 노드는 지정된 위치의 목록에 있습니다.

다음은 동일한 그림입니다 -

이제 이것을 구현하는 방법을 살펴보겠습니다 -

예시

insert(data, position = this.length) {
   let node = new this.Node(data);
   this.length++;
   // List is currently empty
   if (this.head === null) {
      this.head = node;
      this.tail = node;
      return this.head;
   }
   // Insertion at 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++;
   }
   // Make new node point to next node in list
   node.next = currNode.next;
   // Make next node's previous point to new node
   if (currNode.next != null) {
      currNode.next.prev = node;
   }
   // Make our node point to previous node
   node.prev = currNode;
   // Make previous node's next point to new node
   currNode.next = node;
   // check if inserted element was at the tail, if yes then make tail point to it
   if (this.tail.next != null) {
      this.tail = this.tail.next;
    }
    return node;
}

마지막 요소로 위치를 지정했습니다. 위치를 지정하지 않으면 기본적으로 맨 끝에 삽입되기 때문입니다.

다음을 사용하여 테스트할 수 있습니다.

예시

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를 삽입해 보았습니다.