《链表与数组》

说明：本笔记仅供自我学习。参考极客时间王争的《数据结构与算法之美》专栏。首先我们得知道是什么数组？

数组是一种线性表的数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。如果是查找的话就算排好序的数组

，你用二分查找的话，时间复杂度应该为O(logn)。并且如果是删除和插入元素的话，其最坏复杂度为O(n)。

链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了储存数据之外还要记录下一个节点的地址，我们把记录下一个节点的地址的指针叫做后继指针。我们把第一个节点叫做头节点，最后一个节点叫做尾节点。头节点用来记录链表的基地址。尾节点储存的就是空地址 NULL。链表的话由于其是不连续的空间所以针对插入和删除是非常快速的。其复杂度是O(1)。如果是想访问的由于其内存空间不是连续的，需要遍历才行。其复杂度为O(n)。

链表分为单链表和双链表以及循环链表，接下来我们看看循环列表。循环列表是一种特殊的单链表其尾节点指向的不是空地址而是头节点。

再接下来我们看看双向链表，单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指prev 指向前面的结点。

最后来一个数组和链表的性能大比拼。

数组对于插入和删除是非常低效的其复杂度是O(n)，对于随机访问是很高效的其复杂度为O(1)。

而链表恰恰相反，它对于数据的插入和删除其复杂度是O(1),对于随机访问其复杂度是O(n)。