【数据结构】链表（linked list）

一、链表的介绍

二、单链表

1. 单链表的初始化

2. 单链表的插入

（1）动态申请一个节点

（2）头插法

（3）尾插法

（4）按照位置来插入

（5）在地址之前插入

（6）在地址之后插入

3. 单链表的建立

（1）头插法建立单链表

（2）尾插法建立单链表

4. 单链表的删除

（1）头删

（2）尾删

（3）按位置删

（4）删除当前地址的结点

（5）删除当前地址之后的结点

5. 单链表的查找

（1）查找结点地址

（2）单链表的按位查找

（3）单链表的按值查找

6、单链表的销毁

三、双链表

1. 申请新结点

2. 初始化

3. 双链表的插入

4. 双链表的建立

4. 双链表的删除

5. 双链表的打印

6. 双链表的销毁

四、总结

一、链表的介绍

我们知道线性表的顺序存储结构称为顺序表，那么线性表的链接存储结构则称为链表。链表是一种物理存储结构上非连续、非顺序的存储结构，它可以用任意存储单元存放线性表的元素，在写存储单元可以连续，也可以不连续，甚至可以零散分布在内存中的任意位置。二为了表示元素之间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储官该元素的后继元素地址信息，所以数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表结构示意图：

链表的分类：

实际中链表的结构非常多样，但总体上可以分为6种基础链表结构，它们可以相互可以组成共8种链表：

按方向：

按有无头结点（也叫做有无哨兵结点）：

按循环：

结构最简单的是无头的单向非循环单链表；
结构最复杂的是有头的双向循环链表。

而下面要详细介绍的是无头的单向非循环单链表。因为无头的单向非循环单链表结构比较简单，但一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。实际应用得比较多，比如一些OJ题。

也要介绍有头的双向循环链表，因为这种链表一般会用在单独存储数据。而实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但也有许多优势，比较好实现。

二、单链表

下面的单链表是指无头的单向非循环单链表。

单链表是通过一个一个的结点来存储数据的，每个结点结构只含有一个数据域和一个指针域，数据域用来存储数据，指针域用来存储下一个结点的地址。

下面是单链表结点的定义：

typedef int DataType;
typedef struct ListNode
{DataType data;//数据域struct ListNode* next;//指针域
}Node;

结构示意图：

1. 单链表的初始化

这种无头的单向非循环单链表的初始化比较简单，只需要生成一个空的结点指针即可以了。即：

SListNode* first = NULL;

2. 单链表的插入

单链表的插入有多种方法：头插法、尾插法、中间插。其中中间插入又包含了可以按照位置（所在的次序）来插入和按照结点地址（指针）来插入两种情况。

（1）动态申请一个节点

想要插入，就必须要先申请一个新的结点，用来存放要插入的值。加入要插入一个值为x的数据，那么现在就需要申请一个单链表结点，其中的数据域用来存放值x，指针域先置空。则C语言实现如下：

//动态申请一个值为x的结点空间
Node* ApplyNode(DataType x)
{//申请空间Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL){perror("malloc fail\n");return NULL;}//赋值newNode->data = x;newNode->next = NULL;return newNode;
}

（2）头插法

头插法即是在链表的表头进行插入。对于无头的单向非循环单链表的头插法，分为两种情况：空表和非空表。但对于这里而言，它们是一样的代码。由于初始化时传递到是一个空的结点指针，这里头插函数传递的就应该是一个指向该空结点的地址（传二级指针），因为这里要改变头指针的值，所以必须使用传址调用。

需要注意的是，当生成了一个新结点后，必须先将新结点中的指针域部分进行赋值，即：“ newNode->next = *phead ”，再将头指针指向这个新结点，即：“ *phead = newNode; ”。

C语言实现如下：

// 单链表的头插
void PushFront(Node** phead, DataType x)
{assert(phead);//由于这里的phead是头指针的地址，所以一定不为空，需断言Node* newNode = ApplyNode(x);//产生新结点newNode->next = *phead;*phead = newNode;
}

（3）尾插法

尾插法是指在链表的表尾依次插入。尾插法就必须分为两种情况：空表和非空表，它们的情况是不同的。对于空表，由于只有一个空指针，所以只需要将申请的新结点的地址赋值给它就行了；对于非空表，就需要找到这个链表最后一个结点的地址：假设为tail，然后将申请的新结点地址赋给该结点的指针域。

则C语言实现如下：

//单链表尾插
void PushBack(Node** phead, DataType x)
{assert(phead);//这里phead指的是头指针的地址，它一定不为空，所以必须断言Node* newNode = ApplyNode(x);if (*phead == NULL){*phead = newNode;}else{//找尾Node* tail = *phead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}
}

