Cần tạo hàm insert(data, position) chèn dữ liệu tại vị trí cho trước. Các bước:
- Tạo Node mới
- Kiểm tra list rỗng: thêm vào head và tail, return
- Không rỗng: duyệt đến vị trí cần chèn với currElem (currElem = currElem.next)
Thay đổi liên kết:
- Node mới trỏ đến node tiếp theo
- Node tiếp theo prev trỏ về node mới
- Node mới prev trỏ về node trước
- Node trước next trỏ về node mới
Minh họa:
Triển khai
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; } 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; if (currNode.next != null) { currNode.next.prev = node; } node.prev = currNode; currNode.next = node; if (this.tail.next != null) { this.tail = this.tail.next; } return node; }
Tham số position mặc định = this.length (chèn cuối). Test:
Ví dụ
let list = new LinkedList(); list.insert(10); list.insert(20); list.insert(30); list.insert(15, 2); list.display();
Kết quả
10 <-> 30 <-> 15 <-> 20 <->
Chèn 15 tại vị trí sau 2 (index 2).