什么是链表

链表图示

1-1 什么是链表【一手微信itit11223344】.mp4_20210921_142625634.jpg

1-1 什么是链表【一手微信itit11223344】.mp4_20210921_142845504.jpg

使用链表增删改查

图示

1632365802278.jpg

代码实现

  1. public class LinkedList<E> {
  3.     private class Node{
  4.         public E e;
  5.         public Node next;
  7.         public Node(E e,Node next){
  8.             this.e = e;
  9.             this.next = next;
  10.         }
  12.         public Node(E e){
  13.             this(e,null);
  14.         }
  16.         public Node(){
  17.             this(null,null);
  18.         }
  20.         @Override
  21.         public String toString() {
  22.             return e.toString();
  23.         }
  24.     }
  26.     private Node dummyHead;
  27.     private int size;
  29.     public LinkedList(){
  30.         dummyHead = new Node(null,null);
  31.         size = 0;
  32.     }
  34.     public boolean isEmpty(){
  35.         return size == 0;
  36.     }
  38.     //在链表的index位置添加新的元素e
  39.     //在链表中不是一个常用的操作，仅用于学习使用
  40.     public void add(int index,E e){
  41.         if (index < 0 || index>size){
  42.             throw new IllegalArgumentException("Add Failed. Illegal index");
  43.         }
  45.         //使用dummyHead头节点之后就不用再就行判断是否插入位置是0的顾虑了
  46.         Node prev = dummyHead;
  47.         for (int i = 0; i < index; i++) {
  48.                 prev = prev.next;
  49.          }
  51.             //Node node = new Node(e);
  52.             //node.next = prev.next;
  53.             //prev.next = node;
  55.         prev.next = new Node(e,prev.next);
  56.         size++;
  58.     }
  60.     //在链表头添加新的元素
  61.     public void addFirst(E e){
  63.         //Node node = new Node(e);
  64.         //node.next = head;
  65.         //head = node;
  66.         add(0,e);
  67.     }
  69.     //在链表末尾添加新的元素
  70.     public void addLast(E e){
  71.         add(size,e);
  72.     }
  74.     //获得链表的第index个位置的元素
  75.     //在链表中不是一个常用的操作,仅是练习使用
  76.     public E get(int index){
  77.         if (index < 0 || index >= size){
  78.             throw new IllegalArgumentException("Get Failed . Illegal index");
  79.         }
  80.         Node cur = dummyHead.next;   //这次得到的是头节点
  81.         for (int i = 0; i < index; i++) {
  82.             cur = cur.next;
  83.         }
  85.         return cur.e;
  86.     }
  88.     //获得链表的第一个元素
  89.     public E getFirst(){
  90.         return get(0);
  91.     }
  93.     //获得链表的最后一个元素
  94.     public E getLast(){
  95.         return get(size);
  96.     }
  99.     //修改链表中的第index个元素
  100.     public void set(int index,E e){
  101.         if (index < 0 || index >= size){
  102.             throw new IllegalArgumentException("Set Failed. Illegal index");
  103.         }
  104.         Node cur = dummyHead.next;
  105.         for (int i = 0; i < index; i++) {
  106.             cur = cur.next;
  107.         }
  108.         cur.e = e;
  109.     }
  111.     //查找链表是否含有元素e
  112.     public boolean contains(E e){
  113.         Node cur = dummyHead.next;
  114.         while (cur != null){
  115.             if (cur.e.equals(e)){
  116.                 return true;
  117.             }
  118.             cur = cur.next;
  119.         }
  120.         return false;
  121.     }
  124.     //从列表中删除index位置的元素，返回删除的元素
  125.     public E remove(int index){
  126.         if (index < 0 || index >= size){
  127.             throw new IllegalArgumentException("Remove Failed . Illegal index");
  128.         }
  129.         Node prev = dummyHead;
  130.         for (int i = 0; i < index; i++) {
  131.             prev = prev.next;
  132.         }
  134.         Node retNode = prev.next;
  135.         prev.next = retNode.next;
  136.         retNode.next = null;
  137.         size--;
  139.         return retNode.e;
  140.     }
  143.     //从链表中删除第一个元素，返回删除第一个元素
  144.     public E removeFirst(){
  145.         return remove(0);
  146.     }
  149.     //从链表中删除最后一个元素
  150.     public E removeLast(){
  151.         return remove(size-1);
  152.     }
  154.     public int getSize(){
  155.         return size;
  156.     }
  157.     @Override
  158.     public String toString() {
  159.         StringBuffer res = new StringBuffer();
  161.         Node cur = dummyHead.next;
  162.         while (cur!=null){
  163.             res.append(cur+"->");
  164.             cur = cur.next;
  165.         }
  166.         res.append("NULL");
  167.         return res.toString();
  169.     }
  170. }

