最令初学 C 语言的朋友犯难的，应该是指针了。下述内容绝大部分都可以在《深入理解计算机系统》一书中找到更细节的解释，但考虑到此书对初学者并不友好，因此我用更好懂的语言以及例子进行解释。有决心的读者应当在书中找到我所说的概念，验证学到的知识。

想要理解指针，需要先理解计算机中内存与地址的概念。

内存是计算机中存放运行时数据的地方。什么叫运行时数据呢？就是说程序正在运行的时候，需要的数据。当编译器把源代码编译为可执行文件的时候，这个文件是放在磁盘上的。在运行的时候，操作系统需要首先把这个可执行文件从磁盘里加载到内存中，然后才能执行。在执行过程中，程序需要对数据进行读写的操作，这些数据是存放在内存里的。

内存可以抽象地理解为一个无限长的格子序列，每个格子可以放一个字节的数据。我们称这样的一个格子为内存中的一个存储单元。

[ ] [ ] [ ] [ ] [ ] [ ] ...
^   ^   ^
|   |   |
0   1   2

同时，每个格子都有一个编号，这个编号我们称之为内存中的地址。从而，我们可以根据地址来找到存储单元，进一步地可以读取或者修改这个存储单元中的数据。

一般而言，你在 C 语言中声明的变量，都会存放在内存中的一段空间中。如果是一个 int 类型的变量，会占用连续的四个字节；一个数组则会占用连续的数组大小乘以每个元素大小的空间。注意，这里着重强调“连续”的概念。

举个例子，如果你在程序中声明了 int a[101]; 的数组，那么内存中就会有一段空间用来存放这个数组。这段空间的大小应该是 $4\times 101$ 个字节，因为每个 int 元素的大小为 4 个字节，而这个数组内总共有 101 个元素。

数组中第一个元素 a[0] 的地址，就是这段空间的地址。在 C 语言中，我们可以通过在变量前添加 & 来获取这个变量的地址，& 被称为取地址运算符。举例来说，如果数组 a 在内存空间中占用的地址区间是 [400, 804)（注意是左闭右开的区间），那么 &a[0] 作为一个表达式的值就是数组 a 中第一个元素的地址，即 400，而 &a[33] 的值则为 $400+33\times 4=532$。

当我们知道了某个变量在内存中存储的地址，我们希望能通过地址来读取或者修改这个变量的值。

首先我们需要明白的是，变量在内存中究竟是如何存储的。

用 int 来举例，int 的大小为 4 个字节。假设有一个 int 变量，值为 0x44332211 （这里用 16 进制表示，读者可以自行计算其十进制的值），那么从低位到高位，每个字节的值分别为 0x11, 0x22, 0x33, 0x44。假设这个变量存储在地址 [100, 104) 上，那么如果其摆放为 [0x11] [0x22] [0x33] [0x44] ，则称为小端表示法（little-endian），如果为 [0x44] [0x33] [0x22] [0x11] 则为大端表示法（big-endian），这摆放的顺序被称为字节序（endianness），不同的 CPU 架构可能会采用不同的字节序。CPU 在从内存中读取 int 的值时，会根据其认可的字节序来理解值。

对于复杂一些的结构体，例如 struct myStruct { int a; char b } s; 来说，我们定义了一个名为 s 的变量，其类型为 struct myStruct，包含了两个成员变量（field），分别为 int 和 char 两个类型。

首先一个问题是，s 会占用多少内存空间？单纯看成员变量，得出的结论是 $4 + 1 = 5$，然而有一个重要的规则要求，int 的变量只能从 4 的整倍数的地址上开始存储，即 int 变量能存储在 [104, 108) 这段地址上，但不能是 [102, 106) 这种地址。这个规则被称为地址对齐规则（alignment），类似地，对于 double 这种需要占用 8 个字节的变量，其地址需要按 8 的倍数对齐。因此，如果 s 占用 5 个字节的地址，那么在数组中连续摆放 struct myStruct 时，第二个结构体的 int 成员变量的地址将无法对齐。因此，s 需要占用 8 个字节，末尾的 3 个字节是浪费掉的。读者可以通过 https://godbolt.org/z/x8Kcvjh6s 查看编译器编译的结果，验证 myStruct 变量的确占用 8 个字节。

理解了对齐的规则，其实对结构体的存储表示就呼之欲出了。取决于是否允许对成员变量的摆放顺序进行重新排列，如果是按顺序摆放的话，需要对内部的每一个成员变量都执行对齐的规则，从最近的其大小整倍数的地址上开始摆放。

本质上说，内存只负责储存字节，需要程序来理解这些存储的字节数据的意义，指挥 CPU 对数据进行各种操作。而程序对数据的理解则来源于变量的类型。同样的 4 个字节，如果按照 int 理解，那么其值就是整数；如果按照 float 理解，那么其值就是浮点数。

