数据结构04链表_wx619474981d7fe的技术博客_51CTO博客

1 链表存在的意义

线性表的顺序存储结构最大的缺点就是插入和删除时需要移动大量元素，这显然是需要耗费大量的时间，链式存储结构就是为了解决这个问题而存在。

为什么当插入和删除时，就要移动大量元素。仔细分析后，发现原因就在于响铃元素的存储位置具有邻居关系。它们编号是1，2，3，·····，n，它们在内容中的位置也是挨着的，中间没有空隙，当然就无法快速插入，而删除后，当中就会留出空隙，问题就出在这里。

2 链表的定义

2.1 文字定义

在顺序结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素外，还要存储它的后继元素的存储地址。

为了表示每个数据元素aia_iai与其直接后继数据元素ai+1a_{i+1}ai+1之间的逻辑关系，对数据元素aia_iai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域，指针域中存储的信息称作指针或链。这两部分信息组成数据元素aia_iai的存储映像称为结点。

线性表的链式存储结构：nnn个结点(aja_jaj的存储映像)链结成一个链表，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

头指针：链表中第一个结点的存储位置。

尾指针：线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）

头结点：在单链表的第一个结点前附设一个结点，称为头结点。（头结点的数据域可以不存储任何信息，也可以存储如线性表长度等附加信息，头结点的指针指向第一个结点的指针。）

头指针与头结点的异同：

头指针
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。

头指针具有标志作用，所以常用头指针冠以链表的名字。

无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点
头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）。

有了头结点对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了。

头结点不一定是链表必需要素。

2.2 代码定义

用存储示意图表示单链表如图所示：

C语言描述：

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; // 定义LinkList

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

3 单链表的读取、插入与删除

3.1 单链表的读取

获取链表第i个数据的算法思路：

声明一个指针p指向链表第一个结点，初始化j从1开始。
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
若到链表末尾p为空，则说明第i个结点不存在。
否则查找成功，返回结点p的数据。

实现代码如下：

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e){
    int j;
    LinkList p; /* 声明一结点p */
    p = L->next; /* 让p指向链表L的第一个结点 */
    j = 1; /*  j为计数器 */
    while (p && j<i){ /* p不为空或者计数器j还没有等于i时，循环继续 */
        p = p-> next; /* 让p指向下一个结点 */
        ++j;
    }
    if (!p || j>i){ /*  第i个元素不存在 */
        return ERROR;
    }
    *e = p->data; /*  取第i个元素的数据 */
    return OK;
}

3.2 插入

设存储元素e的结点为s,要实现结点p、p-＞next和s之间逻辑关系的变化，只需将结点s插入到结点p和p-＞next之间即可。

数据结构04链表_数据_07

根本用不着惊动其他结点，只需要让s-＞next和p-＞next的指针做一点改变即可。

s->next = p->next; // 将p的后继结点复制给s的后继
p->next = s; // 将s复制给p的后继

也就是说让p的后继结点改成S的后继结点，再把结点S变成p的后继结点。

数据结构04链表_链表_08

单链表第i个数据插入结点的算法思路：

声明一指针p指向链表头结点，初始化j从1开始；
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，在系统中生成一个空节点s；
将数据元素e复制给s->data；
单链表的插入标准语句 s->next = p->next; p->next=s;
返回成功。

C实现代码算法如下：

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while(p && j<i){  /* 寻找第i个结点 */
        p = p->next;
        ++j;
    }
    if(!p || j>i){  /* 第i个元素不存在 */
        return ERROR;
    }
    
    S = (LinkList)malloc(sizeof(Node));   /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = p->next;  /* 将p的后继结点赋值给s的后继  */
    p->next = s;  /* 将s赋值给p的后继 */
    return OK;
}

malloc函数的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是再内存中找了一小块空地，准备用来存放数据e的s结点。

3.3 单链表的删除

设存储元素aia_{i}ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。

我们所要做的，实际上就是—步，p-＞next＝p-＞next-＞next，用q来取代p-＞next，即是

q = p->next;
p->next = q->next; //将q的后继复制给p的后继

单链表第j个数据删除结点的算法思路：

