链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
根据前一章顺序表的介绍，我们发现对于顺序的删除和添加元素很麻烦，如果是一个非常大的基数那么我们所消耗的时间非常大，所以我们还有一种表可以极大的减少添加元素和删除元素操作的时间。那就是本章的主题：链表。
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(); } }
结果：
ArrayList和LinkedList的对比：
一、ArrayList和LinkedList查询之间的区别
首先，从名字就可以看出，ArrayList和LinkedList的区别，ArrayList是基于数组的，LinkedList是基于链表的。
从这一点，我们可以推理出来，ArrayList适合查询，LinkedList适合插入，但是这只是一个广泛的结论，我们应该了解的更细致一点。
比如，对于ArrayList，它真正的优点是按下标查询元素，相比于LinkedList，LinkedList也可以按下标查询元素，但是LinkedList需要对底层链表进行遍历，才能找到指定下标的元素，而ArrayList不用，所以这是ArrayList的优点。
但是，如果我们讨论的是获取第一个元素，或最后一个元素，ArrayList和LinkedList在性能上是没有区别的，因为LinkedList中有两个属性分别记录了当前链表中的头结点和尾结点，并不需要遍历链表。
以上，是对于ArrayList和LinkedList在查询方面的区别。
二、ArrayList和LinkedList插入之间的区别
ArrayList可以插入到指定下标位置，或者数组末尾，这种插入普通情况下是很快的，但是如果某次插入操作触发了扩容，那么本次插入就增加了额外的扩容成本。
对于LinkedList，如果是插在链表的头部或者是尾部都是很快的，因为LinkedList中有单独的属性记录的链表的头结点和尾结点，不过，如果是插在指定下标位置，那么就需要遍历链表找到指定位置，从而降低了效率。
但是，使用LinkedList是不用担心扩容问题的，链表是不需要扩容的。
