Linked List

链表（Linked list）

• 链表（Linked list）是一种常见的基础数据结构，是一种线性表，
• 但是并不会按线性的顺序储存数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
• 由于不必须按顺序储存，链表在插入的时候可以达到 o(1)的复杂度，
• 比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 o(n)的时间，
• 而顺序表响应的时间复杂度分别是 o(logn)和 o(1)

优点

• 无需预先分配内存
• 插入/删除节点不影响其他节点，效率高（典型的例子：git commit）

单向链表：

是链表中最简单的一种，它包含两个域，一个信息域和一个指针域。

这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表包含两个值:

当前节点的值和一个指向下一个节点的链接

单链特点：

节点的链接方向是单向的；

相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很高。

Notion – The all-in-one workspace for your notes, tasks, wikis, and databases.A new tool that blends your everyday work apps into one. It's the all-in-one workspace for you and your teamhttps://serious-lose.notion.site/Linked-List-b25b203f540b433ab88c93d4481322ca