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

理解双向链表

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

节点结构

双向链表中的节点包含

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

添加节点

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

1. 将当前位于插入索引处的节点存储在临时变量 nextnode 中。
   

   CSS婚礼策划服务机构宣传网站模板

   CSS婚礼策划服务机构宣传网站模板是一款适合提供婚礼策划和婚庆服务机构宣传网站模板下载。提示：本模板调用到谷歌字体库，可能会出现页面打开比较缓慢。

   下载
2. 更新前一个节点和新节点的连接：
   将前一个节点的next指针设置为newnode。
   设置newnode的prev指针指向前一个节点。
3. 将新节点连接到下一个节点：
   将newnode的next指针设置为nextnode。
   将 nextnode 的 prev 指针设置为 newnode。

删除节点

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

更新前一个节点的next指针：
1. 设置为指向被移除后的节点。
更新下一个节点的prev指针：
2. 将其设置为指向被删除节点之前的节点。

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

时间复杂度分析

• 在双向链表中添加/删除 →

  o(n)o(n)o(n)

• 在双向链表的头部或尾部添加/删除 →

  o(1)o(1)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 < 0 || index >= this.size) return null;
    let current;
    if (index < this.size / 2) {
      current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = this.size - 1; 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 list
DoublyLinkedList.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 list
DoublyLinkedList.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 list
DoublyLinkedList.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 list
DoublyLinkedList.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 index
DoublyLinkedList.prototype.removeAt = function(index) {
  if (index < 0 || index >= this.size) return null;
  let current;
  if (index < this.size / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
  } else {
    current = this.tail;
    for (let i = this.size - 1; 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
DoublyLinkedList.prototype.getSize = function() {
  return this.size;
};

// Get the values in the list
DoublyLinkedList.prototype.getValues = function() {
  const values = [];
  let current = this.head;
  while (current) {
    values.push(current.value);
    current = current.next;
  }
  return values;
};