假设理解 big o 表示法。 javascript 中有示例。资料参考 gayle laakmann mcdowell 的《cracking the coding interview》
理解双向链表
双向链表与单链表非常相似，除了节点的结构和添加/删除节点的方式不同。
节点结构
双向链表中的节点包含
prev指针、next指针和value。 prev 指针指向前一个节点，next 指针指向下一个节点。本质上，这个列表在每个节点都是双向的。
添加节点
在特定索引处插入新节点（newnode）：
将当前位于插入索引处的节点存储在临时变量 nextnode 中。
更新前一个节点和新节点的连接：
将前一个节点的next指针设置为newnode。设置newnode的prev指针指向前一个节点。将新节点连接到下一个节点：
将newnode的next指针设置为nextnode。将 nextnode 的 prev 指针设置为 newnode。 删除节点
要删除特定索引处的节点：
更新前一个节点的next指针：设置为指向被移除后的节点。更新下一个节点的prev指针：将其设置为指向被删除节点之前的节点。这有效地“弥合”了删除节点所产生的间隙，保持了列表的完整性。
时间复杂度分析
在双向链表中添加/删除 →
o(n)
在双向链表的头部或尾部添加/删除 →
o(1)
javascript 实现
经典面向对象编程
class listnode { constructor(value, prev = null, next = null) { this.value = value; this.prev = prev; this.next = next; }}class doublylinkedlist { constructor() { this.head = null; this.tail = null; this.size = 0; } // add a node to the head of the list addhead(value) { const newnode = new listnode(value, null, this.head); if (this.head) { this.head.prev = newnode; } else { this.tail = newnode; // if list was empty, new node is also the tail } this.head = newnode; this.size++; } // add a node to the tail of the list addtail(value) { const newnode = new listnode(value, this.tail, null); if (this.tail) { this.tail.next = newnode; } else { this.head = newnode; // if list was empty, new node is also the head } this.tail = newnode; this.size++; } // remove a node from the head of the list removehead() { if (!this.head) return null; // list is empty const removedvalue = this.head.value; this.head = this.head.next; if (this.head) { this.head.prev = null; } else { this.tail = null; // list became empty } this.size--; return removedvalue; } // remove a node from the tail of the list removetail() { if (!this.tail) return null; // list is empty const removedvalue = this.tail.value; this.tail = this.tail.prev; if (this.tail) { this.tail.next = null; } else { this.head = null; // list became empty } this.size--; return removedvalue; } // remove a node at a specific index removeat(index) { if (index = this.size) return null; let current; if (index < this.size / 2) { current = this.head; for (let i = 0; i index; i--) { current = current.prev; } } if (current.prev) current.prev.next = current.next; if (current.next) current.next.prev = current.prev; if (index === 0) this.head = current.next; if (index === this.size - 1) this.tail = current.prev; this.size--; return current.value; } // get the size of the list getsize() { return this.size; } // get the values in the list getvalues() { const values = []; let current = this.head; while (current) { values.push(current.value); current = current.next; } return values; }}
class listnode { constructor(value, prev = null, next = null) { this.value = value; this.prev = prev; this.next = next; }}class doublylinkedlist { constructor() { this.head = null; this.tail = null; this.size = 0; } // add a node to the head of the list addhead(value) { const newnode = new listnode(value, null, this.head); if (this.head) { this.head.prev = newnode; } else { this.tail = newnode; // if list was empty, new node is also the tail } this.head = newnode; this.size++; } // add a node to the tail of the list addtail(value) { const newnode = new listnode(value, this.tail, null); if (this.tail) { this.tail.next = newnode; } else { this.head = newnode; // if list was empty, new node is also the head } this.tail = newnode; this.size++; } // remove a node from the head of the list removehead() { if (!this.head) return null; // list is empty const removedvalue = this.head.value; this.head = this.head.next; if (this.head) { this.head.prev = null; } else { this.tail = null; // list became empty } this.size--; return removedvalue; } // remove a node from the tail of the list removetail() { if (!this.tail) return null; // list is empty const removedvalue = this.tail.value; this.tail = this.tail.prev; if (this.tail) { this.tail.next = null; } else { this.head = null; // list became empty } this.size--; return removedvalue; } // remove a node at a specific index removeat(index) { if (index = this.size) return null; let current; if (index < this.size / 2) { current = this.head; for (let i = 0; i index; i--) { current = current.prev; } } if (current.prev) current.prev.next = current.next; if (current.next) current.next.prev = current.prev; if (index === 0) this.head = current.next; if (index === this.size - 1) this.tail = current.prev; this.size--; return current.value; } // get the size of the list getsize() { return this.size; } // get the values in the list getvalues() { const values = []; let current = this.head; while (current) { values.push(current.value); current = current.next; } return values; }}
函数式面向对象编程
function ListNode(value, prev = null, next = null) { this.value = value; this.prev = prev; this.next = next;}function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0;}// Add a node to the head of the listDoublyLinkedList.prototype.addHead = function(value) { const newNode = new ListNode(value, null, this.head); if (this.head) { this.head.prev = newNode; } else { this.tail = newNode; } this.head = newNode; this.size++;};// Add a node to the tail of the listDoublyLinkedList.prototype.addTail = function(value) { const newNode = new ListNode(value, this.tail, null); if (this.tail) { this.tail.next = newNode; } else { this.head = newNode; } this.tail = newNode; this.size++;};// Remove a node from the head of the listDoublyLinkedList.prototype.removeHead = function() { if (!this.head) return null; const removedValue = this.head.value; this.head = this.head.next; if (this.head) { this.head.prev = null; } else { this.tail = null; } this.size--; return removedValue;};// Remove a node from the tail of the listDoublyLinkedList.prototype.removeTail = function() { if (!this.tail) return null; const removedValue = this.tail.value; this.tail = this.tail.prev; if (this.tail) { this.tail.next = null; } else { this.head = null; } this.size--; return removedValue;};// Remove a node at a specific indexDoublyLinkedList.prototype.removeAt = function(index) { if (index = this.size) return null; let current; if (index < this.size / 2) { current = this.head; for (let i = 0; i index; i--) { current = current.prev; } } if (current.prev) current.prev.next = current.next; if (current.next) current.next.prev = current.prev; if (index === 0) this.head = current.next; if (index === this.size - 1) this.tail = current.prev; this.size--; return current.value;};// Get the size of the listDoublyLinkedList.prototype.getSize = function() { return this.size;};// Get the values in the listDoublyLinkedList.prototype.getValues = function() { const values = []; let current = this.head; while (current) { values.push(current.value); current = current.next; } return values;};
function ListNode(value, prev = null, next = null) { this.value = value; this.prev = prev; this.next = next;}function DoublyLinkedList() { this.head = null; this.tail = null; this.size = 0;}// Add a node to the head of the listDoublyLinkedList.prototype.addHead = function(value) { const newNode = new ListNode(value, null, this.head); if (this.head) { this.head.prev = newNode; } else { this.tail = newNode; } this.head = newNode; this.size++;};// Add a node to the tail of the listDoublyLinkedList.prototype.addTail = function(value) { const newNode = new ListNode(value, this.tail, null); if (this.tail) { this.tail.next = newNode; } else { this.head = newNode; } this.tail = newNode; this.size++;};// Remove a node from the head of the listDoublyLinkedList.prototype.removeHead = function() { if (!this.head) return null; const removedValue = this.head.value; this.head = this.head.next; if (this.head) { this.head.prev = null; } else { this.tail = null; } this.size--; return removedValue;};// Remove a node from the tail of the listDoublyLinkedList.prototype.removeTail = function() { if (!this.tail) return null; const removedValue = this.tail.value; this.tail = this.tail.prev; if (this.tail) { this.tail.next = null; } else { this.head = null; } this.size--; return removedValue;};// Remove a node at a specific indexDoublyLinkedList.prototype.removeAt = function(index) { if (index = this.size) return null; let current; if (index < this.size / 2) { current = this.head; for (let i = 0; i index; i--) { current = current.prev; } } if (current.prev) current.prev.next = current.next; if (current.next) current.next.prev = current.prev; if (index === 0) this.head = current.next; if (index === this.size - 1) this.tail = current.prev; this.size--; return current.value;};// Get the size of the listDoublyLinkedList.prototype.getSize = function() { return this.size;};// Get the values in the listDoublyLinkedList.prototype.getValues = function() { const values = []; let current = this.head; while (current) { values.push(current.value); current = current.next; } return values;};
以上就是实现双向链表的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1490414.html
微信扫一扫 
支付宝扫一扫 
