Chèn các phần tử vào danh sách được liên kết kép bằng Javascript

Chúng ta cần tạo một hàm chèn (dữ liệu, vị trí) để chèn dữ liệu vào vị trí đã cho trong danh sách liên kết. Chúng tôi sẽ thực hiện các bước sau -

• Tạo một nút mới
• Kiểm tra xem danh sách có trống không. Nếu nó thì thêm nút vào head và tail rồi quay lại.
• Nếu không, thì chúng tôi sẽ lặp lại vị trí mà chúng tôi muốn chèn nó vào bằng cách sử dụng currElem. Chúng tôi lặp lại một danh sách được liên kết bằng cách đặt currElem bằng currElem.next.

Bây giờ chúng ta thay đổi các liên kết theo cách sau -

• Đặt nút mới trỏ đến nút tiếp theo trong danh sách
• Chuyển điểm trước đó của nút tiếp theo tới nút mới
• Làm cho nút của chúng ta trỏ đến nút trước đó
• Đưa điểm tiếp theo của nút trước tới nút mới

Cuối cùng, chúng tôi ngắt liên kết từ currElem đến phần còn lại của danh sách và làm cho nó trỏ đến nút đã tạo của chúng tôi. Bây giờ nút nằm trong danh sách ở vị trí đã cho.

Đây là một minh họa của cùng một -

Bây giờ chúng ta hãy xem cách chúng tôi sẽ triển khai điều này -

Ví dụ

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;
}

Lưu ý rằng chúng tôi đã đưa ra vị trí là yếu tố cuối cùng. Điều này là do nếu bạn không cung cấp một vị trí, nó sẽ được chèn vào cuối theo mặc định.

Bạn có thể kiểm tra điều này bằng cách sử dụng:

Ví dụ

let list = new LinkedList();
list.insert(10);
list.insert(20);
list.insert(30);
list.insert(15, 2);
list.display();

Đầu ra

Điều này sẽ cung cấp đầu ra -

10 <->
30 <->
15 <->
20 <->

Như chúng ta có thể thấy tất cả các yếu tố theo thứ tự mà chúng tôi dự định. Chúng tôi đã thử chèn 15 ở vị trí sau 2.