前言
自古以来数据结构界就分为九重天，据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬，受万人敬仰。
但是这谈何容易，因为每一重天都有神兽把守，想要冲破每一重天都必须收服守护的神兽才行。
守护九重天的神兽分别是：数组、字符串、栈、队列、链表、树、散列表、堆、图。可见他们的战斗力也是逐层增强的。想只凭靠自身的能力拿下他们谈何容易。
不过大家不必惊慌，我这里有一本上古秘籍《Java小子怒闯数据结构九重天》，里面有每一重天神兽的攻略。只要修炼者仔细钻研里面的每一篇，对九重天了如指掌之后，冲破这九重天也是易如反掌的。
今天为大家带来第五重天的攻略！
1.🌀链表的基础知识
链表是一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。
简单来说链表是实现线性表的链式存储结构的基础。
链表是一种通过指针串联在一起的线性结构，每一个节点是由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
节点情况如下：
数据域 指针域
date next
上面的介绍都是单链表相关的，除了单链表我们还有双向链表，循环链表等。
双链表
双链表顾名思义就是比单链表高级了一点，一个双链表的结点在单链表的基础上又增加了一个指针，这个指针指向它的前一个结点
节点情况如下：
指针域 数据域 指针域
prior date next
循环链表
之前的链表都是条状的，循环链表是头尾相连了，就是将链表的尾部与头部连接起来。有因为条状链表有单链表与双链表之分，所以循环链表也有两种分别是：循环单链表与循环双链表
对于循环单链表我们一般设置尾指针这样操作效率会更高。
对于循环双链表我们头结点的prior结点指向最后一个节点，尾结点的next指针指向头结点，以形成循环双链表。
2.🌀Java实例化链表
想要实例化链表就得先创建一个链表的结构类，这个类代表的是每一个节点结构。
之前提到过每一个节点是由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
所以链表节点结构定义为：
class ListNode { int val; // 节点值 ListNode next; // 后继节点引用 ListNode(int x) { val = x; } }
使用定义的这个链表结构我们可以自己构造一个链表如下：
// 实例化节点
ListNode n1 = new ListNode(4); // 节点 head ListNode n2 = new ListNode(5); ListNode n3 = new ListNode(1);
// 连接节点使之成为链表
n1.next = n2; n2.next = n3; n3.next = null;
我们构造出来的链表如下图：
3.🌀Java实现单链表
其中实现了Iterable接口，提供了遍历方式。
import java.util.Iterator; /** * 链表的head是不可以动的 * @param */ public class LinkList implements Iterable{ private Node head;//头结点，链表的head是不可以动的 private int N;//结点个数 //构造方法 public LinkList() { this.head = new Node(null,null); N = 0; } //结点内部类 private class Node{ //存储数据 T item; //下一个结点 Node next; public Node(T item,Node next) { this.item = item; this.next = next; } } //清空链表 public void clear(){ head.item=null; head.next=null;// 头节点next为null就是空链表 this.N=0; } //判断链表是否为空 public boolean isEmpty(){ return this.N==0; } //获取链表的长度 public int length(){ return this.N; } //读取链表第i位置的元素值并返回 public T get(int i){ //非法性检查 if(i<0 || i > this.N){ throw new RuntimeException("位置不合法"); } // n也是指向头结点 Node n = head; for(int index=0; index n = n.next; } return n.item; } //往链表中插入数据t public void insert(T t){ // head不可以移动，不然就无法在找到链表 // 定义一个临时的Node也指向head的指针就可以通过移动该指针就可以 Node n = head; // 获取尾节点 while(true){ // 当刚好就一个节点时（头节点） if(n.next == null){ break; } n = n.next; } //当为空表时，就可以插入 Node node = new Node(t, null); n.next =node; this.N ++; } //在第i位置上插入数据t public void insert(T t,int i){ // 非法性检查 if(i < 0 || i > this.N){ throw new RuntimeException("插入位置非法"); } Node pre = head; for(int index=0;index <= i-1; index++){ pre = pre.next; } Node current = pre.next; //先链接后面结点 Node newNode = new Node(t,null); pre.next = newNode; newNode.next = current; this.N++; } //移除并返回第i位置的元素值 public T remove(int i){ // 非法性检查 if(i < 0 || i >this.N){ throw new RuntimeException("删除位置有误"); } Node n =head; for(int index=0;index <= i-1;index ++){ n = n.next; } //要删除的节点 Node curr = n.next; n.next = curr.next; this.N--;//结点个数减一 return curr.item; } //查找元素t在链表中第一次出现的位置 public int indexof(T t){ Node n = head; for(int i = 0; n.next != null;i++){ n =n.next; if(n.item.equals(t)){ return i; } } return -1; } @Override public Iterator iterator() { return new Iterator() { Node n =head; @Override public boolean hasNext() { return n.next !=null; } @Override public Object next() { //下移一个指针 n = n.next; return n.item; } }; } }
补充一点：链表的赋值给新的链表后，两个链表是会相会影响的，说白了就是把地址赋值给它了，他们操作是同一块内存的同一个对象。
Node n = head;
把head赋值给n，现在对n操作也是会影响head的。
4.🌀链表进阶练习
Leetcode 206. 反转链表
题解：
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
代码如下：
class Solution { public ListNode reverseList(ListNode head) { //申请节点，pre和 cur，pre指向null ListNode pre = null; ListNode cur = head; ListNode tmp = null; while(cur!=null) { //记录当前节点的下一个节点 tmp = cur.next; //然后将当前节点指向pre cur.next = pre; //pre和cur节点都前进一位 pre = cur; cur = tmp; } return pre; } }
结语
恭喜你修炼到这里，你已经基本有了收服神兽链表的能力。神兽链表是我们到进攻算法界最重要的能力之一。大家不可懈怠。
