链表知识点总结

article/2025/8/25 10:48:51

一、基本概念：

1.定义：

2.性质：

3.链表的分类：单链表：

双向链表

单链表和双向链表的区别：

双向链表的作用：

循环链表

二、链表的主要操作：

1.插入操作：

a.重要知识点：

b.完整代码：

2.删除操作：

a.重要知识点：

b.完整代码：

3.查找操作：

a.完整代码

三、链表和数组的区别

1.存储结构上：

2.操作上：

一、基本概念：

1.定义：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。每一个结构均含有元素和指向该元素后继结构的指针。

2.性质：

相连的元素之间通过指针进行链接
最后一个元素的后继指针为NULL
在执行的过程中链表的长度可以增加或者是减少
链表的空间可以按需要进行分配
没有存储空间的浪费，但是链表中的指针需要额外的内存开

3.链表的分类：
单链表：

根据下面的单链表结构图可以发现：

每个结点除了存储数据data外，还需要记录下个结点的地址，称为后继指针next。
单链表有两个特殊的结点，分别是第一个结点——头结点和最后一个结点——尾结点。
头结点：用来记录链表的基地址。
尾结点：尾结点的后继指针指向一个空地址NULL。

双向链表

根据下面的双向链表结构图可以发现：

每个结点除了存储数据data外，还会记录上一个结点和下一个结点的地址。

单链表和双向链表的区别：

单链表的结点只有一个指向，即后继指针next指向下一个结点。
双向链表的结点有两个指向，一个后继指针next指向下一个结点，还有一个前驱指针prev指向上一个结点。(所以增加了空间的需求，同时也是的插入和删除的开销增加一倍)

双向链表的作用：

1.使得倒序扫描链表很方便 2.简化了删除操作(原因：可以不再使用一个指向前驱结点的指针)

循环链表

根据下面的循环链表结构图可以发现：

循环链表的尾结点不指向空，而是指向头结点，类似一个环形结构。

二、链表的主要操作：

注：如下操作都是基于单链表，其他链表的操作都大差不差。

1.插入操作：

a.重要知识点：

1.在表头插入结点的时间复杂度为o(1),在表尾插入结点的时间复杂度为o(n)；

2.核心代码：s->next=p->next;p->next=s;

注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。

b.完整代码：

//单链表的插入，在链表的第i个位置插入x的元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*在L中第i个位置之前插入新的数据元素e，L的长度加1*/
LinkedList ListInsert(LinkedList L,int i,ElemType x) {LinkedList pre;                      //pre为前驱结点 pre = L;int tempi = 0;for (tempi = 1; tempi < i; tempi++) {pre = pre->next;                 //查找第i个位置的前驱结点 }Node *p;                                //插入的结点为pp = (Node *)malloc(sizeof(Node));p->data = x;             //主要代码p->next = pre->next;          //主要代码pre->next = p;return L;                           
}

2.删除操作：

a.重要知识点：

1.核心代码：q=p->next;p->next=q->next;

b.完整代码：

//单链表的删除，在链表中删除第i个数据元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，L的长度减1*/ 
LinkedList ListDelete(LinkedList L,int i)
{LinkedList p,q;                   int j=2; p = L->next;while(p->next&&j<i) {              //查找第i个位置 p=p->next;++j;}if(!(p->next)||j>i)			//第i个元素不存在printf("第i个元素不存在\n");q=p->next;				p->next=q->next;			//将q的后继赋值给p的后继 free(q);                    //释放q结点return L;
}

3.查找操作：

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需要平均比较(n+1)/2个元素结点。

a.完整代码

//单链表的查找
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：用e打印中第i个数据元素的值*/ void GetElem(LinkedList L){int i,j=1;		//j为计数器 int *e;LinkedList p;		//声明一结点p printf("请输入查找的位置:");scanf("%d",&i);p=L->next;		//让p指向链表L的第一个结点 while(p&&j<i)        //p不为空且到达i结点{p=p->next;		//让p指向下一个结点 ++j;	}if(!p||j>i)        //链表p为空否则链表长度过短printf("第i个元素不存在");		//第i个元素不存在 *e=p->data;				//取第i个元素的数据 printf("%d\n",*e);}

三、链表和数组的区别

1.存储结构上：

数组的存储空间是静态的，连续分布的，初始化的过程会造成空间浪费，过小右会是空间溢出的机会增多。
链表的存储空间是动态分布的，只要内存空间尚有空闲，就不会产生溢出；链表中每个节点除了域值外，还有链域（先一个节点的地址），这样空间利用率会变高。

数组中的数据在内存中按顺序存储的，而链表是随机存储的！

2.操作上：

原因：要访问数组中的元素可以按下标索引来访问，速度快，如果对他进行插入操作的话，就得平均要移动一半的节点，所以对数组进行插入操作效率很低！
由于链表是随机存储的，链表在插入，删除操作上有很高的效率（相对于数组），如果要访问链表中的某个元素的话，就得从链表的头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问的效率就比数组要低。

注：如果想要博主总结哪一章的知识点或者本章哪里不懂，可以在评论区留言哦！