单链表简介

单链表及其节点
链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，
一个域用于数据元素的存储，另一个域是指向其他单元的指针。
这里具有一个数据域和多个指针域的存储单元通常称为结点（node）

一种最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，
指针域用于指向下一个具有相同结构的结点。
因为只有一个指针结点，称为单链表

图片.png

链表的第一个结点和最后一个结点，分别称为链表的首结点和尾结点。
尾结点的特征是其 next 引用为空（null）。
链表中每个结点的 next 引用都相当于一个指针，指向另一个结点，
借助这些 next 引用，我们可以从链表的首结点移动到尾结点。
在单链表中通常使用 head 引用来指向链表的首结点，由 head 引用可以完成对整个链表中所有节点的访问。

图片.png

在单链表中还需要注意的一点是，由于每个结点的数据域都是一个 Object 类的对象，因此，每个数据元素并非真正如图中那样，而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。

与数组类似，单链表中的结点也具有一个线性次序，即如果结点 P 的 next 引用指向结点 S，则 P 就是 S 的直接前驱，S 是 P 的直接后续。
单链表的一个重要特性就是只能通过前驱结点找到后续结点，而无法从后续结点找到前驱结点。

单链表的查询操作

在单链表中进行查找操作，只能从链表的首结点开始，通过每个结点的 next 引用来一次访问链表中的每个结点以完成相应的查找操作

例如需要在单链表中查找是否包含某个数据元素 e，则方法是使用一个循环变量 p，起始时从单链表的头结点开始，
每次循环判断 p所指结点的数据域是否和 e 相同，如果相同则可以返回 true，否则让p指向下一个节点，继续循环直到链表中所有
结点均被访问，此时 p 为 null

图片.png

关键操作：
1.起始条件：p = head;
2.结束条件：
找到：e.equals(p.getData())==true
未找到 p == null
3.p指向下一个结点: p = p.getNext();

缺点：逐个比较，频繁移动指针，导致效率低下
注意：如果要查询第i个元素的值，无法直接定位，也只能从首结点开始逐个移动到第i个结点，效率同样低下。

添加操作
在单链表中数据元素的插入，是通过在链表中插入数据元素所属的结点来完成的。
对于链表的不同位置，插入的过程会有细微的差别。
中间、末尾的添加过程其实是一样的，关键是在首部添加，会有不同，会改变整个单链表的起始结点。

图片.png

以添加中间结点为例
**
1.指明新结点的后继 s.setNext(p.getNext()); 或者 s.next = p.next
**
2.指明新结点的前驱（其实是指明前驱结点的后继是新结点）p.setNext(s) 或者 p.next = s;
**
添加节点不需要移动元素，只需要修改元素的指针即可，效率高。
但是如果需要先查询到添加位置再添加新元素，因为有逐个查询的过程，效率不高。

删除操作
类似添加操作

图片.png

在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。一个带头结点的单链表实现线性表的结构图如图所示。