1.概念
链式存储是常用的动态存储方式，相对于顺序表，可以更好的任意插入与删除，而采用链式存储的结构叫做链表。
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
从链接方式的角度：链表分为单链表、双链表及循环链表；
从实现方式的角度：链表分为动态链表和静态链表；
2.链表
2.1 单链表概念及结构
概念：
单链表是通过一个一个结点进行连接，而链表并不像顺序表一样存储的是一组地址连续的存储单元，而是非连续的。因此，链表中的结点不仅需要存储自己的数据元素值（数据域），还需要存储下一个结点的地址（指针域）。
结构：
单链表的每个结点的地址都存储在其前驱结点的指针域中，因此第一个结点无前驱，这个时候我们可以设置一个头指针Head指向第一个结点。而最后一个结点后面没有结点，所以最后一个结点指针域为空（Null）。
单链表结构：
2.2双链表的概念及结构
概念：
每个结点相对与单链表多了一个指针域，其它与单链表基本相同。
结构：
2.3 循环链表
概念：
循环链表是建立在单链表和双链表的基础上，将头尾相连，形成一个环，这就是循环链表，可分为：循环单链表、循环双链表。
3.链表的具体使用
| 方法 | 解释 |
| add（E e） | 尾插 e |
add（int i, E e） |
把e插在i位置 |
| addAll(Collection<? extends E> c) | 尾插c |
| addFirst（E e） | 头插e |
| remove（int i） | 删除i坐标元素 |
| remove（int i） | 删除i坐标元素 |
| get（int i） | 获得i坐标元素 |
| set（int i ， E e） | 将i坐标元素换为e |
| clear（） | 清空 |
| contains（object o ） | 判定o是否存在 |
| indexOf（object o） | 返回第一个o所在位置的下标 |
| lastIndexOf（object o） | 返回最后一个o下标 |
| subList(int f, int t) | 截取f坐标到t坐标list |
代码实现：
public class Test1 { public static void main(String[] args) { System.out.println(list.add(1));//尾插1，Boolean list.addFirst(2);//头插2 System.out.println(list); list.addLast(3);//尾插3 System.out.println(list); list.add(1,4);//1坐标插入4 System.out.println(list); list.remove(2);//删除2坐标元素 System.out.println(list); System.out.println(list.get(2));//获得2坐标元素 System.out.println(list); list.set(1,3);//将1坐标元素改为3 System.out.println(list); System.out.println(list.contains(3));//是否含5 System.out.println(list.contains(6));//是否含6 System.out.println(list.indexOf(3));//第一个3的下标 System.out.println(list.lastIndexOf(3));//最后一个3的下标 System.out.println(list.subList(0,1));//截取[0,1)的list，前闭后开 System.out.println(list.isEmpty());//list中是否有元素 list.clear();//清空 System.out.println(list.isEmpty()); } }
运行结果：
true [2, 1] [2, 1, 3] [2, 4, 1, 3] [2, 4, 3] 3 [2, 4, 3] [2, 3, 3] true false 1 2 [2] false true
4.自己实现链表及方法：
注意：
上面这些方法的实现，我们可以直接用，但是我们也可以创建自己的链表，实现自己的方法，让我们更好的理解，提升我们的代码能力。
代码的实现我放在了下面，但是最好自己实现一遍。
双链表：
public class MyLinkedList { static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; //头插法 public void addFirst(int data){ ListNode listNode = new ListNode(data); if (head == null){ head = listNode; last = listNode; }else{ head.prev = listNode; listNode.next = head; head = listNode; } } //尾插法 public void addLast(int data){ ListNode listNode = new ListNode(data); if(last == null){ last = listNode; head = listNode; }else{ last.next = listNode; listNode.prev = last; last = listNode; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ ListNode listNode = new ListNode(data); if(index < 0 || index > size()){ System.out.println("不合法"); return; } if(index == 0){ addFirst(data); return; } if (index == size()){ addLast(data); return; } ListNode cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } listNode.next = cur; cur.prev.next = listNode; listNode.prev = cur.prev; cur.prev = listNode; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = head; while (cur != null){ if(cur.val == key){ return true; } } return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ ListNode cur = head; while (cur != null){ if(cur.val == key){ if(cur == head){ head = head.next; }else{ if (cur.next == null) { cur.prev.next = null; last = cur.prev; }else{ cur.prev.next = cur.next; cur.next.prev = cur.prev; } } return; }else{ cur = cur.next; } } System.out.println("没有这个节点"); } //删除所有值为key的节点 public void removeAllKey(int key){ ListNode cur = head; while (cur != null){ if(cur.val == key){ if(cur == head){ head = head.next; }else{ if (cur.next == null) { cur.prev.next = null; last = cur.prev; }else{ cur.prev.next = cur.next; cur.next.prev = cur.prev; } } } cur = cur.next; } } //得到单链表的长度 public int size(){ int count = 0; ListNode cur = head; while (cur != null){ count++; cur = cur.next; } return count; } public void display(){ ListNode cur = head; while (cur != null){ System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } public void clear(){ head = null; } }
单链表：
public class SingleLinkedList { class ListNode{ public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public void createNode(){ ListNode listNode1 = new ListNode(12); ListNode listNode2 = new ListNode(23); ListNode listNode3 = new ListNode(34); ListNode listNode4 = new ListNode(45); ListNode listNode5 = new ListNode(45); head = listNode1; listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; } public ListNode head; //打印 public void show(){ ListNode cur = head; for (int i = 0; i < size(); i++) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //长度 public int size(){ ListNode cur = head; int count = 0; while(cur != null){ cur = cur.next; count++; } return count; } //查找 public boolean contains(int key){ ListNode cur = head; if(cur == null){ return false; } while (cur.val != key){ if(cur.next == null){ return false; } cur = cur.next; } return true; } //头插 public void addFirst(int data){ ListNode newNode = new ListNode(data); newNode.next = head; head = newNode; } //尾插 public void addLast(int data){ ListNode newNode = new ListNode(data); ListNode cur = head; while (cur.next != null){ cur = cur.next; } cur.next = newNode; } //随意插 public void addIndex(int index,int data){ ListNode cur = head; ListNode newNode = new ListNode(data); if(index == 0){ addFirst(data); return; } if(index < 0 || index > size() || cur == null){ throw new IndexOutOfBounds("数组不合法，越界: " + index); } if(index == size()){ addLast(data); return; } for (int i = 1; i < index; i++) { cur = cur.next; } newNode.next = cur.next; cur.next = newNode; } //删除第一次出现关键字为key的节点 public void remove(int key){ ListNode cur = head; ListNode pver = head; if(cur == null){ System.out.println("链表无节点"); return; } if(cur.val == key){ head = head.next; } while(cur.val != key){ if(cur.next == null){ System.out.println("无此节点"); return; } pver = cur; cur = cur.next; } if(cur.val == key){ pver.next = cur.next; return; } } //删除所有值为key的节点 public void removeAllKey(int key){ if(head == null) { return; } ListNode cur = head.next; ListNode prev = head; while (cur != null) { if(cur.val == key) { prev.next = cur.next; cur = cur.next; }else { prev = cur; cur = cur.next; } } if(head.val == key) { head = head.next; } } //清除所有数据 public void clear(){ head = null; } }
