DSA_04：链表

数组：用一组连续的内存空间，来存储一组具有相同类型的数据。

链表：通过“指针”将一组零散的内存块串联起来使用。

 

数组和链表，各有各的用武之地，各有个的优缺点。

 

链表有哪些形态呢？

　　1. 单链表

　　2. 循环链表

　　3. 双链表

　　4. 双向循环链表

 

关于链表的插入、删除、查找性能，以及与数组的对比，这里不再啰嗦。

链表增删的细节操作这里也不再说明。

 

一些注意问题：

　　1. 可以利用哨兵简化实现难度

　　2. 重点留意边界条件处理

　　　　如果链表为空时，代码是否能正常工作？

　　　　如果链表只包含一个结点时，代码是否能正常工作？

　　　　如果链表只包含两个结点时，代码是否能正常工作？

　　　　代码逻辑在处理头结点和尾结点的时候，是否能正常工作

　　3. 举例画图，辅助思考

 

关于链表的各种操作，算法等很多，可前往力扣刷题。

一些常用的链表算法操作：

　　1. 单链表反转

　　2. 链表中环的检测

　　3. 两个有序的链表合并

　　4. 删除链表倒数第n个结点

　　5. 求链表的中间结点

 

题1：请看力扣 第206题

题2：请看力扣 第141题

题3：请看力扣 第21题

题4：请看力扣 第19题

题5：请看力扣 第876题