链表及其相关算法

简要链表的基础知识 #

链表在逻辑结构中是一种线性结构，除第一个节点无前驱节点和最后一个节点无后继节点之外，其他的节点都有一个前驱和后继节点。存储的数据在逻辑上是线性存储的，但在物理结构中并不是线性的，而是离散的。 常见的链表分为单向链表、单向循环链表、双向链表、双向循环链表，不同的链表逻辑结构相同，但是节点设计不同，根据需要去选择不同的链表类型。

• 链表中的每个节点至少包含两个部分：数据域和指针域，通俗的来说就是前者存储需要存储的数据，后者则存储的是下一个需要链接的节点内存地址。
• 链表中的每个节点，通过指针域的值，逻辑上形成一个线性结构
• 查找节点O(n)，插入节点O(1)，删除节点O(1)，链表是不支持随机访问的
• 不适合快速的定位数据，适合动态的插入和删除数据的应用场景