数据结构中，链表是如何实现动态存储的？

本文共计3592个文字，预计阅读时间需要15分钟。

链表和数组都需要一块连续的内存空间来存储，对内存的要求较高。如果我们请求一个100MB大小的数组，而内存中连续的、足够大的存储空间不足，那么即便内存的剩余总可用空间大于100MB，也无法满足需求。

链表

数组要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间 时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。

 

链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。

 

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点 的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。

单向链表

单向链表就是通过每个节点的指针指向下一个节点从而链接起来的结构，最后一个节点的next指向null。

其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。