1. 链表的概念：

2.链表的实现

ArrayList和LinkedList的对比：

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

根据前一章顺序表的介绍，我们发现对于顺序的删除和添加元素很麻烦，如果是一个非常大的基数那么我们所消耗的时间非常大，所以我们还有一种表可以极大的减少添加元素和删除元素操作的时间。那就是本章的主题：链表。

1. 链表的概念：

定义：

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

特点：

链表由一系列节点（链表中每一个元素称为节点）组成，每个节点包括两个部分：

一个是存储数据元素的数据域

另一个是存储下一个节点地址的指针域

看代码：

我们有很多种方法，可以在一个类中创建一个内部类，是否静态任选；也可以自己创建一个ListNode类，再创建一个

SingleLinkedList 类把代码写在里面。

随便选择一种，我这里选择再SingleLinkedList内写一个静态内部类。

static class ListNode  {public int val;//存储的数据public ListNode  next;//存储下一个节点的地址public ListNode(int val) {this.val = val;}}

在我们创建链表时，每new一个都是随机的地址,在物理上不连续，但是在逻辑上是连续的。

图示：

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们重点掌握两种:
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
那么链表究竟是如何实现的呢？

2.链表的实现

我们先写一个初始化

 public ListNode head;// 代表当前链表的头节点的引用// 初始化public ListNode CreateLinkedList () {ListNode node1 = new ListNode(2);ListNode node2 = new ListNode(4);ListNode node3 = new ListNode(6);ListNode node4 = new ListNode(2);head = node1;//记录头节点node1.next = node2;//我们用next链接后一个结点node2.next = node3;node3.next = node4;return head;};

对链表的插入分为头插和尾插：

 //头插法public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;};//尾插法public void addLast(int data) {ListNode node = new ListNode(data);if (head == null) {head = node;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;};

我们也可以选择在任意位置去下表选择型的插入：

 //任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data) {checkIndex(index);//判断下表是否合理if(index == 0) {addFirst(data);return true;}if(index == size()) {addLast(data);return true;}ListNode cur = findIndexSubOne(index);//找到下表前一个位置处ListNode listNode = new ListNode(data);listNode.next = cur.next;cur.next = listNode;return true;};private ListNode findIndexSubOne(int index) {ListNode cur = head;int count = 0;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) {if(index < 0 || index > size()) {throw new ListIndexOutOfException("index位置不合法");}}

public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
}

删除操作：

    //查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) throws NothingnessException {if (!contains(key)) {//contains方法用于查询是否有该元素throw new NothingnessException("key不存在");}if (head == null) {throw new NullPointerException("头节点为空");//抛出异常}if(head.val == key) {head = head.next;return;}ListNode cur = searchPrev(key);//找到需要删除结点的前一个结点ListNode del = cur.next;cur.next = del.next;};private ListNode searchPrev(int key) {ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;//没有你要删除的节点}

public class NothingnessException extends Exception{public NothingnessException() {}public NothingnessException(String message) {super(message);}
}

删除所有结点为key的值

 //删除所有值为key的节点public void removeAllKey(int key) throws NothingnessException {if (!contains(key)) {throw new NothingnessException("key不存在");}if (head == null) {throw new NullPointerException("头节点为空");}ListNode cur = head;while (cur.next != null) {if (cur.next.val == key) {cur.next = cur.next.next;}cur = cur.next;}};

还有其他的操作：求链表长度，我们链表长度不同于顺序表，顺序表可以直接得到表长，我们链表只能通过计数器一个个去加加。

//得到单链表的长度public int size() {int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;};
//清除表public void clear() {head = null;};
//移除所有元素public ListNode removeElements( int val) {if (head == null) {throw new NullPointerException("头节点为空");}ListNode slow = head;ListNode fast = head;while(fast.next != null) {if(fast.val != val) {slow = slow.next;} else {slow.next = fast;}fast = fast.next;}return head;}
}

测试：

public class Main {public static void main(String[] args) throws NothingnessException {SingleLinkedList myLinkedList = new SingleLinkedList();myLinkedList.CreateLinkedList();myLinkedList.display();myLinkedList.addFirst(1);myLinkedList.addLast(100);myLinkedList.addIndex(2,20);myLinkedList.display();System.out.println(myLinkedList.contains(100));myLinkedList.remove(100);myLinkedList.display();System.out.println(myLinkedList.size());myLinkedList.clear();myLinkedList.display();}
}

结果：