首页 > 代码库 > [考研系列之数据结构]线性表之链表
[考研系列之数据结构]线性表之链表
1.链表分类
通过线性表概述，我们知道了链表这样一种数据结构，它又分成三类，分别是- 单向链表
- 循环链表
- 双向链表
单向链表
单向链表的指针域只有一个指向下一个节点的指针，需要注意几点:
1.头指针——指向第一个节点
2.最后一个结点的指针指向NULL
3.头结点——在链表的第一个结点之前附设一个结点，它的数据域为空
所以，我们看到:
单向链表为空的<=>链表有且只有一个头结点<=>头结点的指针指向NULL
循环链表
循环链表和单向链表最大的不同就是:最后一个结点的指针不再指向NULL而是指向第一个结点。那么:
循环链表为空的<=>链表有且只有一个头结点<=>头结点的指针指向自己
双向链表
双向链表的指针域有两个，分别为:prior和next:
prior指向前一个结点，next指向后一个结点。
对于双向链表:
双向链表为空的<=>链表有且只有一个头结点<=>头结点的prior和next指针都指向自己
2.关于链表操作
对所有数据结构的操作最基本的都是增删改查，让我们对单向链表的增删改查进行一些分析:
增
在单向链表中insert一个结点，我们分为两种情况
insert的结点在表尾
insert的结点不在表尾
insert的结点不在表尾
如果insert的结点在表尾的话，我们要进行的操作就是：
| 遍历链表到表尾，找到最后一个结点 | O(n) |
| 将最后一个结点的指针从NULL改成指向需要insert的结点 | O(1) |
所以很明显，整个操作的算法复杂度是O(n)
如果insert的结点是在第i个结点之后，而且i<n，整体操作如下:
| 遍历链表，找到第i个结点 | O(n) |
| 让需要插入结点的指针指向第i+1个结点 | O(1) |
| 将第i个结点的指针指向需要插入的结点 | O(1) |
整个算法复杂度也是O(n)
删
删除操作也分两种情况
delete的结点是最后一个
delete的结点不是最后一个
delete的结点不是最后一个
对于delete的结点是最后一个的情况，操作:
| 遍历找到最后一个结点和它的前一个结点 | O(n) |
| 将它的前一个结点的指针指向NULL | O(1) |
| [如果结点是存储在堆上，可以使用free释放此结点空间] | O(1) |
而如果delete的结点是第i个，而且i<n，相应的操作
| 遍历找到第i个结点和它的前一个结点i-1 | O(n) |
| 将i-1结点的指针指向第i+1个结点[即将i的指针的值赋给i-1的指针] | O(1) |
| 将第i个结点的指针指向NULL | O(1) |
| [如果结点是存储在堆上，可以使用free释放此结点空间] | O(1) |
改
对于结点数据域的改操作是建立在查操作之上的，只要找到了这个结点，那么对于数据域的修改就只是赋值那么简单了。
查
单向链表由于只能从头结点开始向后遍历，所以找到第i个结点也肯定会遍历前面的i-1个结点，关于遍历的算法复杂度:
(数学公式不好机打只好手写了)
扩展
1.两个链表的归并
有两个链表La和Lb，它们同递增或同递减，求一个新的链表Lc，它是La和Lb的元素合并，且Lc也具有相同的递增递减性质
首先，我们明确Lc的长度是
Lc.length=La.length+Lb.length
我们先定义三个指针Pa、Pb和Pc，
初始状态：
Pa指向La的头结点，Pb指向Lb的头结点，Pc指向Lc的头结点
结束状态：
Pa=Pb=Pc=NULL（他们都分别遍历了三个链表）
中间过程：
从初始状态开始，三个指针分别指向三个链表的头，下面用一段伪代码去描述算法(递减):
while(Pa!=NULL&Pb!=NULL)
{
if(Pa->next->data>=Pb->next->data)
{
Pc->next->data=Pa->next->data;
Pa=Pa->next;
}
else
{
Pc->next->data=Pb->next->data;
Pb=Pb->next;
}
Pc=Pc-next;
}
{
if(Pa->next->data>=Pb->next->data)
{
Pc->next->data=Pa->next->data;
Pa=Pa->next;
}
else
{
Pc->next->data=Pb->next->data;
Pb=Pb->next;
}
Pc=Pc-next;
}
算法的核心就是:每次将Pa和Pc指向的数据比较，如果Da(Data Of La)>=Db(Data Of Lb)，则Dc=Da，Da指向下一个结点的数据，这样下次循环就是下一个Da和上一次的Db比较了，每次循环Lc长度都会增加1，增加的数据是Pa和Pb指向元素中较大的。
2.多项式的表示和相加
见严书P39
最后，链表更多的是提供一种数据的表示方法，以后的树和图也会使用链式表示的方法，但是单独作为链表还是会有很多小的知识点和技巧的，更多的可以看我以前的一篇博客:
http://blog.csdn.net/acidsweet/article/details/8642689
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。