审核中~
溜忙之道
首页
溜忙手册
offer之道
项目Git
写文章
登录
·
注册
登录
没有账号,去注册
注册
已有账号,去登录
博客
链表
南易_站长
阅读量:6638
关注
链表
# 链表 在计算机科学中, 一个 **链表** 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。 在最简单的形式下,每个节点由数据和到序列中下一个节点的引用(换句话说,链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。 更复杂的变体添加额外的链接,允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(而且难以管道化)。 更快的访问,如随机访问,是不可行的。与链表相比,数组具有更好的缓存位置。 [![Linked List](https://camo.githubusercontent.com/37013b59008ed49a6701968da6b182eb6a9d24c8/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f362f36642f53696e676c792d6c696e6b65642d6c6973742e737667)](https://camo.githubusercontent.com/37013b59008ed49a6701968da6b182eb6a9d24c8/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f362f36642f53696e676c792d6c696e6b65642d6c6973742e737667) ## [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/linked-list/README.zh-CN.md#%E5%9F%BA%E6%9C%AC%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/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 tail.next ← n tail ← n end if end Add ``` ``` Prepend(value) Pre: value is the value to add to the list Post: value has been placed at the head of the list n ← node(value) n.next ← head head ← n if tail = ø tail ← n end end Prepend ``` ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/linked-list/README.zh-CN.md#%E6%90%9C%E7%B4%A2)搜索 ``` Contains(head, value) Pre: head is the head node in the list value is the value to search for Post: the item is either in the linked list, true; otherwise false n ← head while n != ø and n.value != value n ← n.next end while if n = ø return false end if return true end Contains ``` ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/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 n ← head if n.value = value if head = tail head ← ø tail ← ø else head ← head.next end if return true end if while n.next != ø and n.next.value != value n ← n.next end while if n.next != ø if n.next = tail tail ← n end if n.next ← n.next.next return true end if return false end Remove ``` ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/linked-list/README.zh-CN.md#%E9%81%8D%E5%8E%86)遍历 ``` Traverse(head) Pre: head is the head node in the list Post: the items in the list have been traversed n ← head while n != 0 yield n.value n ← n.next end while end Traverse ``` ### [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/linked-list/README.zh-CN.md#%E5%8F%8D%E5%90%91%E9%81%8D%E5%8E%86)反向遍历 ``` ReverseTraversal(head, tail) Pre: head and tail belong to the same list Post: the items in the list have been traversed in reverse order if tail != ø curr ← tail while curr != head prev ← head while prev.next != curr prev ← prev.next end while yield curr.value curr ← prev end while yield curr.value end if end ReverseTraversal ``` ## [](https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/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/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/linked-list/README.zh-CN.md#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)空间复杂度 O(n)
评论
表情
发送
0
评论