C++链表和数组：零基础入门到精通

链表和数组是计算机科学中常见的两种数据结构。其中数组有以下特点：

1.数组是一块连续的区域。

2.数组需要预留空间，可能会有空间没有数据或者数据不够放的情况。

3.插入和删除效率低，需要移动后继的元素。

4.随机访问效率高，因为每个元素地址都是已知的。

而链表则有以下特点：

1.链表的每个节点都不需要连续，可以放在任何地方。

2.不用预留空间，数据可随意增删。

3.每个节点都存着下个节点的地址。

4.访问需要顺着一个个节点找，不支持随机访问。

我们可以看到链表和数组的区别是非常大的，适用场景也不尽相同。接下来我们学习如何利用指针实现基本的单向链表及其基本操作。

动手写12.3.1

(www.xing528.com)

动手写12.3.1展示了单链表的实现和应用，运行结果如图12.3.1所示：

图12.3.1　单链表

本示例只实现了在单链表头部添加和删除元素的操作，结合遍历我们也能很方便地实现尾部的添加和删除元素。在链表中间添加和删除元素的过程略微烦琐一些，在这里笔者只介绍链表的内存结构，感兴趣的读者可以查看一些与数据结构相关的资料。

我们可以看到，单链表的实体其实就是一个头部节点，而每个节点里存放着数据和指向下一个节点的指针。之所以叫单链表是因为要与实现list的双链表区分。双链表的节点除了下一个节点的指针之外，还保留着上一个节点的指针，从而可以实现双向的遍历。但也正因如此，双链表的添加和删除操作实现起来更容易出错，因为我们要将两个节点的4个指针都进行修改。

关于指针的内容，画图表示总是更直观一些，接下来让我们看一下链表实现和在头部添加和删除节点的图解：

图12.3.2　链表的内存结构

图12.3.2中的链表节点在内存中是分散放置的，但是由于节点中存着下一个节点的地址（104、204），我们就可以跳转到那个地址去获取数据。

图12.3.3　添加和删除首节点

在添加和删除的过程中，我们经常需要做的是修改现有节点的next，在添加的时候由于新节点的next初始化为空，我们需要修改next让它链接到原来的head首节点上去。