声明—指针p指向链表头结点，初始化j从1开始;
当j＜i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1;
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，将预删除的结点p->next赋值给q；
单链表的删除标准语句p->next=q->next;
将q结点中的数据赋值给e，作为返回；
释放q结点；
返回成功。

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e){
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p->next && j<i){  /* 遍历寻找第i个元素 */
        p = p-> next;
        ++j;
    }
    if(!(p->next) || j>i){  /* 第i个元素不存在 */
        return ERROR;
    }
    q = p->next;
    p->next = q->next;  /* 将q的后继赋值给p的后继 */
    *e = q->data;  /* 将q结点中的数据给e */
    free(q);  /* 让系统回收此结点，释放内存 */
    return OK;
}

free函数的作用是让系统回收一个Node结点，释放内容。

4 单链表的整表创建与删除

4.1 单链表的整表创建

创建单链表的过程就是—个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路：

声明一指针p和计数器变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
1. 生成一新结点赋值给p；
2. 随机生成一数字赋值给p的数据域p->data;
3. 将p插入到头结点与前一新结点之间。

头插法：始终让新结点在第一的位置。

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L,int n){
    LinkList p;
    int i;
    srand(time(0));  /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;  /*  先建立一个带头结点的单链表 */
    for(int i=0; i<n; i++){
        p = (LinkList)malloc(sizeof(Node));  /*  生成新结点 */
        p->data = rand()%100 + 1;   /*  随机生成100以内的数字 */
        p->next = (*L) -> next;
        (*L)->next = p;  /*  插入到表头 */
    }
}

尾插法：每次新结点都插在终端结点的后面。

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n) 
{
	LinkList p,r;
	int i;
	srand(time(0));                      /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
	r=*L;                                /* r为指向尾部的结点 */
	for (i=0; i<n; i++) 
	{
		p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;           /*  随机生成100以内的数字 */
		r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
		r = p;                            /* 将当前的新结点定义为表尾终端结点 */
	}
	r->next = NULL;                       /* 表示当前链表结束 */
}

L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不4断地变化结点，而L则是随着循环增长为—个多结点的链表。

4.2 单链表的整表删除

当我们不打算使用这个单链表时我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下:

声明一指针p和q；
将第一个结点赋值给p；
循环：
1. 将下一结点复制给q；
2. 将q复制给p。

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L){
    LinkList p,q;
    p = (*L)->next;   /*  p指向第一个结点 */
    while(p){  /*  没到表尾 */
        q = p->next;
        free(p);
        p=q;
    }
    (*L)->next = NULL;  /* 头结点指针域为空 */
    return OK;
}

5 顺序存储结构与链式存储结构的优缺点

存储分配方式：

顺序存储结构用一段连续存储单元依次存储线性表的数据元素；
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能：

查找
- 顺序存储结构O(1)O(1)O(1)
- 单链表O(n)O(n)O(n)
插入和删除
- 顺序存储结构需要平均移动表长一半的元素，时间复杂度O(n)O(n)O(n)
- 单链表在找出位置的指针后，插入和删除时间复杂度仅为O(1)O(1)O(1)

空间性能：

顺序存储结构需要预分配存储空间，分大了浪费，分小了易发生上溢
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

一些经验性的结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构。

1 链表存在的意义

2 链表的定义

2.1 文字定义

2.2 代码定义

3 单链表的读取、插入与删除

3.1 单链表的读取

3.2 插入

3.3 单链表的删除

4 单链表的整表创建与删除

4.1 单链表的整表创建

4.2 单链表的整表删除

5 顺序存储结构与链式存储结构的优缺点

Recommend

巴西暂停销售不附送充电器的iPhone机型，并对苹果处以234万美元罚款

Don't be silly, of course you can use EVs in cold weather

日耗电3万度 EUV光刻机要关机省电？台积电回应了

Free Icons - Open-source vector icons in 16 styles | Product Hunt

8月投融资汇总：持续聚焦产业链关键技术

关于《远距离通信记录》，被「大人糖」戳到了！

.NET 反向代理-YARP - 一事冇诚

又一款高性价比机型即将到来 realme新机值得期待

Sony unveils 'world's first' robotic pan-tilt-zoom full-frame mirrorless camera

字节跳动A/B实验背后的秘密：样本量计算

About Joyk