单链表的Java实现代码:
第三章 线性表
线性表的链式存储结构
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195523553-936000635.png)
n个结点链结成一个链表,即为线性表(a1, a2, ..., an)的链式存储结构,因为链表的每个节点中只包含一个指针域,所以叫做单链表。
头指针
链表中第一个结点的存储位置叫做头指针,最后一个结点指针为NULL
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195524584-615335630.png)
头结点
有时,为了更方便的对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头结点。头结点的数据域可不存储任何信息,也可存储如线性表的长度等附件信息,头结点的指针域指向第一个结点的指针。
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195525334-1024954637.png)
头指针和头结点的异同
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195526475-144580701.png)
线性表链式存储结构代码描述
若线性表为空表,则头结点的指针域为NULL
简化的链表表示图如下:
1. 头指针型的单链表
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195526881-1799709905.png)
2. 带有头结点的单链表
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195527162-1674619070.png)
3. 空链表
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195527865-1942371148.png)
C语言中可用结构指针来描述单链表,如下:
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195529569-2029440401.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195530350-1188810555.png)
单链表的读取:最坏情况的时间复杂度为O(n)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195532209-100672711.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195534084-140178773.png)
其核心思想就是“工作指针后移”。
单链表的插入与删除
插入:时间复杂度O(n)
1. 插入链表中段
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195535162-1265450986.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195536053-1112933297.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195536740-1157496104.png)
2. 插入到表头或表尾
与上同
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195537537-1975611674.png)
算法思路与代码实现:
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195538350-67694195.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195540115-1249450959.png)
删除:时间复杂度O(n)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195541584-2069491278.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195541928-246403637.png)
算法思路与代码实现:
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195542865-1012345375.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195545819-1828868924.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195548334-1413583283.png)
注:
如果不知道第i个元素的指针位置,单链表数据结构在插入和删除操作上,与线性表的顺序存储结构是没太大优势的。但如果,我们希望从第i个位置插入10个元素,对顺序存储结构来说,每一次插入都需要移动n-i个元素,每次都是O(n);而对单链表来说,我们只需要在第一次找到第i个位置的指针,此时为O(n),接下来只是简单的通过赋值移动指针而已。
综上,对于插入或删除数据越频繁的操作,单链表的效率优势越是明显。
单链表的整表创建
1. 头插法
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195548662-1752143762.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195549319-2050355637.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195551287-1346574674.png)
2. 尾插法
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195553803-740298184.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195555115-596439163.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195555819-1602897519.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195556553-22616022.png)
单链表的整表删除
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195557178-138021983.png)
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195558803-504015142.png)
单链表结构与顺序存储结构优缺点
![](https://images2015.cnblogs.com/blog/1007623/201704/1007623-20170427195559990-316794156.png)
经验总结:
1. 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。
2. 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间的大小问题。