数据结构与算法(3)_链表

数组与链表区别

从底层结构上来看,数组是一块连续的内存,对内存要求较高.而链表则是通过”指针”将一组零散的内存块串联起来.

常见的链表结构:单链表,双向链表和循环链表

单链表

链表通过指针将一组零散的内存块串联在一起,其中把内存块成为链表的”结点”,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址.我们把这个记录结点的指针叫做后继指针 next.

其中有两个结点比较特殊.习惯性的把第一个结点叫头结点,最后一个结点叫尾结点.其中头结点用来记录链表的基地址.尾结点指针指向一个空地址NULL,表示这是链接上的最后一个结点.

插入,删除操作

链表插入和删除数据是非常快速的.因为链表的存储空间并不是连续的,插入或删除只是改变前后指针的位置,如图:
//todo

查询操作

因为链表数据并非连续存储的,所以随机访问k个元素,无法像数组那样根据地址和下标通过寻址公式,直接计算出对应的内存地址,而是需要根据指针一个结点一个结点依次遍历,直到找到相应的结点.

循环链表

循环列表是一种特殊的单链表.循环链表的尾结点指针是指向链表的头结点.

和单链表相比,循环链表的优点是从链尾到链头比较方便.当要处理的数据具有环形特点时,就特别适用.比如约瑟夫问题.

双向链表

单链表只有一个方向,结点只有一个后继指针 next指向后一个结点.而双向链表,支持前后两个方向,还有一个前驱指针 prev指向前面的结点

双链表需要额外空间来存储后继结点和前驱结点,所以存储同样多的数据,双向链表比单链表占用更多的内存空间.

从结构上来看,双向链表可以支持O(1)时间复杂度的情况下找到前驱结点,正是这样的特点,双向链表在某些情况下的插入和删除操作比单链表更简单高效.

删除操作

删除结点中”值等于某个给定值”的结点

不管是单链表还是双向链表,为了完成上述操作,都需要从头结点开始依次遍历对比.尽管单纯的删除操作时间复杂度为O(1),但遍历的时间复杂度为O(n).根据加法法则,删除给点值的结点的总时间复杂度为O(n).

删除给点指针指向的结点

假设删除某个结点q,我们得知道其前驱结点.单链表为了找到前驱结点,就需要从头遍历.但是,对于双向链表来说,结点已经保存了前驱结点的指针.所以在此情况下单链表操作需要O(n)时间复杂度,双向链表为O(1)时间复杂度.

同理,插入操作双向链表可以在O(1)时间复杂度搞定,而单链表需要O(n)时间复杂度.

此外,对于一个有序的链表,双向链表也比单链表效率高一些.因为我们可以记录上次查询的位置p,每次查询时,根据查找的值与p的大小关系,决定往前还是往后查找,所以平均只需要查找一般的数据

这就是空间换时间的设计思想

双向循环链表

循环链表和双向链表结合一起就是双向循环列表

链表数组性能比较

如何轻松写出链表代码

理解指针或引用的含义

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量

警惕指针丢失和内存泄漏

指针是如何丢失的呢?我们以单链表插入操作为例分析.

如图,我们希望在a和b之间插入x,假设当前指针p指向a结点,

p->next = x; //将p的next指针指向x
x->next = p->next; //将x的指针指向b,此时指针已经丢失了
//因为在p->next 指针在进行完第一步操作后就已经不指向b了
//而是指向结点x.
//第二行代码相当于将x赋值给x->next,自己指向自己,整个链表也就断了

插入结点时一定要注意顺序.正确操作如下:

x->next = p->next;
p->next = x;

利用哨兵简化实现难度

针对链表的插入,删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理.利用哨兵结点来解决这个问题

如果我们引入一个哨兵结点,不管链表是不是空,head指针都会指向这个哨兵结点,我们把这种有哨兵结点的叫做带头链表,相反叫做不带头链表.

重点留意边界条件处理

检查链表代码是否正确的边界条件

• 如果链表为空时,代码能否正常工作.
• 如果链表只包含一个结点时,代码是否能正常工作
• 如果代码只包含两个结点时,代码是否能正常工作
• 代码再处理头结点和尾结点的时候,是否能正常工作

举例画图,辅助思考

多写多练,没有捷径

常见链表操作

• 单链表翻转
• 链表中环检测
• 两个有序的链表合并
• 删除链表倒数第n个结点
• 求链表的中间结点