前言：
线性表是我们最常用的一种数据结构，线性表包含顺序表和链表，顺序表典型应用就是我们常用的ArrayList，链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结单链表的实现以及使用并且对比单链表与顺序表的优缺点，确定其使用功能场景，且该篇文章总结的单链表是不带有头结点的实现方式，若是想要看带有头结点的单链表的实现请看这里： java实现单链表—含头结点，且该篇文章与另一篇含头结点的实现单链表的文章第一部分均是重复的，若看可忽略，说到这里必须要写下含不含头结点的区别，带有头结点是为了更好的实现单链表的功能，带有头结实现的insert、remove等方法相比于不带头结点的单链表会更简洁一些，此外，学习不带头结点的和带有头结点的单链表是没有区别的。
一、相关概念
第一部分主要介绍下和单链表有关的相关概念，这里给出的概念都是书本上的官方定义，并不是作者胡诌的，为什么给出这些官方的定义呢 ？因为笔者认为官方给出的定义，是对一个概念最本质的解释，它的解释经过了时间的考验，被认为是解释的最合理深入简明扼要的。
1.什么是线性表
线性表是由n个数据元素构成的有限序列，n为线性表的表长，当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱，终端节点没有后继，其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。
2.什么是顺序表
采用顺序存储结构存储数据元素的线性表被称为顺序表，顺序表，要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的，当在顺序表的第i（0<=i<=n）插入一个数据元素时，需要后移n-i+1个数据元素，当删除第i个元素时需要移动n-i个数据元素。java实现顺序表
3.什么是链表
采用链式存储结构存储数据元素的线性表被称为链表，链表不要求逻辑上相邻的数据元素内存上必须相邻，链表的每个节点都包含两部分，一部分是数据域用以存储数据，一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时，被称为单链表。
4.单链表、双链表、循环单链表、循环双链表
当链表的结点只有一个指针域时被称为单链表，循环单链表是单链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。
当链表的结点有两个时，一个指向前驱，一个指向后继这种链表便是双链表，循环双链表是双链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。
所有的链表的实现均有两种方式，一种是带有头结点，一种是不带有头结点的实现方式，两种实现略有区别。
5.头结点和首结点
首节点：真正存储第一个数据元素的结点被称为首节点。
头结点：当链表采用带头结点方式实现时，会创建一个数据域为null的节点，该节点的指针域存储的指针指向首节点的指针，他的唯一作用是标识链表的开始，带有头结点的链表更易于操作。
6.常见的栈和队列与线性表的关系
栈和队列也是常见的数据结构，但是栈和队列并不是线性表的一种，线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢，栈是被限制了只能在一端进行插入和删除操作的线性表，所以栈的特性是先入后出，队列是被限制了只能在一端插入另一端删除的线性表，所以队列的特性是先入先出。既然栈和队列都是特殊的线性表，那么栈和队列自然就可以使用线性表来实现了，通常可以使用线性表中的顺序表和队列来实现栈和队列。
二、实现过程
第二部分总结单链表中常用的方法，比如insert、remove、get、length、isEmpty、display等方法的实现。对方法实现的思路加以总结，点名该方法实现的核心思想。
1.提供结点类：Node
实现单链表、结点类则是前提。根据单链表的定义我们可以知道，单链表中每个结点都是包含了两部分，一部分是数据域，一部分是指针域。数据域存储数据，指针域存储指向下一个结点的引用，所以Node应该有两个属性，然后我们还需要提供必需的构造方法，同时我们有两处策略处理Node的两个属性，要么声明成public类型的变量，这样便于操作，要么声明成private的私有变量，这样更符合面向对象的思想，我们操作时需通过get、set方法操作，这里使用将两个属性声明成public的方式，实现如下：
public class Node { public Object object;//数据域 public Node next;//指针域 public Node(){ } public Node(Object object){ this.object = object; } public Node(Node next){ this.next = next; } public Node(Object object,Node next){ this.object = object; this.next = next; } @Override public String toString() { return "Node{" + "object=" + object + ", next=" + next + '}'; } }
2.实现单链表：NoHeadLinkedTable
在头结点的单链表里，我们需要声明一个头结点，用以存储指向首节点的指针，同样为了插入、删除等方法的实现，在不带头结点的单链表中我们也需要提供一个结点—首结点，不过该结点是可以存储数据的，这个结点也就是我们的首结点（头结点不存储数据，首结点存储数据），但是我们无需去提供构造方法初始化首结点，直接使用默认的空参构造即可，在需要插入的地方我们再手动创建首结点的实现。
/** * 这是不带头结点的单链表 * 说明：带头结点的标志是，第一个结点(头结点)只存储指向下一个节点的指针，其数据域为空 * 此处的firstNode是首结点，他的数据域和指针域都是可以存储数据的。 * @author pcc * @version 1.0.0 * @className NoHeadLinkedTable * @date 2021-04-15 15:31 */ public class NoHeadLinkedTable { private Node firstNode; }
3.提供根据下标插入方法：insert(int i,Object object)
链表下标从0开始，这里的i指的是待插入位置的下标，该方法的实现思路就是找到i-1位置的数据元素，然后将i-1的next的属性交给这个新的数据元素的next属性，再将新的数据元素交给i-1位置数据元素的next即可，此外需要注意的是首结点的元素需要单独判断下。
/** * * @param i 下标 * @param object 待存储对象 */ public void insert(int i,Object object) throws Exception{ if(i<0 || i>length()) throw new Exception("下标不合法"); if(null == object) throw new Exception("数据不可为空"); //不使用头结点时，首结点特殊处理，使用头结点的意义就是方便处理 //从这里也可以看到，不使用头结点，需要单独处理首结点的数据 if(i==0) if(length()==0){ firstNode = new Node(object); return; }else{ firstNode = new Node(object,firstNode); return; } Node node = firstNode; int j = 0; while(node.next !=null && j<i-1) { j++; node = node.next; } node.next = new Node(object,node.next); }
上面是不带有头结点单链表的插入实现，下面再展示下带有头结点的时的插入实现，做个对比。
//提供插入方法：根据下标插入 /** * 思路： * 1.寻找i位置的前一个数据元素，若是找不到则说明i输入有误（） * 2.在指定位置插入object * @param i * @param object */ public void insert(int i,Object object) throws Exception{ if(i<0 || i>length() ||object==null) throw new Exception("下标或者值无效"); Node node = head; int j = 0; while(node.next!=null && j<i){ node = node.next; j++; } node.next = new Node(object,node.next); }
对比以上两处代码，核心的区别就是i==0时的这一串逻辑，这串逻辑就是单独处理在头部插入时的逻辑的代码，总结可以看出不带有头结点时，实现只需要多关注下再头部插入的问题即可，其他位置插入时操作没有区别的。
4.头插法、尾插法：insertHead(Object object)、insertHail(Object object)
头插法和尾插法的实现也很简单，我们可以直接调用根据下标插入的方法，在下标为0的位置插入就是头插，在下标为length()-1的位置插入就是尾插法，此外还可以直接根据头结点尾结点进行操作，因为上篇文章是使用根据下标实现的头插法和尾插法，这里就使用另外一种方式实现。
//头部插入 public void insertHead(Object object) throws Exception{ firstNode = new Node(object,firstNode); }
以上是头插法的代码，思路：直接生成一个新的首结点，将以前的首结点作为新首结点的next属性，若是以前首结点就是null，那么新首结点的next属性也为null。以下是尾插法的实现：
//尾部插入 public void insertTail(Object object) throws Exception{ if(length()==0) firstNode = new Node(object); else{ Node node = firstNode; while(node.next!=null){ node = node.next; } node.next = new Node(object); } }
以上便是尾插法的实现代码，思路：同样是先判断链表是否为空（使用length方法判断是一样的效果），为空我们直接创建首结点即可，此时首结点就是尾结点。不为空我们就需要遍历了，找到next属性为null的结点，该节点就是尾结点（尾结点的标志就是尾结点的next属性为null），然后在尾部插入即可。
5.提供判空(isEmpty）、长度(length)、打印(display)、清空(clear)等方法
这些方法都比较简单，直接将代码展示在这里
//判空 public boolean isEmpty(){ return firstNode.object==null; } //链表长度 public int length(){ if(firstNode!=null){ Node node = firstNode; int i = 0; while(node!=null){ i++; node = node.next; } return i; } else return 0; } //输出链表 public void display(){ if(firstNode!=null){ Node node = firstNode; while(node != null){ System.out.println("结点："+node.object); node = node.next; } } } //清空链表 public void clear(){ if (firstNode!=null){ firstNode.object = null;firstNode.next=null; } }
在这里我们就可以初步测试下根据下标插入、头插法、尾插法等其他方法了，测试场景如下，根据代码，我们猜测输出结果应该是：唐僧、孙悟空、沙和尚、猪八戒、白龙马，效果如下图，可以看到如预期所想，这些方法的实现没有问题，其他场景笔者也有测试这里就不一一展示测试结果了。
6.提供根据下标获取数据元素的方法：get(int i)
下标从0开始，此处i代表下标为i的元素，实现思路：若i是0则返回首结点，否则遍历链表寻找下标为i的数据元素。
//根据下标获取方法 public Object get(int i) throws Exception{ if(i<0 || i>length()-1) throw new Exception("下标不合法"); if(length() == 0) throw new Exception("链表为空"); //单独处理首结点情况 if(i==0) return firstNode.object; Node node = firstNode; int j =0; while(node.next != null && j < i){ j++; node = node.next; } return node.object; }
然后测试下上方代码是否有效，我们获取里阿尼宝的第一个和最后一个，然后再从链表中间位置任意位置获取一个，看看输出是否正确，如下：
根据上方测试代码和输出，我们可以看到根据下表获取的方法实现是没有问题的，其他场景笔者也有测试这里就不一一展示测试结果了。
7.提供根据下标删除的方法：remove(int i)
这里的i指的都是链表元素的下标，删除的思路：判断i的值是否是首结点，如果是直接将以前的第二个结点变成首结点，这样就实现了删除首结点，若不是，则需要遍历寻找下标为i-1的数据元素，将该元素的指针域指向下标为i+1的数据元素即可实现删除，代码如下：
//根据下标删除方法 public void remove(int i) throws Exception{ if(i<0 || i>length()-1) throw new Exception("下标不合法"); if(length() == 0) throw new Exception("链表为空"); //特殊处理i为0的时候。 if(i==0){ firstNode = firstNode.next; return; } //遍历时，与带有头结点的链表不同的是，无头结点的链表 Node node = firstNode; int j = 0; while(node.next != null && j< i-1){ j++; node =node.next; } //找到的是下标为i-1的元素 node.next = node.next.next; }
然后我们测试下该方法，我们将刚刚根据下标获取到的三个元素删了，若是正常剩下的元素应该是孙悟空、猪八戒，如下图：
根据上方的输出内容我们可以看到，输出结果都是正常的。
8.提供获取某数据元素第一次出现的下标方法：indexOf(Object object)
该方法是获取某数据元素第一次出现的下标位置，所以我们需要遍历链表，当链表的元素与目标元素相等则返回下标，否则继续遍历，若遍历完成依然没有找到该与目标元素相等的数据元素，则说明链表不含有该元素，返回-1，代码如下：
//获取某元素第一次出现的下标 public int indexOf(Object object) throws Exception{ if(object==null) throw new Exception("数据不合法"); if(length() == 0) throw new Exception("链表为空"); Node node = firstNode; int j = 0; //这里找的是当前元素下标，插入、删除都是获取的i-1的下标 //区别是获取当前元素时，我们应该判断的是node！=null，获取i-1时，我们 //应该判断node.next != null。 while(node!=null ){ if(node.object.equals(object)) return j; j++; node = node.next; } return -1; }
测试该代码的实现是否正确，我们使用猪八戒来测试，若返回下标时1，说明该方法实现没有问题 ，结果如下图，可以看到返回的下标确实是1，说明该方法实现正确。
9.附上单链表实现的完整代码
/** * 这是不带头结点的单链表 * 说明：带头结点的标志是，第一个结点(头结点)只存储指向下一个节点的指针，其数据域为空 * 此处的firstNode是首结点，他的数据域和指针域都是可以存储数据的。 * @author pcc * @version 1.0.0 * @className NoHeadLinkedTable * @date 2021-04-15 15:31 */ public class NoHeadLinkedTable { private Node firstNode; /** * * @param i 下标 * @param object 待存储对象 */ public void insert(int i,Object object) throws Exception{ if(i<0 || i>length()) throw new Exception("下标不合法"); if(null == object) throw new Exception("数据不可为空"); //不使用头结点时，首结点特殊处理，使用头结点的意义就是方便处理 //从这里也可以看到，不使用头结点，需要单独处理首结点的数据 if(i==0) if(length()==0){ firstNode = new Node(object); return; }else{ firstNode = new Node(object,firstNode); return; } Node node = firstNode; int j = 0; while(node.next !=null && j<i-1) { j++; node = node.next; } node.next = new Node(object,node.next); } //头部插入 public void insertHead(Object object) throws Exception{ firstNode = new Node(object,firstNode); } //尾部插入 public void insertTail(Object object) throws Exception{ if(length()==0) firstNode = new Node(object); else{ Node node = firstNode; while(node.next!=null){ node = node.next; } node.next = new Node(object); } } //根据下标获取方法 public Object get(int i) throws Exception{ if(i<0 || i>length()-1) throw new Exception("下标不合法"); if(length() == 0) throw new Exception("链表为空"); //单独处理首结点情况 if(i==0) return firstNode.object; Node node = firstNode; int j =0; while(node.next != null && j < i){ j++; node = node.next; } return node.object; } //根据下标删除方法 public void remove(int i) throws Exception{ if(i<0 || i>length()-1) throw new Exception("下标不合法"); if(length() == 0) throw new Exception("链表为空"); //特殊处理i为0的时候。 if(i==0){ firstNode = firstNode.next; return; } //遍历时，与带有头结点的链表不同的是，无头结点的链表 Node node = firstNode; int j = 0; while(node.next != null && j< i-1){ j++; node =node.next; } //找到的是下标为i-1的元素 node.next = node.next.next; } //获取某元素第一次出现的下标 public int indexOf(Object object) throws Exception{ if(object==null) throw new Exception("数据不合法"); if(length() == 0) throw new Exception("链表为空"); Node node = firstNode; int j = 0; //这里找的是当前元素下标，插入、删除都是获取的i-1的下标 //区别是获取当前元素时，我们应该判断的是node！=null，获取i-1时，我们 //应该判断node.next != null。 while(node!=null ){ if(node.object.equals(object)) return j; j++; node = node.next; } return -1; } //判空 public boolean isEmpty(){ return firstNode.object==null; } //链表长度 public int length(){ if(firstNode!=null){ Node node = firstNode; int i = 0; while(node!=null){ i++; node = node.next; } return i; } else return 0; } //输出链表 public void display(){ if(firstNode!=null){ Node node = firstNode; while(node != null){ System.out.println("结点："+node.object); node = node.next; } } } //清空链表 public void clear(){ if (firstNode!=null){ firstNode.object = null;firstNode.next=null; } } }
三、总结
1.含头结点的单链表与不含头结点的单链表区别
两者在性能上是没有区别的，区别在于根据下标插入、删除等方法的实现。略有区别，不含头结点时，我们需要对首结点进行单独的判断，这样会相对复杂一些，但是在总体的时间复杂度上是可以忽略不计的，因此在实际中开发中，这两种实现应该是都可以使用，没有太强的优劣之分。
2.链表的缺点
线性表的两种实现顺序表、链表。相比于顺序表，链表的缺点就是查找元素比较慢，查找元素的时间复杂度是O(n),而顺序表的时间复杂度是O(1)，在查找上顺序表要优于链表,链表查找慢，就是它的缺点了。
3.链表的优点
顺序表在指定下标x位置插入元素，组需要后移n-x+1个元素，若是删除下标为x的数据元素，则需要向前移动n-x个数据元素，但是链表则不需要移动任何元素，链表需要做的只是找到对应的元素将指针域中的指针进行更新即可。链表的插入和删除的时间复杂度可以看成O(1)，而顺序表插入和删除操作的都是O(n).所以链表的优点就是插入和删除比较快。
4.如何使用链表
所以综合链表的优点与缺点我们可以发现，顺序表更适合存储“静态”型数据，而链表更适合存储“动态”型数据，何为动态型呢，就是那些插入、删除操作比较频繁的数据。这类数据更适合使用链表存储。而数据结构不易改变的数据使用顺序表存储更合适。顺序表可类比java中的ArrayList，链表可类比java中的LinkedList。这两者都是顺序表与链表的典型应用。
