手撕408|数据结构之链表(3)

通知：冷月目前提供免费408 1对1辅导，有需要的同学可以加我微信：lengyue408。  

“ 链表是408算法题的热门出题点，大家千万要熟练其操作。”

手撕408系列之数据结构之链表，冷月出品必是精品，大家好，我是学长冷月。

昨天咱们介绍了线性表中顺序表（数组）的相关知识，今天我们接着学习线性表的另一个经典数据结构—链表。

定义

除了第一个元素，其他元素有且只有一个直接前驱；除了最后一个元素，其他元素有且只有一个直接后继；并且在逻辑上相邻，物理上不一定相邻的线性表。符合这样的数据结构称为链表。如下图所示：

基础术语

链表中有几个常用到的术语，大家先了解一下。其实这类术语大家切记不要死记硬背。在题目中遇到的时候，反复翻看，熟练后自然就可以记住。

首节点：有效元素的第一个节点

尾节点：有效元素的最后一个节点

头结点：首节点前面的节点

头指针：指向头结点的指针

尾指针：指向尾节点的指针

分类

单链表

最简单的链表，每个一个节点内分为数据域和指针域，如下图所示：

双链表

相对于单链表，双链表有两个指针域。一个指向前驱，一个指向后继，如下图所示：

循环链表

最后一个节点的指针域指向第一个节点，如下图所示：

静态链表

利用一个二维数组，指针域就是数组的下标，如下图所示：

其特点有：1、预先分配一块连续的内存空间；2、插入、删除无需移动元素。

与顺序表之间的关系

1、存取方式

数组既可以随机存取也可以顺序存取，而链表只能从前往后顺序存取。

2、存储方式

顺序表逻辑上相邻、物理上也相邻

链表逻辑上相邻、物理上不一定相邻

3、查找方式

按值查找：数组无序，则都为O(n);数组有序，可以采用折半查找，O(logn)。

按下标查找：数组可以采用随机存取，时间复杂度为O(1)；而链表从前往后查找，时间复杂度O(n)。

明天别忘了来做题！

关注下方“学长冷月”可获得更多408答题技巧及资料。

请帮冷月点一下旁边的在看，再点一个赞,一键三连支持一下！您的每一次点击都是对冷月莫大的鼓励，谢谢！！

点“在看”给我一朵小黄花