审核中~
溜忙之道
首页
溜忙手册
offer之道
项目Git
写文章
登录
·
注册
登录
没有账号,去注册
注册
已有账号,去登录
博客
双向链表
南易_站长
阅读量:6121
关注
双向链表
# 双向链表 在计算机科学中, 一个 **双向链表(doubly linked list)** 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段,称为链接,它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点,通常是前哨节点或 null,以方便遍历列表。如果只有一个前哨节点,则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表,但顺序相反。 [![Doubly Linked List](https://camo.githubusercontent.com/a77efae509d76b6329bf3752d5367aaa4d8905f0/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f352f35652f446f75626c792d6c696e6b65642d6c6973742e737667)](https://camo.githubusercontent.com/a77efae509d76b6329bf3752d5367aaa4d8905f0/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f352f35652f446f75626c792d6c696e6b65642d6c6973742e737667) 两个节点链接允许在任一方向上遍历列表。 在双向链表中进行添加或者删除节点时,需做的链接更改要比单向链表复杂得多。这种操作在单向链表中更简单高效,因为不需要关注一个节点(除第一个和最后一个节点以外的节点)的两个链接,而只需要关注一个链接即可。 ## [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C%E7%9A%84%E4%BC%AA%E4%BB%A3%E7%A0%81)基础操作的伪代码 ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E6%8F%92%E5%85%A5)插入 ``` Add(value) Pre: value is the value to add to the list Post: value has been placed at the tail of the list n ← node(value) if head = ø head ← n tail ← n else n.previous ← tail tail.next ← n tail ← n end if end Add ``` ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E5%88%A0%E9%99%A4)删除 ``` Remove(head, value) Pre: head is the head node in the list value is the value to remove from the list Post: value is removed from the list, true; otherwise false if head = ø return false end if if value = head.value if head = tail head ← ø tail ← ø else head ← head.next head.previous ← ø end if return true end if n ← head.next while n = ø and value = n.value n ← n.next end while if n = tail tail ← tail.previous tail.next ← ø return true else if n = ø n.previous.next ← n.next n.next.previous ← n.previous return true end if return false end Remove ``` ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E5%8F%8D%E5%90%91%E9%81%8D%E5%8E%86)反向遍历 ``` ReverseTraversal(tail) Pre: tail is the node of the list to traverse Post: the list has been traversed in reverse order n ← tail while n = ø yield n.value n ← n.previous end while end Reverse Traversal ``` ## [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E5%A4%8D%E6%9D%82%E5%BA%A6)复杂度 ## [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)时间复杂度 | Access | Search | Insertion | Deletion | | :-: | :-: | :-: | :-: | | O(n) | O(n) | O(1) | O(1) | ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/doubly-linked-list/README.zh-CN.md#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)空间复杂度 O(n)
评论
表情
发送
0
评论