使用链表的虚拟头节点(dummyHead)

1-3 使用链表的虚拟头结点【一手微信itit11223344】.mp4_20210921_150606789.jpg

为什么要设立dummyHead?

  • 当实行插入操作时，使用dummyHead头节点就不需要再判断插入位置是0的顾虑了
  • 遍历操作index次时，就遍历index次，而不需要遍历index-1

image.png

链表实现栈

  • 链表头作为栈顶

    1. public class LinkedListForStack<E> implements Stack<E> {
    3.   LinkedList<E> stack;
    5.   public LinkedListForStack() {
    6.       stack = new LinkedList<>();
    7.   }
    9.   @Override
    10.   public int getSize() {
    11.       return stack.getSize();
    12.   }
    14.   @Override
    15.   public boolean isEmpty() {
    16.       return stack.isEmpty();
    17.   }
    19.   @Override
    20.   public void push(E e) {
    21.       stack.addFirst(e);
    22.   }
    24.   @Override
    25.   public E pop() {
    26.       return stack.removeFirst();
    27.   }
    29.   @Override
    30.   public E peek() {
    31.       return stack.getFirst();
    32.   }
    34.   @Override
    35.   public String toString() {
    36.       final StringBuffer sb = new StringBuffer("stack  top");
    37.       sb.append(stack);
    38.       return sb.toString();
    39.   }
    40. }

