原文出处：http://learn-c.org/en/Linked_lists

介绍

链表是最好的、最简单的、用指针实现的动态数据结构例子。学习链表，需要有动态内存分配和结构体的相关基础。

实际上，链表具有数组的功能，它可以在任意的节点上增加或者减少元素。

相比数组，链表有以下的好处：

可以在链表的中间添加或者删除项目；不需定义初始长度

当然，链表也有一些缺点：

不可以“随机”访问——如果需要访问第 n 项，那么需要从头开始遍历链表直到第 n 项。需要使用动态内存分配和指针，这会使代码变得复杂，也提高了内存泄漏和段错误的风险。链表比数组的开销要大得多。这是因为链表的所有项是动态分配的（对内存的使用效率不高），并且链表中的每一项比数组要多存储一个指针。

什么是链表？

一个链表是一组动态分配的节点，其中每个节点包括一个值和一个指针。指针总是指向下一个成员。如果指针为 NULL，那么该指针所在节点是链表的最后一个节点。

一个链表有一个指向链表第一项的本地指针变量。如果该指针为 NULL，那么说明链表是空的。

------------------- ------------------- | | | \ | | | | DATA | NEXT |----------| DATA | NEXT | | | | / | | | ------------------- -------------------

举个例子看下如何定义一个链表：

typedef struct node { int val; struct node * next; } node_t;

注意到我们用递归的方式定义上述结构体，在 C 语言中是允许这样做的。我们将该类型命名为 node_t。

现在我们可以使用节点了。首先定义一个指向链表第一项的本地指针变量（称为 head）。

node_t * head = NULL; head = malloc(sizeof(node_t)); if (head == NULL) { return 1; } head->val = 1; head->next = NULL;

这就创建了链表的第一个变量。如果我们想要把数据填进链表，那么必须给 val 赋值，同时 next 指针设为 NULL。

如果想要在链表的最后添加变量，那么继续向前移动 next 指针即可。

node_t * head = NULL; head = malloc(sizeof(node_t)); head->val = 1; head->next = malloc(sizeof(node_t)); head->next->val = 2; head->next->next = NULL;

这可以一直继续下去，但是我们要做的是一直向着链表的最后一项前进，直到 next 变量为 NULL。

遍历链表

下面写一个函数用于打印链表中的所有项。为了达到目的，我们使用一个指针 current，该指针会一直记录我们当前正在打印的节点。每次打印完节点的值以后，将 current 指针指向下一个节点，然后再次打印，直到到达链表的末尾（下一个节点为 NULL）。

void print_list(node_t * head) { node_t * current = head; while (current != NULL) { printf("%d\n", current->val); current = current->next; } }

在链表的末尾添加一项

使用 current 指针来遍历链表的所有成员。首先将它设为 head，然后在每个循环中，把它指向链表的下一项，直到到达最后一项。接下来就可以在链表的末尾添加节点了。

void push(node_t * head, int val) { node_t * current = head; while (current->next != NULL) { current = current->next; } /* now we can add a new variable */ current->next = malloc(sizeof(node_t)); current->next->val = val; current->next->next = NULL; }

链表最好的使用案例是堆栈和队列，下面来实现一下：

在链表的开头添加一项（pushing to the list）

想要在链表的开头添加一项，我们需要：

创建新的项目并且给它赋值；使新的项指向链表头；将新的项设为链表头

这样可以高效地创建新的链表头，然后把链表剩下的部分连接到这个新的链表头。

由于使用一个函数来做这个操作，我们想要去修改 head 变量。为了达到目的，我们必须传入一个指向指针的指针变量，这样才可以修改指针本身。

void push(node_t ** head, int val) { node_t * new_node; new_node = malloc(sizeof(node_t)); new_node->val = val; new_node->next = *head; *head = new_node; }

删除链表的第一项（popping from the list）

为了 pop 出一个变量，我们需要这样做：

提取 head 指向的 next 项并保存；free head 节点；将步骤 1 保存的 next 项设为 head int pop(node_t ** head) { int retval = -1; node_t * next_node = NULL; if (*head == NULL) { return -1; } next_node = (*head)->next; retval = (*head)->val; free(*head); *head = next_node; return retval; }

删除链表的最后一项

删除链表的最后一项的方法与在链表末尾添加一项的很相似，除了一个区别——由于我们需要修改倒数第二项，因此实际上需要关注最后一项的前两项：

int remove_last(node_t * head) { int retval = 0; /* if there is only one item in the list, remove it */ if (head->next == NULL) { retval = head->val; free(head); return retval; } /* get to the last node in the list */ node_t * current = head; while (current->next->next != NULL) { current = current->next; } /* now current points to the last item of the list, so let's remove current->next */ retval = current->next->val; free(current->next); current->next = NULL; return retval; }

删除链表中的特定项

为了删除链表中的特定项，无论通过该项在链表中的索引还是该项的值，都需要检查所有项，一直向前查找直到找到需要删除项的前一项为止。这是因为需要修改前一个节点所指向的位置。

下面是算法：

遍历节点直到想要删除项的前一项为止；将想要删除的节点保存到一个临时指针中；将前一个节点的 next 指针指向想要删除节点的后一个节点；删掉使用临时指针的节点

由于还需要关注一些边界条件，所以请确保已经理解了下面的代码。

int remove_by_index(node_t ** head, int n) { int i = 0; int retval = -1; node_t * current = *head; node_t * temp_node = NULL; if (n == 0) { return pop(head); } for (int i = 0; i < n-1; i++) { if (current->next == NULL) { return -1; } current = current->next; } temp_node = current->next; retval = temp_node->val; current->next = temp_node->next; free(temp_node); return retval; }