（4）按照位置来插入

按照位置来插入和顺序表的插入差不多。就是先给定一个位置（第几个位置，即一个整数），在这个位置插入所给的元素值x。

则C语言实现如下：

//在第i个位置插入x
void ListPush(Node** phead, int i, DataType x)
{assert(phead);Node* newNode = ApplyNode(x);if (*phead == NULL && i == 1 ){//空表的处理*phead = newNode;return;}Node* prev = NULL;Node* cur = *phead;int count = 1;while (cur&&count < i){prev = cur;cur = cur->next;count++;}if (cur == NULL){printf("插入位置不合理，插入失败！\n");return;}newNode->next = cur;prev->next = newNode;
}

（5）在地址之前插入

给定一个地址pos，在该地址之前插入一个新结点。

则C语言实现如下：

//在pos的前面插入
void InsertBefore(Node** phead, Node* pos, DataType x)
{assert(phead);assert(pos);if (pos == *phead){//头插PushFront(phead, x);}else{Node* prev = *phead;while (prev->next != pos){prev = prev->next;}Node* newNode = BuySListNode(x);newNode->next = pos;prev->next = newNode;}
}

（6）在地址之后插入

给定一个地址pos，在该地址之后插入一个新结点。

则C语言实现如下：

//在pos的后面插入
void InsertAfter(Node** phead, Node* pos, DataType x)
{assert(phead);assert(pos);if (pos == *phead){//头插PushFront(phead, x);}else{Node* cur = *phead;while (cur != pos){cur = cur->next;}Node* newNode = ApplyNode(x);newNode->next = pos->next;cur->next = newNode;}
}

3. 单链表的建立

建立单链表有两种方法：头插法和尾插法。知道了单链表的插入方法，那么建立方法也就和简单了。这里假设要将一个数组的数据依次插入到链表中去。

（1）头插法建立单链表

还未建立单链表之前，只有一个空的头指针，所以建立单链表只需顺序遍历数组，利用单链表的插入的头插法函数将数组的数据依次传入就可以了。则C语言实现如下：

//单链表的建立--头插法建立
void CreatListByFront(Node** phead, DataType arr[], int sz)
{for (int i = 0; i < sz; i++){//通过头插法建立PushFront(phead, arr[i]);}
}

（2）尾插法建立单链表

和头插法建立单链表一样，调用尾插法的函数就可以实现尾插法建立单链表了。则C语言实现如下;

//单链表的建立--尾插法建立
void CreatListByBack(Node** phead, DataType arr[], int sz)
{for (int i = 0; i < sz; i++){//通过尾插法建立PushBack(phead, arr[i]);}
}

4. 单链表的删除

和插入一样，删除也有多种情况。

（1）头删

头删即删除链表中的第一个结点，这里要注意的是必须将要删除的结点的空间释放，否则会出现内存泄漏。

头删需要注意的是所删除的链表一定不能是空链表，所以在对所传递的二级指针（存放头指针地址指针）进行断言的同时，也要对头指针是否为空进行断言操作。则C语言实现如下：

//单链表头删
void PopFront(Node** phead)
{assert(phead);assert(*phead);Node* first = *phead;*phead = (*phead)->next;free(first);//释放第一个结点的空间first = NULL;
}

（2）尾删

和头删一样，需要断言头指针和存放头指针的地址的二级指针。尾删也需要考虑空表的情况，然后将最后的一个结点删除。因为空表是进行无法删除操作的。这里也必须将所删结点的空间释放，并将所删结点的上一个结点的指针域置空。

但是要删除最后一个结点就必须找到倒数第二个结点的地址，如果当链表只有一个结点的情况倒数第二个结点的地址就无法找到，那么就可以只返回一个空指针NULL就可以了。则C语言实现如下：

// 单链表的尾删
void PopBack(Node** phead)
{assert(phead);assert(*phead);if ((*phead)->next == NULL){*phead = NULL;}else{Node* prev = NULL;Node* tail = *phead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

（3）按位置删

给一个位置 i，删除第 i 个位置，C语言实现如下：

//删除第i个位置的结点（0<i）
void Delete(Node** phead, int i)
{assert(phead);assert(*phead);if (i == 1){PopFront(phead);//头删return;}Node* cur = *phead;Node* prev = NULL;int count = 1;while (cur != NULL && count < i){prev = cur;cur = cur->next;count++;}	if (cur == NULL){printf("删除位置不合理\n");}else{prev->next = cur->next;free(cur);cur = NULL;}
}

（4）删除当前地址的结点

给定链表中的一个结点地址，该地址可以通过单链表的查找中的查找地址来获得，然后将这个结点删除，则C语言实现如下：

//删除pos位置
void Delete(Node** phead, Node* pos)
{assert(phead);assert(pos);if (pos == *phead){//头删PopFront(phead);}else{Node* prev = *phead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

（5）删除当前地址之后的结点

给定链表中的一个结点地址，删除该结点之后的一个结点，。C语言实现如下;

//单链表删除pos位置之后的结点
void DeleteAfter(Node* pos)
{assert(pos);Node* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

5. 单链表的查找

查找的方式也分多种，一种是给定值来查找链表结点的地址，这是单链表最主要的查找，另一种则是和顺序表的按位查找一样，当然也还有和顺序表一样的按值查找。

（1）查找结点地址

查找值为x的结构体地址，则C语言实现如下：

//单链表查找，查找值为x的结构体地址
Node* ListFind(Node* head, DataType x)
{Node* cur = head;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

（2）单链表的按位查找

//按位查找
DataType ListGet(Node* head, int i)
{assert(head);Node* cur = head;int count = 1;while (cur && count < i){cur = cur->next;count++;}if (cur == NULL){printf("位置不合理，查找失败\n");return EOF;}return cur->data;
}

（3）单链表的按值查找

/按值查找
DataType ListLocate(Node* head, DataType x)
{assert(head);Node* cur = head;int count = 1;while (cur){if (cur->data == x){return count;}cur = cur->next;count++;}printf("链表中不存在该元素\n");return -1;
}

6、单链表的销毁

通过遍历单链表，逐步销毁各个结点。C语言实现如下：

//单链表的销毁
void Destroy(Node** phead)
{Node* cur = *phead;while (cur){Node* tmp = cur->next;free(cur);cur = tmp;}*phead = NULL;
}

三、双链表

在这里要介绍的是带头双向循环链表。这是图示：

它的结点结构体定义：

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//存储数据struct ListNode* prev;//指向前一个结点的指针 --- 前驱指针域struct ListNode* next;//指向后一个结点的指针 --- 后继指针域
}ListNode;

以下是带头双向循环链表中的比较重要的操作。

1. 申请新结点

给定一个值x，向内存申请一个新的双链表的结点结构体指针将x存储。这里需要注意的是需要将新结点的前驱指针域和后继指针域都置空，防止野指针。C语言实现如下：

//建立一个结点
ListNode* ApplyNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");return NULL;}node->prev = NULL;node->next = NULL;node->data = x;return node;
}

2. 初始化

带头双向循环链表，由于是带哨兵位头结点的所以需要初始化。该类型的初始化是将哨兵位头结点的前驱指针域和后继指针域都指向它自己。并将产生的结点返回。C语言实现如下：

//初始化
ListNode* ListInit()
{ListNode* phead = ApplyNode(-1);//假设给个-1phead->prev = phead;phead->next = phead;return phead;
}

3. 双链表的插入

双链表的插入只需要完成下图中的4个操作就可以了。

C语言实现如下：

//双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = ApplyNode(x);newnode->prev = pos->prev;//1pos->prev->next = newnode;//2newnode->next = pos;//3pos->prev = newnode;//4
}

由于这是带头循环链表，所以由此可以得到头插和尾插：

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListInsert(pHead->next, x);
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListInsert(pHead, x);
}

4. 双链表的建立

建立双链表只需要将给定数组的元素逐步插入即可。C语言实现如下：

//建立双链表链表
void ListCreate(ListNode* pHead, LTDataType arr[], int sz)
{assert(pHead);for (int i = 0; i < sz; i++){ListInsert(pHead, arr[i]);}
}

4. 双链表的删除

双链表的删除只需要完成下图中的4个操作就可以了。

C语言实现如下：

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* tmp = pos;pos->prev->next = pos->next;//1pos->next->prev = pos->prev;//2
}

那么，也可以得到头删和尾删：

// 双向链表头删
void ListPopFront(ListNode* pHead)
{ListErase(pHead->next);
}// 双向链表尾删
void ListPopBack(ListNode* pHead)
{ListErase(pHead->prev);
}

5. 双链表的打印

打印需要遍历链表，以再次回到头结点转为终止条件。C语言实现如下：

// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){printf("%d", cur->data);cur = cur->next;}printf("\n");
}

6. 双链表的销毁

遍历双链表，逐步释放空间，以再次回到哨兵头结点作为停止条件。C语言实现如下：

// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* next = cur->next;free(cur);cur = next;}free(pHead);
}

虽然双链表的结构比较复杂，但它的代码都简单，比较好实现。