目录
一、链表
1.1. 链表的概念及结构
1.2. 链表的实现
专栏：数据结构(Java版)
个人主页：手握风云
一、链表
1.1. 链表的概念及结构
链表是⼀种物理存储结构上⾮连续存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的。与火车类似，火车头、车厢与每一届车厢之间由火车链连接起来。在物理上，链表是不一定连续的，但在逻辑上一定是连续的。
如下图所示，链表的结构分为两个域，一个域用来储存数据，另一个域用来储存下一个节点(类似于火车的一节车厢)的地址。 与顺序表不同的是，链表的地址在物理上不连续，但在逻辑上是连续的。最后一个节点相当于“车尾”，里面存的地址为null。这就是一个单向、不带头、非循环的链表。类似地，还有双向、带头、循环的链表。但考试考最多的说就是单链表。
什么是带头的链表呢？如下图所示，第一个节点可以存任何数据，但存取的数据是没有意义的，唯一的作用就是起到一个“排头兵”的作用。不带头的链表呢，相当于它的head会变的，比如我们把第一个节点删掉，那么第二个节点就会成为head。
那么什么又是循环链表呢？如下图所示，最后一个节点指向了第一个节点或第二个节点，就可以构成循环链表，但一般情况下，我们都是指向第一个节点。
1.2. 链表的实现
接下来我们要通过代码来实现链表，我们就可以定义一个MySingleList类，链表当中有很多的节点，基于面向对象的思想，我们可以使用内部类来定义我们的节点。
public class MySingleList { static class ListNode{ private int val; private ListNode next; public ListNode(int val) { this.val = val; } //因为不知道下一个节点是谁，所以这里的构造函数的参数里不写next。 } public ListNode head;//表示当前链表的头节点 public int listSize;} 链表的基础已经写好了，下面要实行链表的增、删、查、改。我们可以把这些方法写在一个接口里面。接口里面的方法默认都是public，并且不需要具体的实现。然后我们在MySingleList类里面对这些方法进行重写。
public interface Ilist { //头插法 void addFirst(int data); //尾插法 void addLast(int data); //任意位置插⼊第⼀个数据节点为0 号下标 void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 boolean contains(int key); public void remove(int key); //删除所有值为 key的节点 public void removeAllKey(int key); //得到单链表的⻓度 int size(); public void clear(); public void display();}public class MySingleList implements Ilist{ static class ListNode{ private int val; private ListNode next; public ListNode(int val) { this.val = val; } //因为不知道下一个节点是谁，所以这里的构造函数的参数里不写next。 public ListNode head;//表示当前链表的头节点 } @Override public void addFirst(int data) { } @Override public void addLast(int data) { } @Override public void addIndex(int index, int data) { } @Override public boolean contains(int key) { return false; } @Override public void remove(int key) { } @Override public void removeAllKey(int key) { } @Override public int size() { return 0; } @Override public void clear() { } @Override public void display() { }}我们也可以自己创建一个链表：
public ListNode head;//表示当前链表的头节点 public void CreateList(){ ListNode node1 = new ListNode(11); ListNode node2 = new ListNode(22); ListNode node3 = new ListNode(33); ListNode node4 = new ListNode(44); //这些数据之间没有连续性 node1.next = node2; node2.next = node3; node3.next = node4; //node4已经是最后一个节点了，不需要管最后一个next this.head = node1;//这样可以从第一个节点开始去遍历我们的数组 }public class Main { public static void main(String[] args) { MySingleList mySingleList = new MySingleList(); mySingleList.CreateList(); System.out.println("========="); }}我们在对象实例化这里打一个断点来进行调试。开始的时候，头节点是空的，运行到下一行时，我们的val的值和next的地址都被CreateList方法串联起来了。
了解了next的引用原理之后，我们就可以遍历链表来对里面的数据进行打印。我们通过上面的display方法来实现，那我们如何通过head的引用从第一个节点指向第二个节点呢？
//基本变量通过自增的方式来赋值int a = 10;a = a + 1;//同理，引用变量也可以采用上述方法head = head.next; @Override public void display() { while(head != null){ System.out.print(head.val+" "); head = head.next; } System.out.println(); }我们来对这个方法进行调试一下，如下图所示，当head不为空时，进入while循环，当head.next指向第二个节点时val的值变为了22，next的地址也指向了第二个节点。当head指向最后一个节点时，地址变为null，跳出while循环。
运行结果如下：
但这种写法也有致命的缺点，如果说这个方法有返回值呢，head遍历完我们的链表之后，head引用变为了null，返回的值也会成一个null，如果我们再用ListCode创建一个cur变量，head引用保持不动，把head的引用赋值给cur，再让cur去遍历链表。
比如我们通过size方法来获取链表的节点数，就可以这样写：
@Override public int size() { ListNode cur = head; int count = 0; while(cur != null){ cur = cur.next; count++; } return count; }
再比如我们去写contains方法去判断链表里是否存在关键字：
@Override public boolean contains(int key) { ListNode cur1 = head; while(cur1 != null){ if(cur1.val == key){ return true; } cur1 = cur1.next; } return false; } System.out.println(mySingleList.contains(44)); System.out.println(mySingleList.contains(45)); 
可能有的老铁在写这个方法会写出cur1.next != null，因为最后一个节点的next为null，当cur1走到最后节点时，不满足cur1.next != null，相当与根本没有遍历完这个数组。
下面我们将要进行对链表里的数据进行增删查改。我们先来实现头插和尾插。我们如果向把一个node节点(里面存的数据是10)插入head节点前面之后，node节点就变成了head节点。我们可以通过下面两行代码来实现这个过程。这里千万不能把两行代码写反，因为这样就会使得node.next指向自己。
node.next = head;//先让node.next的地址指向node1head = node;//再通过head引用指向node，就能把node变成头节点
public void addFirst(int data) { ListNode node = new ListNode(data); if(head == null){ head = node;//相当于插入进一个空的链表 }else{ node.next = head; head = node; } } public static void main(String[] args) { Ilist mySingleList = new MySingleList(); mySingleList.addFirst(10); mySingleList.addFirst(20); mySingleList.addFirst(30); mySingleList.addFirst(40); mySingleList.display(); }
对于尾插的实现，与头插不同的是，我们需要先找出链表的最后一个节点，然后再让cur.next = node。如果说初始的链表是空的情况下，则cur= null，cur.next就会出现空指针异常。我们就需要参考contains方法来寻找链表的尾部。
@Override public void addLast(int data) { ListNode node = new ListNode(data); //表示链表为空 if(head == null) { head = node; return; } //找到链表的尾巴 ListNode cur = head; while (cur.next != null) { cur = cur.next; } cur.next = node; }下面我们来实现比较复杂的在任意位置插入一个节点：为了方便理解，我们给每个节点都编上号。如果说我们要把新的节点插入到2号位置，那么新的节点就会变成2号位置。但我们的cur是不能走两步的，因为插入之后2号位置不知道前面的节点是谁，这个链表是单向的，所以cur不能往回走，也就是要走index-1步。我们可以通过两行代码来实现这一过程。
node.next = cur.next;cur.next = node;对于cur需要走index-1步的过程，我们可以重新写一个方法来实现。然后我们就可以把新节点插入到链表中了。
private ListNode findIndex(int index){ ListNode cur = head; int count = 0; while(count != index-1){ cur = cur.next; count++; } return cur; }public void addIndex(int index, int data) { ListNode node = new ListNode(data); ListNode cur = findIndex(index); node.next = cur.next; cur.next = node; listSize++; }过程确实有点复杂，不懂的老铁可以去画画图去理解。到这里，看似我们的过程已经结束了，但我们需要考虑其他的一些问题。如果我们在0号位置插或者在5号位置插，那么就相当于头插和尾插了，我们就可以直接调用addFirst和addLast方法。那如果我们在-1、-2位置插呢？这时就会越界访问。我们就需要写一个方法来检查访问是否合法。
if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } private void checkIndexOfAdd(int index){ if(index<0 || index>size()){ throw new RuntimeException("插入的位置不合法,index="+index); } }public class IndexOutOf extends RuntimeException{ public IndexOutOf() { } public IndexOutOf(String message) { super(message); }}try { mySingleList.addIndex(6,99); }catch (IndexOutOf e) { e.printStackTrace(); }
接下来我们看删除元素。删除并不是简单的跳过这个节点，还要把要删除的节点前一个和后一个连接起来。那我们先找到要删除元素的前一个元素，我们又该如何找到要删除的节点呢？
cur.next = del.next;
rivate ListNode findNode(int key) { ListNode cur = head; while (cur.next != null) { if(cur.next.val == key) { return cur; } cur = cur.next; } return null; }通过上面这个方法，我们就可以找到我们要删除的节点。注意，我们不能写成cur != null，因为cur.next就会空指针异常。如果我们没有找到，就返回null。但是，我们需要考虑一下，我们要删除第一个数据，cur已经在第一个节点，那么cur.next就不会对第一个节点进行判断，从而就不会删除。
@Override public void remove(int key) { if(head == null) { return; } if(head.val == key) { head = head.next; listSize--; return; } ListNode cur = findNode(key); if(cur == null) { System.out.println("没有你要删除的数据"); return; } ListNode del = cur.next; cur.next = del.next; listSize--; }