手撕408|数据结构之链表(3)
通知：冷月目前提供免费408 1对1辅导，有需要的同学可以加我微信：lengyue408。
手撕408系列之数据结构之链表，冷月出品必是精品，大家好，我是学长冷月。
昨天咱们介绍了线性表中顺序表（数组）的相关知识，今天我们接着学习线性表的另一个经典数据结构—链表。
定义
除了第一个元素，其他元素有且只有一个直接前驱；除了最后一个元素，其他元素有且只有一个直接后继；并且在逻辑上相邻，物理上不一定相邻的线性表。符合这样的数据结构称为链表。如下图所示：
基础术语
链表中有几个常用到的术语，大家先了解一下。其实这类术语大家切记不要死记硬背。在题目中遇到的时候，反复翻看，熟练后自然就可以记住。
首节点：有效元素的第一个节点
尾节点：有效元素的最后一个节点
头结点：首节点前面的节点
头指针：指向头结点的指针
尾指针：指向尾节点的指针
分类
单链表
最简单的链表，每个一个节点内分为数据域和指针域，如下图所示：
双链表
相对于单链表，双链表有两个指针域。一个指向前驱，一个指向后继，如下图所示：
循环链表
最后一个节点的指针域指向第一个节点，如下图所示：
静态链表
利用一个二维数组，指针域就是数组的下标，如下图所示：
其特点有：1、预先分配一块连续的内存空间；2、插入、删除无需移动元素。
与顺序表之间的关系
1、存取方式
数组既可以随机存取也可以顺序存取，而链表只能从前往后顺序存取。
2、存储方式
顺序表逻辑上相邻、物理上也相邻
链表逻辑上相邻、物理上不一定相邻
3、查找方式
按值查找：数组无序，则都为O(n);数组有序，可以采用折半查找，O(logn)。
按下标查找：数组可以采用随机存取，时间复杂度为O(1)；而链表从前往后查找，时间复杂度O(n)。
明天别忘了来做题！
关注下方“学长冷月”可获得更多408答题技巧及资料。
请帮冷月点一下旁边的在看，再点一个赞,一键三连支持一下！您的每一次点击都是对冷月莫大的鼓励，谢谢！！
点“在看”给我一朵小黄花
