实现双向链表

假设理解 big o 表示法。 javascript 中有示例。资料参考 gayle laakmann mcdowell 的《cracking the coding interview》

理解双向链表

双向链表与单链表非常相似，除了节点的结构和添加/删除节点的方式不同。

节点结构

双向链表中的节点包含

prev指针、next指针和value。 prev 指针指向前一个节点，next 指针指向下一个节点。本质上，这个列表在每个节点都是双向的。

添加节点

在特定索引处插入新节点（newnode）：

1. 将当前位于插入索引处的节点存储在临时变量 nextnode 中。
2. 更新前一个节点和新节点的连接：

3. 将新节点连接到下一个节点：

删除节点

要删除特定索引处的节点：

更新前一个节点的next指针：
1. 更新下一个节点的prev指针：

这有效地“弥合”了删除节点所产生的间隙，保持了列表的完整性。

时间复杂度分析

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