回到“通过地址来读取或者修改这个变量的值”的问题上来。

光有地址，我们只能更好地理解变量的表示，想要真正发挥其能力，还需要引入指针的概念。

本质上说，指针就是一个存储地址的变量，所有的指针都是。

因此，所有指针在内存中的大小都是固定的。在过去的 32 位 CPU 上，这个大小为 4 个字节；在现在，大部分 CPU 都是 64 位，这个大小为 8 个字节。32 位、64 位的意思本质上就是允许用来表示地址的值大小，32 位 CPU 可以读取的地址的值可以用 32 个 bit 来表示，一个 byte 等价于 8 个 bit，因此作为存储地址的指针需要 4 个字节；而 64 位 CPU 可以访问的地址的值需要 64 个 bit，则指针需要 8 个字节。计算机世界里，很多东西都是有迹可循、有理可依的，读者应当多问为什么、多探索这背后的机理。

一个 int 指针，定义为 int* intPtr; ，表示其值作为地址开始往后的四个字节，存储了一个 int。类似的，一个 char 指针 char* charPtr; 表示其值作为地址的那个字节存储了一个 char；或者 myStruct 指针 struct myStruct* myStructPtr; 定义了一个名为 myStructPtr 的指针变量，其值作为地址开始往后的 8 个字节，存储了一个 struct myStruct。形象地说，我们称某个类型的指针在内存中指向了一个具有某个类型的变量。这个形象的比喻其实是让初学者迷惑的主要原因。特别是当我们学习到指针的指针的时候。

如果我们想要访问指针指向的变量时，我们需要使用一个特殊的运算符 *，这个运算符被称为解引用（dereference）运算符。对于指针 intPtr 而言，*intPtr 就表示内存中 intPtr 所指向的 int。如果我们写 *intPtr = 3 ，就是在给这个 int 赋值；而如果我们写 printf("%d\n", (*intPtr) * 2)，则是打印这个 int 与 2 乘的结果。请注意不要把解引用运算符和乘法运算，甚至是定义指针时所写的 * 搞混。

聪明的读者应该已经发现了，解引用运算和取地址运算互为逆操作。给定一个 int a = 520; 和一个 int* aPtr = &a; ，&a 获取了 a 这个变量的地址，于是 aPtr 存储了这个地址。因此，当我们写 *aPtr = 1314 的时候，a 这个变量的值就变成了 1314，而在任何我们需要 a 这个变量的值的时候，我们都可以写 *aPtr 来参与运算。

额外补充一下数组与指针的关系。数组本质上就是一个指针。例如 int arr[233]; 这样一个数组， arr 是可以当作一个指向数组在内存中第一个字节的地址的 int 指针来使用的。因此 *arr 等价于 a[0] 。得益于数组的元素在内存中是连续摆放的，C 语言还支持对指针进行加减法的运算，这被称为指针算术（pointer arithmatics）。不同于对数值的加减法运算，arr + 1 的值是 arr 的值加 4，因为指针的类型是 int。因此 *(arr + 1) 等价于 a[1]。

只有光秃秃的地址，我们无法理解这个地址中存储的值所表示的意义，因此我想强调的是指针需要类型帮助我们理解地址中的值。

一个指针中存储的地址，在解引用时究竟意味着什么，完全取决于这个指针的类型。类型明确了变量在内存中占用空间的大小，也明确了程序应该如何理解数据。

所以，一个 int 类型的指针，其存储的地址在解引用的时候应该按照 int 来理解。臭名昭著的指针的指针，不过是一个具有指针类型的指针而已，解引用这个指针就得到了另一个指针。

在理解取地址、解引用之后，我们来看一个具体的链表的 C 语言实现的例子。

首先我们定义一个结构体。

struct ListNode {
	int val;
	struct ListNode* next;
};

这个结构体包含两个成员变量，val 表示链表中元素的值，而 next 则是一个指向下一个元素的指针。

程序在运行过程中，可以动态地向操作系统索要内存空间，使用 malloc 函数，可以获得内存中一段连续的空间用来存放数据。

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

上面这一行代码调用了 malloc 函数申请了一端用来存放 struct ListNode 的内存空间。malloc 接受一个表示所需内存空间大小的值，这里我们使用 sizeof 运算，得到一个 struct ListNode 的大小。在上面了解了对齐规则后，我们知道，这个大小应该是 16。而 malloc 函数的返回值为开辟出的内存的首字节的地址。注意，malloc 函数返回的地址是没有类型的（没有类型的指针用void* 类型表示），因为 malloc 函数的参数只告知了内存大小，而没有告知数据类型，因此需要进行一次强制类型转换。malloc 函数前的 (struct ListNode*) 表示将这个地址理解为一个 struct ListNode 的指针，这和我们为 newNode 变量声明的类型是一致的。

