【数据结构】线性表--链表

一.前情回顾

上篇文章讲述了动态顺序表及其实现，我们知道了动态顺序表在物理结构上是连续的，因此我们也认识到它的缺点：
①如果空间不足需进行增容，付出一定的性能消耗，并且可能存在一定的空间浪费。
②在进行某些插入或删除操作时，需要大量移动数据。这是因为相邻数据元素在物理存储结构上也是连续存储的，中间没有空隙。

因此本篇文章将讲述线性表的另一种表示方法：链表。

二.链表的概念

链表，即线性表的链式实现，指用一组任意连续或者不连续的存储单元存储数据，通过指针像链条一样链结各个元素的一种存储结构。
如图所示：

因此，对于每个数据元素，除了要存储自身信息，也要存储后继（下一个）数据元素的信息。这两部分合起来被称为结点。
每个结点包含两个域，一个是数据域：存储数据元素的信息；另一个是指针域：存储后继元素的位置信息。n个结点链结成一个链表。如图所示：

对于线性表，总要有头有尾，我们把链表中第一个结点的存储位置叫做头指针，最后一个结点置为NULL。由于每个结点的指针域只包含一个指向后继位置的指针，因此该链表又称单链表（单向链表）。

三.链表的实现

1.链表结点的结构：

在C语言中用结构体指针来存储后继结点的信息。

typedef int SLDataType;//结点的结构体
typedef struct SListNode
{SLDataType data;//数据域struct SListNode* next;//指向下一个结点的指针域，所以指针类型应该为struct SListNode*
}SLTNode;//起别名，将struct SListNode简写成SLTNode

2.申请新结点函数：

因为在插入操作中需要频繁申请结点，因此可以将申请结点的操作封装成一个函数。

//申请新结点
SLTNode* BuySListNode(SLDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));NewNode->data = x;NewNode->next = NULL;return NewNode;
}

3.尾插函数：

需要特别注意的是，凡是涉及修改链表，必须传二级指针，因为链表本身是用每个结点的指针链结而成的，作为参数传递时是一级指针，再将每个结点的地址作为实参传递，这是二级指针。

//尾插函数
//需要传二级指针，否则形参的改变不影响实参
void SListPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);//不能传空地址，否则解引用找链表头结点会报错//创建新结点SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));NewNode->data = x;NewNode->next = NULL;//链表为空，直接插入if (*pphead == NULL){*pphead = NewNode;}else{//需要找到最后一个结点才能尾插，因此先用一个cur结点标记当前所在位置SLTNode* cur = *pphead;while (cur->next != NULL)//循环结束走到最后一个结点{cur = cur->next;//让cur遍历到最后一个结点}if (NewNode == NULL){perror("malloc fail!");exit(1);}cur->next = NewNode;}
}

4.头插函数：

//头插函数
void SListPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);//创建新结点SLTNode* NewNode = BuySListNode(x);NewNode->next = *pphead;*pphead = NewNode;
}

5.尾删函数：

//尾删函数
void SListPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//如果只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL)//需要找到倒数第二个结点才能删除最后一个结点{cur = cur->next;}SLTNode* tmp = cur->next;free(tmp);tmp = NULL;cur->next = NULL;}
}

6.头删函数：

//头删函数
void SListPopFront(SLTNode** pphead)
{assert(pphead&&*pphead);//链表为空时不能删除SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}

7.在指定结点之前插入：

//在指定结点之前插入函数
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);//需要找到指定结点的前一个结点SLTNode* prev = *pphead;//可能第一个结点就是指定结点，此时相当于头插if (prev == pos){//直接调用头插函数SListPushFront(pphead, x);}else{while (prev->next != pos){prev = prev->next;}SLTNode* NewNode = BuySListNode(x);NewNode->next = prev->next;prev->next = NewNode;}
}

8.在指定结点之后插入：

//在指定结点之后插入函数
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* NewNode = BuySListNode(x);NewNode->next = pos->next;pos->next = NewNode;
}

8.删除指定结点：

