链表

文章目录

概念

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

元素可以存储在内存中的任何地方。链表中的每个元素都存储下一个元素的地址，从而使一系列随机的内存地址串在一起。

链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

生活模型：藏宝游戏

只要有足够的内存，就可以为链表分配内存。

假如你只想读取最后一个元素，不能直接读取。但是你不知道它所在的地址，必须从头开始访问，直到访问到最后一个元素。同时访问所有元素时，效率很高，单独访问时，因为需要跳跃，导致效率很低。

需要插入元素时，若使用链表，只需修改前面元素指向的地址；而如果使用数组，则必须把后面所有元素都向后移一位，如果内存空间不足，整个数组都得复制到其他地方。（类似排队）

因为数组支持随机访问，所以经常被用来应用在构建需要支持能够随机访问的数据结构中。

链表的每个节点结构如下：
data|next
完整结构如下：
单链表
其中，head 保存首位节点的地址，其余节点保存本节点数据以及下一节点地址，最后一个节点保存节点数据，指向 null;