我们来看一段构建链表的代码。

struct ListNode* constructList(int* vals, int len) {
	struct ListNode* head = NULL;
	struct ListNode* last = NULL;
	for (int i = 0; i < len; ++i) {
		struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
		newNode->val = vals[i];
		if (last == NULL) {
			head = newNode;
			last = head;
		} else {
			last->next = newNode;
			last = newNode;
		}
	}
	last->next = NULL;
	return head;
}

这段代码的逻辑应当是好理解的。head 表示链表的第一个元素，last 表示最后一个元素，在插入元素的时候，如果 head 是空，则初始化 head 和 last 都为这个元素；否则我们把这个元素接到 last 后面，然后更新 last 为新的元素。

这样写的代码的唯一的问题是，给定的 if 判断其实是冗余的，只要我们愿意使用指针的指针，这段代码可以更简洁地写作

struct ListNode* constructList(int* vals, int len) {
	struct ListNode** head = （struct ListNode*)malloc(sizeof(struct ListNode*));
	struct ListNode** cur = head;
	for (int i = 0; i < len; ++i) {
		struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
		newNode->val = vals[i];
		*cur = newNode;
		cur = &(newNode->next);
	}
	*cur = NULL;
	return *head;
}

我个人更倾向于后一种写法，只要正确、深刻地理解指针的概念，后面这种写法所表现出来的简洁性更加具有美感。

我们可以逐行地进行分析。

前两行代码定义了两个可以指向类型为 struct ListNode* 的变量的指针，换言之就是指针的指针。head 初始化为了一个通过 malloc 申请的 struct ListNode* 的地址，而 cur 也同样指向这个 struct ListNode* 的空间。见下图，head 本身占用 8 字节的空间，地址为 [302, 310)，其存储的地址为 1000，指向 malloc 返回的地址。因为 malloc 申请的 struct ListNode* 也是一个指针，所以其大小也为 8 个字节。cur 的地址为 [310, 318) 同样指向这个指针。

head: [302, 310) ---> [1000, 1008)
                      ^
cur: [310,  318) -----|

随后，对于每一个链表中的元素，我们都通过 malloc 在内存中申请一个 struct ListNode 的空间，并为其 val 赋值。随后的

		*cur = newNode;
		cur = &(newNode->next);

是这个实现中最关键的地方。

newNode 的值是 malloc 返回的 struct ListNode 在内存中的地址，malloc 申请的空间的大小为 16 个字节（因为对齐规则）。所以 *cur = newNode 等价于把 malloc 返回的新节点的地址复制到 [1000, 1008) 所表示的内存空间上去。

head: [302, 310) ---> [1000, 1008) ---> newNode: [2000, 2016)
                      ^
cur: [310,  318) -----|

假设 newNode 的地址为 [2000, 2016)，那么 newNode→next 的地址则为 [2008, 2016)，所以而后的 cur = &(newNode→next) 则让 cur 指向了 [2008, 2016)

head: [302, 310) ---> [1000, 1008) ---> newNode: [2000, 2008, 2016)
                                                 [val,  next)
                                                        ^
cur: [310,  318) ---------------------------------------|

随后的迭代中，我们每次修改 *cur 就相当于让尾部节点的 next 等于新的节点，然后修改 cur 则相当于让 cur 指向新节点的 next 指针。

head: [302, 310) ---> [1000, 1008) ---> [2000, 2008, 2016)
                                        [val,  next)
																							 |
                                               ---> newNode: [3000, 3008, 3016)
                                                             [val,  next)
                                                                    ^
cur: [310,  318) ---------------------------------------------------|

最后的 *cur = NULL 让最后一个节点的 next 置为 NULL，表示链表的终结。

head: [302, 310) ---> [1000, 1008) ---> [2000, 2008, 2016)
                                        [val,  next)
																							 |
                                               ---> newNode: [3000, 3008, 3016)
                                                             [val,  next) ---> NULL
                                                                    ^
cur: [310,  318) ---------------------------------------------------|

而最开始的 head 指向的指针正是第一个节点的指针，所以返回 *head 即可。

到这里，读者应该理解了上述实现。事实上 Linux 的创始人 Linus 推崇下面这种写法，并称之为 good taste（好的品味）。

感兴趣的读者应当阅读 https://github.com/mkirchner/linked-list-good-taste 并理解其中通过指针的指针来删除节点的做法，它用到的知识就是本文所谈论的。

希望读者在这篇文章之后彻底理解指针的概念，并善于利用指针写出更优雅的代码。