链表

链表

• 链表是一种线性表存储结构，它通过指针将不连续的内存空间串在一起使用。

• 每个内存块称为一个结点，第一个结点称为头结点，最后一个结点称为尾结点。

• 除了尾结点，每个结点都包含一个后继指针，指向下一个结点，尾结点的后继指针，指向NULL。

链表的查找

链表不支持按照下标随机访问元素，需要一个结点一个结点遍历查找。

时间复杂度：O(n)

链表的删除

如果只考察删除这个操作，而不讨论查找指定结点这个过程，时间复杂度为O(1)，因为不需要进行数据的搬移。

链表的插入

如果在指定结点后面插入元素，时间复杂度为O(1)

单向链表

链表方向是单向的，每个结点只有一个后继指针，指向下一个结点。

循环链表

尾结点的后继指针指向的不是NULL，而是头结点，从而形成了一个环。

双向链表

每个结点包括两个指针，前驱指针pre指向上一个结点，后继指针指向下一个结点。

双向链表的性能有时候会优于单向链表，比如删除值等于给定值的结点，或者删除某个指针指向的结点，或者在某个结点前插入结点，这些情况都需要查找前驱结点，双向链表更适合。

链表 VS 数组

内存组织方式不同：

• 数组需要一块连续的内存单元，对CPU缓存友好

• 链表不需要内存连续，对CPU缓存不友好

复杂度不同：

• 数组的查找复杂度为O(1)，插入、删除复杂度为O(n)

• 链表的查找复杂度为O(n)，插入、删除复杂度为O(1)