//删除指定结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{SLTNode* prev = *pphead;//如果第一个结点就是要删除的结点if (prev == pos){//直接调用头删SListPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}SLTNode* tmp = prev->next;//tmp即要删除的结点prev->next = tmp->next;free(tmp);tmp = NULL;}
}

9.查找函数：

//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x)return cur;cur = cur->next;}//没找到或链表为空时，返回空指针return NULL;
}

10.销毁链表：

//销毁链表函数
void SListDestory(SLTNode** pphead)
{assert(pphead && *pphead);while (*pphead != NULL){SLTNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);tmp = NULL;}
}

四.全部源代码实现

1.头文件（声明动态顺序表的结构，操作等，起到目录作用）：

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;//结点的结构体
typedef struct SListNode
{SLDataType data;//数据域struct SListNode* next;//指向下一个结点的指针域，所以指针类型应该为struct SListNode*
}SLTNode;//起别名，将struct SListNode简写成SLTNode//打印函数（方便调试）
void SListPrint(SLTNode* phead);//申请新结点
SLTNode* BuySListNode(SLDataType x);//尾插函数
void SListPushBack(SLTNode** pphead, SLDataType x);//需要传二级指针，否则形参的改变不影响实参//头插函数
void SListPushFront(SLTNode** pphead, SLDataType x);//尾删函数
void SListPopBack(SLTNode** pphead);//头删函数
void SListPopFront(SLTNode** pphead);//在指定位置之前插入函数
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);//在指定位置之后插入函数
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x);//删除指定结点
void SListErase(SLTNode** pphead, SLTNode* pos);//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x);//销毁链表函数
void SListDestory(SLTNode** pphead);

2.源文件（具体实现各种操作）：

SList.c

#include"SList.h"//打印函数（方便调试）
void SListPrint(SLTNode* phead)
{assert(phead);SLTNode* cur = phead;while (cur != NULL)//循环结束走到空结点{printf(" %d ->", cur->data);cur = cur->next;}printf("NULL\n");
}//申请新结点
SLTNode* BuySListNode(SLDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));NewNode->data = x;NewNode->next = NULL;return NewNode;
}//尾插函数
//需要传二级指针，否则形参的改变不影响实参
void SListPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);//不能传空地址，否则解引用找链表头结点会报错//创建新结点SLTNode* NewNode = BuySListNode(x);//链表为空，直接插入if (*pphead == NULL){*pphead = NewNode;}else{//需要找到最后一个结点才能尾插，因此先用一个cur结点标记当前所在位置SLTNode* cur = *pphead;while (cur->next != NULL)//循环结束走到最后一个结点{cur = cur->next;//让cur遍历到最后一个结点}if (NewNode == NULL){perror("malloc fail!");exit(1);}cur->next = NewNode;}
}//头插函数
void SListPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);//创建新结点SLTNode* NewNode = BuySListNode(x);NewNode->next = *pphead;*pphead = NewNode;
}//尾删函数
void SListPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//如果只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL)//需要找到倒数第二个结点才能删除最后一个结点{cur = cur->next;}SLTNode* tmp = cur->next;free(tmp);tmp = NULL;cur->next = NULL;}
}//头删函数
void SListPopFront(SLTNode** pphead)
{assert(pphead&&*pphead);//链表为空时不能删除SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//在指定结点之前插入函数
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);//需要找到指定结点的前一个结点SLTNode* prev = *pphead;//可能第一个结点就是指定结点，此时相当于头插if (prev == pos){//直接调用头插函数SListPushFront(pphead, x);}else{while (prev->next != pos){prev = prev->next;}SLTNode* NewNode = BuySListNode(x);NewNode->next = prev->next;prev->next = NewNode;}
}//在指定结点之后插入函数
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* NewNode = BuySListNode(x);NewNode->next = pos->next;pos->next = NewNode;
}//删除指定结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{SLTNode* prev = *pphead;//如果第一个结点就是要删除的结点if (prev == pos){//直接调用头删SListPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}SLTNode* tmp = prev->next;//tmp即要删除的结点prev->next = tmp->next;free(tmp);tmp = NULL;}
}//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x)return cur;cur = cur->next;}//没找到或链表为空时，返回空指针return NULL;
}//销毁链表函数
void SListDestory(SLTNode** pphead)
{assert(pphead && *pphead);while (*pphead != NULL){SLTNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);tmp = NULL;}
}

