链表
在计算机科学中, 一个 链表 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。
链表是一种基础的数据结构，它由一系列节点组成，这些节点通过指针连接起来。
每个节点至少包含两个部分：一部分是存储数据的元素，另一部分是指向列表中下一个节点的指针（在双向链表中，还会有一个指向前一个节点的指针）。
链表允许动态地在任何位置添加或删除节点，这使得它在处理未知数量的数据时非常有用。
单向链表（Singly Linked List）：
每个节点包含一个指向下一个节点的指针。
插入和删除操作通常在链表的末尾或通过一个给定的节点进行。
双向链表（Doubly Linked List）：
每个节点包含两个指针，一个指向前一个节点，另一个指向下一个节点。
这使得可以在两个方向上遍历链表，也便于在节点的任意一侧进行插入和删除。
循环链表（Circular Linked List）：
链表的最后一个节点的指针指向链表的第一个节点（单向循环链表）或最后一个节点（双向循环链表）。
循环链表常用于实现队列和栈等数据结构。
优点：
动态大小：链表的大小可以根据需要动态增长或缩小。
插入和删除操作高效：在已知节点的情况下，可以在O(1)时间内插入或删除节点。
无需连续内存：链表不需要一块连续的内存空间，可以更好地利用内存。
缺点：
访问速度慢：访问链表中的元素需要从头开始遍历，时间复杂度为O(n)。
额外的内存开销：每个节点需要额外的空间来存储指针。
链表的应用
实现栈和队列。
用于哈希表中的冲突解决。
用于实现某些类型的数据库和文件系统。
在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。
更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(而且难以管道化)。
更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。
基本操作的伪代码
插入
add
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 AddPrepend
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搜索
Contains
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删除
Remove
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遍历
Traverse
Traverse(head)
Pre: head is the head node in the list
Post: the items in the list have been traversed
n ← head
while n != ø
yield n.value
n ← n.next
end while
end Traverse反向遍历
ReverseTraversal
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复杂度
时间复杂度
| Access | Search | Insertion | Deletion |
| O(n) | O(n) | O(1) | O(1) |
空间复杂度
O(n)
https://gitee.com/lucky_ck/algorithms
我希望这篇文章对您有所帮助。
Thank you for reading.