带有尾指针的链表

  • 可以用来实现链表队列 ```java public class LinkedListForQueue implements Queue {
  1. private class Node{
  2.     public E e;
  3.     public Node next;
  5.     public Node(E e, Node next){
  6.         this.e = e;
  7.         this.next = next;
  8.     }
  10.     public Node(E e){
  11.         this(e,null);
  12.     }
  14.     public Node(){
  15.         this(null,null);
  16.     }
  18.     @Override
  19.     public String toString() {
  20.         return e.toString();
  21.     }
  22. }
  24. private Node head,tail;
  25. private int size;
  27. @Override
  28. public int getSize() {
  29.     return size;
  30. }
  32. @Override
  33. public boolean isEmpty() {
  34.     return size==0;
  35. }
  37. @Override
  38. public void enqueue(E e) {
  39.     if (tail == null){
  40.         tail = new Node(e);
  41.         head =tail;
  42.     }else {
  43.         tail.next = new Node(e);
  44.         tail = tail.next;
  45.     }
  46.     size++;
  47. }
  49. @Override
  50. public E dequeue(E e) {
  51.     if (isEmpty()){
  52.         throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  53.     }
  54.     Node retNode = head;
  55.     head = head.next;
  56.     retNode.next = null;
  57.     if (head == null){
  58.         tail = null;
  59.     }
  60.     size--;
  61.     return retNode.e;
  62. }
  64. @Override
  65. public E getFront() {
  66.     if (isEmpty()){
  67.         throw new IllegalArgumentException("Cannot getFront from an empty queue");
  69.     }
  70.     return head.e;
  71. }
  73. @Override
  74. public String toString() {
  75.     final StringBuffer sb = new StringBuffer("Queue front{");
  77.     Node cur = head;
  78.     while (cur != null){
  79.         sb.append(cur+"->");
  80.         cur = cur.next;
  81.     }
  83.     sb.append("null} tail" );
  84.     return sb.toString();
  85. }

}

  2. <a name="TlfkY"></a>
  3. # 链表的复杂度分析
  5. - 增 : O(n) , 如果是在表头添加，则是O(1)
  6. - 删 : O(n) , 如果是表头也是O(1)
  7. - 改 : O(n)
  8. - 查 : O(n)
  11. <a name="HEaRL"></a>
  12. # 链表相关问题
  14. <a name="Y6tMN"></a>
  15. ## 第一个很好的用到了dummyHead好处的例子:移除链表元素
  17. - LeetCode203
  18. <a name="AwIof"></a>
  19. ## 反转链表
  21. - 图示:
  23. ![3-1 链表最经典的问题：翻转链表【一手微信itit11223344】.mp4_20210924_093737283.jpg](https://cdn.nlark.com/yuque/0/2021/jpeg/21552184/1632737317821-beeff95d-aade-4de8-ad21-ebee57ca832d.jpeg#clientId=u7cb5e946-f6c7-4&from=ui&height=410&id=uba0be041&margin=%5Bobject%20Object%5D&name=3-1%20%E9%93%BE%E8%A1%A8%E6%9C%80%E7%BB%8F%E5%85%B8%E7%9A%84%E9%97%AE%E9%A2%98%EF%BC%9A%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8%E3%80%90%E4%B8%80%E6%89%8B%E5%BE%AE%E4%BF%A1itit11223344%E3%80%91.mp4_20210924_093737283.jpg&originHeight=1080&originWidth=1728&originalType=binary&ratio=1&size=76871&status=done&style=none&taskId=u31fdf69a-3162-49f9-95e1-8c7ca0f9b9e&width=656)
  25. - 当使用递归时:
  27. ![3-3 翻转链表的递归实现【一手微信itit11223344】.mp4_20210924_100755474.jpg](https://cdn.nlark.com/yuque/0/2021/jpeg/21552184/1632737379074-f1fd010a-164a-4316-938f-b3fda20936c9.jpeg#clientId=u7cb5e946-f6c7-4&from=ui&height=411&id=u53281aa1&margin=%5Bobject%20Object%5D&name=3-3%20%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8%E7%9A%84%E9%80%92%E5%BD%92%E5%AE%9E%E7%8E%B0%E3%80%90%E4%B8%80%E6%89%8B%E5%BE%AE%E4%BF%A1itit11223344%E3%80%91.mp4_20210924_100755474.jpg&originHeight=1080&originWidth=1728&originalType=binary&ratio=1&size=85947&status=done&style=none&taskId=udad9a41b-bc36-4f0c-8f1d-5fd4cdfab52&width=657)
  30. <a name="hIbfB"></a>
  31. # 递归问题
  32. <a name="pqIxu"></a>
  33. ## 使用递归实现了链表
  34. ```java
  35. public class RecursionForLinkedList<E> {
  36.     private class Node{
  37.         public E e;
  38.         public Node next;
  40.         public Node(E e, Node next){
  41.             this.e = e;
  42.             this.next = next;
  43.         }
  45.         public Node(E e){
  46.             this(e,null);
  47.         }
  49.         public Node(){
  50.             this(null,null);
  51.         }
  53.         @Override
  54.         public String toString() {
  55.             return e.toString();
  56.         }
  57.     }
  59.     private Node head;
  60.     private int size;
  62.     public RecursionForLinkedList() {
  63.         head = null;
  64.         size = 0;
  65.     }
  67.     public boolean isEmpty(){
  68.         return size == 0;
  69.     }
  71.     public int getSize(){
  72.         return size;
  73.     }
  75.     public void add(int index , E e){
  76.         if (index < 0 || index>size){
  77.             throw new IllegalArgumentException("Add Failed. Illegal index");
  78.         }
  80.         head = add(head,index,e);
  81.         size++;
  82.     }
  84.     private Node add(Node node,int index,E e){
  85.         if (index == 0){
  86.             return new Node(e,node);
  87.         }
  88.         node.next = add(node.next,index-1,e);
  89.         return node;
  90.     }
  92.     /**
  93.      * 在链表头添加新的元素
  94.      */
  95.     private void addFirst(E e){
  96.         add(0,e);
  97.     }
  100.     /**
  101.      * 在链表末尾添加新的元素
  102.      */
  103.     private void addLast(E e){
  104.         add(size,e);
  105.     }
  108.     /**
  109.      * 获得链表第index个位置的值
  110.      */
  111.     public E get(int index){
  112.         if (index < 0 || index >= size){
  113.             throw new IllegalArgumentException("Get Failed . Illegal index");
  114.         }
  115.         return get(head,index);
  116.     }
  118.     private E get(Node node,int index){
  119.         if (index < 0 || index >= size){
  120.             throw new IllegalArgumentException("Get Failed . Illegal index");
  121.         }
  122.         if (index == 0){
  123.             return node.e;
  124.         }
  125.         return get(node.next,index-1);
  127.     }
  129.     /**
  130.      * 获得链表的第一个元素
  131.      */
  132.     private E getFirst(){
  133.         return get(0);
  134.     }
  136.     /**
  137.      * 获得最后一个元素
  138.      */
  139.     private E getLast(){
  140.         return get(size);
  141.     }
  144.     /**
  145.      * 修改第index个位置的元素
  146.      */
  148.     public void set(int index,E e){
  149.         set(head,index,e);
  150.     }
  152.     private void set(Node node,int index,E e){
  153.         if (index < 0 || index >= size){
  154.             throw new IllegalArgumentException("Set Failed. Illegal index");
  155.         }
  156.         if (index == 0){
  157.             node.e = e;
  158.         }
  160.         set(node.next,index-1,e);
  161.     }
  163.     /**
  164.      * 查找链表是否存在某个元素
  165.      */
  166.     public boolean contains(E e){
  167.         return contains(head,e);
  168.     }
  170.     private boolean contains(Node node,E e){
  171.         if (node == null){
  172.             return false;
  173.         }
  174.         if (node.e.equals(e)){
  175.             return true;
  176.         }
  178.         return contains(node.next,e);
  179.     }
  181.     /**
  182.      * 在链表中删除某个元素，并返回删除的元素
  183.      */
  184.     public E remove(int index){
  185.         if (index < 0 || index >= size){
  186.             throw new IllegalArgumentException("Remove Failed. Illegal index");
  187.         }
  188.         Pair<Node,E> res = remove(head,index);
  189.         size--;
  190.         head = res.getKey();
  191.         return res.getValue();
  192.     }
  194.     private Pair<Node,E> remove(Node node, int index){
  196.         if (index == 0){
  197.             return new Pair<>(node.next,node.e);
  198.         }
  199.         Pair<Node, E> res = remove(node.next, index - 1);
  200.         node.next = res.getKey();
  201.         return new Pair<>(node,res.getValue());
  202.     }
  205.      // 从链表中删除第一个元素, 返回删除的元素
  206.      public E removeFirst(){ return remove(0); }
  208.      // 从链表中删除最后一个元素, 返回删除的元素
  209.      public E removeLast(){ return remove(size - 1); }
  212.      //从链表中删除元素e
  213.      public void removeElement(E e){
  214.          removeElement(head,e);
  215.      }
  217.      private void removeElement(Node node,E e){
  218.          if (node == null){
  219.              return;
  220.          }
  221.          if (node.next.e.equals(e)){
  222.                node.next = node.next.next;
  223.          }else {
  224.              removeElement(node.next,e);
  225.          }
  226.      }
  229.     @Override
  230.     public String toString() {
  231.         StringBuilder res = new StringBuilder();
  232.         Node cur = head;
  233.         while (cur != null) {
  234.             res.append(cur + "->");
  235.             cur = cur.next;
  236.         }
  237.         res.append("NULL");
  238.         return res.toString();
  239.     }
  241.     public static void main(String[] args) {
  242.         RecursionForLinkedList<Integer> list = new RecursionForLinkedList<>();
  243.         for (int i = 0; i < 10; i++) list.addFirst(i);
  244.         System.out.println(list);
  245.         list.removeElement(3);
  246.         System.out.println(list);
  247.     }
  248. }