1.定义

在计算机科学中，链表是数据元素的线性集合，每个元素都指向下一个元素，元素存储上并不连续

2.分类

链表中还有一种特殊的节点称为哨兵结点，也叫哑元结点、首元结点，它不存储数据，通常用作头尾，用来化简边界判断，如下图所示

3.性能

（1）随机访问

根据index查找，时间复杂度O(n)

（2）插入或删除

起始位置：O(1)

结束位置：如果已至tail尾结点是O(1)，不知道尾结点是O(n)

中间位置：根据index查找时间+O(1)

4.单向链表操作

（1）单向链表类的实现

 public class SinglyLinkedList{//整体private Node head;//头指针private class Node {//节点类int value;//值Node next;//下一个节点指针public Node(int value,Node next){this.value = value;this.next = next;}}}

（2）头部插入结点

     public void addFirst(int value){
//       //1.链表为空
//       head = new Node(value,null);//2.链表非空head = new Node(value,head);}

（3）链表遍历

     public void loop(){Node p = head;while (p != null){System.out.println(p.value);p = p.next;}}

（4）尾部插入结点

     private Node findLast(){//寻找最后一个结点if (head == null){//空链表return null;}Node p = head;while (p.next != null){p = p.next;}return p;}public void addList(int value){Node last = findLast();if (last == null){head = new Node(value,head);return;}last.next = new Node(value,null);}

（5）根据索引获取结点值

     public void test(){//寻找索引int i = 0;for (Node p = head;p != null;p = p.next,i++){System.out.println(p.value + "索引是：" + i);}}private Node findNode(int index){//查找结点int i = 0;for (Node p = head;p != null;p = p.next,i++){if (i == index){return p;}}return null;  //没找到}//单独写，方便其他方法调用public int get(int index){Node node = findNode(index);if (node == null){throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}return node.value;}

（6）向索引位置插入

     public void insert(int index,int value){if (index == 0){addFirst(value);//向第一位插入return;}Node prev = findNode(index-1);//找到上一个节点if (prev == null){//找不到throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}prev.next = new Node(value,prev.next);}

（7）删除头部结点

     public void removeFirst(){if (head == null){throw new IllegalArgumentException(String.format("index [0] 不合法%n"));}head = head.next;}

（8）根据索引删除结点

     public void remove(int index){if (index == 0){ //要删除的是头结点removeFirst();return;}Node prev = findNode(index-1);//上一个结点if (prev == null){  //链表最多只有索引3，要删除5号则找不到索引4throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}Node removed = prev.next; //被删除的结点if (removed == null){  //链表最多只有索引3，要删除4号throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}prev.next = removed.next;}

5.带哨兵的单向链表

（1）单向链表类的实现

 public class SinglyLinkedList{//整体private Node head = new Node(666,null); //哨兵，value可以随意制定private class Node {//节点类int value;//值Node next;//下一个节点指针public Node(int value,Node next){this.value = value;this.next = next;}}}

（2）链表遍历

     public void loop(){Node p = head.next;while (p != null){System.out.println(p.value);p = p.next;}}

（3）尾部插入结点

​
private Node findLast(){//寻找最后一个结点Node p = head; //若是空链表，则最后一个是哨兵while (p.next != null){p = p.next;}return p;}public void addList(int value){Node last = findLast();//若为空，则直接插入哨兵后面last.next = new Node(value,null);}

 (4)查找结点对象

     private Node findNode(int index){//查找结点int i = -1;for (Node p = head;p != null;p = p.next,i++){if (i == index){return p;}}return null;  //没找到}

 （5）向索引位置插入

     public void insert(int index,int value){//若index为0，在哨兵后插入Node prev = findNode(index-1);//找到上一个节点if (prev == null){//找不到throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}prev.next = new Node(value,prev.next);}

 （6）根据索引删除结点

     public void remove(int index){Node prev = findNode(index-1);//上一个结点if (prev == null){  //链表最多只有索引3，要删除5号则找不到索引4throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}Node removed = prev.next; //被删除的结点if (removed == null){  //链表最多只有索引3，要删除4号throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}prev.next = removed.next;}