> For the complete documentation index, see [llms.txt](https://mm.ricky.moe/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mm.ricky.moe/algorithm/algorithm-and-data-structure/shu-ju-jie-gou/lian-biao/shuang-xiang-lian-biao.md).

# 双向链表

双向链表中节点除了有 `next` 指向下一个节点，还有`prev`指向前一个节点。双向链表的优点在于能够从头到尾迭代，也能够从尾到头迭代。如果从头到尾遍历到中间位置的时候，想反向从尾到头进行遍历，也是可以办到的。

双向链表虽然比单向链表占了更多的内存，但是双向链表最大的好处是删除给定指针操作时不用再遍历一遍找到其 `prev` 指向的节点，所以此时的删除操作单向链表时间复杂度是 `O(n)`，双向链表的时间复杂度是 `O(1)`。<br>

![](/files/-Lxe74WxeWyaIQBjr47H)

```javascript
const DoubleLinkedList = (function(){
  let Node = function (element) {
    this.element = element
    this.prev = this.next = null
  }
  class DoubleLinkedList {
    constructor () {
      this.head = this.tail = null
      this.length = 0
    }
    append (element) {
      let newNode = new Node(element)
      if (!this.head) {
        this.head = this.tail = newNode
      } else {
        let current = this.head
        while (current) {
          current = current.next
        }
        current = this.tail
        current.next = this.tail = newNode
        newNode.prev = current
      }
    }
    insert (position, element) {
      if (position < 0 || position > this.length) {
        return false
      }
      let newNode = new Node(element)
      let previous, current = this.head, index = 0
      if (position === 0) {
        if (!this.head) {
          this.head = this.tail = newNode
        } else {
          newNode.next = current
          current.prev = newNode
          this.head = newNode
        }
      } else if (position === this.length) {
        this.tail.next = newNode
        newNode.prev = this.tail
        this.tail = newNode
      } else {
        while (index++ < position) {
          previous = current
          current = newNode
        }
        previous.next = newNode
        newNode.prev = previous
        newNode.next = current
        current.prev = newNode
      }
      this.length++
      return true
    }
    removeAt (position) {
      if (position < 0 || position >= this.length) {
        return false
      }
      let previous, current = this.head, index = 0
      if (position === 0) {
        this.head = current.next
        if (this.length === 1) {
          this.tail = null // 若只有一项，则 current.next 为 null ，所以只需要将尾部设为 null
        } else {
          this.head.prev = null
        }
      } else if (position === this.length - 1) {
        current = this.tail
        this.tail = current.prev
        this.tail.next = null
      } else {
        while (index++ < positon) {
          previous = current
          current = current.next
        }
        previous.next = current.next
        current.next.prev = previous
      }
      this.length--
      return current.element
    }
    // 删除指定节点
    removeByNode (node) {
      if (!node.prev) {
        this.head = node.next
        this.head.prev = null
        return
      }
      if (!node.next) {
        return
      }
      let prev = node.prev
      let next = node.next
      prev.next = next
      next.prev = prev
    }
    // 其他方法实现和单向链表相同
  }
  return DoubleLinkedList
})
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mm.ricky.moe/algorithm/algorithm-and-data-structure/shu-ju-jie-gou/lian-biao/shuang-xiang-lian-biao.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.