3.测试文件（测试各个函数的功能）

test.c

#include"SList.h"//测试尾插函数
void test01()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);
}//测试头插函数
void test02()
{SLTNode* phead = NULL;SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);SListPushFront(&phead, 4);SListPrint(phead);
}//测试尾删函数
void test03()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);SListPopBack(&phead);SListPrint(phead);SListPopBack(&phead);SListPrint(phead);SListPopBack(&phead);SListPrint(phead);
}//测试头删函数
void test04()
{SLTNode* phead = NULL;SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);SListPushFront(&phead, 4);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);
}//测试查找函数
void test05()
{SLTNode* phead = NULL;SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);SListPushFront(&phead, 4);SListPrint(phead);SLTNode* ret1 = SListFind(phead, 2);if (ret1 != NULL)printf("找到了\n");elseprintf("未找到\n");SLTNode* ret2 = SListFind(phead, 57);if (ret2 != NULL)printf("找到了\n");elseprintf("未找到\n");
}//测试在指定结点之前插入
void test06()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);//在第三个结点前插入57//先查找到第三个结点SLTNode* pos1 = SListFind(phead, 3);SListInsert(&phead, pos1, 57);SListPrint(phead);//在第一个结点前插入79//先查找到第一个结点SLTNode* pos2 = SListFind(phead, 1);SListInsert(&phead, pos2, 79);SListPrint(phead);//在最后一个结点前插入36//先查找到最后一个结点SLTNode* pos3 = SListFind(phead, 4);SListInsert(&phead, pos3, 36);SListPrint(phead);
}//测试在指定结点之后插入
void test07()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);//在第三个结点后插入57//先查找到第三个结点SLTNode* pos1 = SListFind(phead, 3);SListInsertAfter(&phead, pos1, 57);SListPrint(phead);//在第一个结点后插入79//先查找到第一个结点SLTNode* pos2 = SListFind(phead, 1);SListInsertAfter(&phead, pos2, 79);SListPrint(phead);//在最后一个结点后插入36//先查找到最后一个结点SLTNode* pos3 = SListFind(phead, 4);SListInsertAfter(&phead, pos3, 36);SListPrint(phead);
}//测试删除结点函数
void test08()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);//删除第一个结点SLTNode* pos1 = SListFind(phead, 1);SListErase(&phead, pos1);SListPrint(phead);//删除第三个结点SLTNode* pos2 = SListFind(phead, 3);SListErase(&phead, pos2);SListPrint(phead);//删除最后一个结点SLTNode* pos3 = SListFind(phead, 4);SListErase(&phead, pos3);SListPrint(phead);
}//测试销毁函数
void test09()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);SListDestory(&phead);SListPrint(phead);
}
int main()
{//test01();//test02();//test03();//test04();//test05();//test06();//test07();//test08();test09();return 0;
}

五.单链表和顺序表的对比

1.存储分配方式

顺序表采用一段连续的存储单元存储数据元素。
单链表采用一组任意的存储单元存储元素。

2.时间性能

查找：
顺序表按值查找O(n)，按索引查找O(1)。
单链表O(n)。
插入和删除：
顺序表O(n)。
单链表O(1)。

3.空间性能

顺序表需要预分配空间，小了需再次分配，大了造成空间浪费。
单链表需要时申请结点空间。

4.总结

若线性表需要频繁查找，宜采用顺序存储结构。若频繁插入和删除，宜采用链式存储结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构 。而游戏中的玩 家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不大合适了，链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。
总之，线性表的顺序存储和链式存储各有优缺点，不能简单说哪个好，哪个不好，需根据实际情况做出选择。