基础数据结构-链表 - 图1

1. 什么是链表？

1.1 链表的基本概念

链表在内存中的保存是不连续的，每个结点通过指针的方式联系在一起。以单向链表为例，它包含两个部分，一部分保存数据内容，一部分保存下一个结点的引用。
image.png

1.2 链表的特点

  • 内存中不连续存在
  • 通过指针建立联系
  • 大小不是固定的，不需要扩容的操作

  • 插入、删除元素比较快

    1.3 链表的分类

  • 单向链表

  • 双向链表
  • 循环链表

    1.3.1 单向链表

    单向链表，顾名思义就是记录的引用信息时单向的，一般的单向链表都是记录下一个结点的引用信息。
    image.png ```java package com.muzili.list;

import org.w3c.dom.Node;

import java.util.Objects;

/*

  • @author: muzili(李敷斌)
  • @date: 2021/7/13
  • @version: v0.0.1

  • @description: 单向链表 */ public class LinkedList {

    /**

    • 头结点 / private Node first; /*
    • 尾结点 / private Node last; /*

    • 链表大小 */ private int size;

      public Node getFirst() { return first; }

      public void setFirst(Node first) { this.first = first; }

      public Node getLast() { return last; }

      public void setLast(Node last) { this.last = last; }

      public int getSize() { return size; }

      public void setSize(int size) { this.size = size; }

      public LinkedList() { }

      public LinkedList(Node node) { this.first = node; this.last = node; this.size = 1; }

      /**

    • 添加到头部

    • @param data */ public void addFirst(T data){ Node node = new Node(data); node.next = first; first = node; if (size==0){

      1.  last = node;

      } size++; }

      /**

    • 添加到尾部

    • @param data */ public void addLast(T data){ Node node = new Node(data); if (Objects.isNull(last) && Objects.isNull(first)){

      1.  last = node;
      2.  first = node;
      3.  size++;
      4.  return;

      }

      if (Objects.isNull(last)){

      1.  last = node;
      2.  size++;
      3.  return;

      } last.next = node; last = node; size++; }

      /**

    • 添加原始到指定位置
    • @param loc

    • @param data */ public void addNth(int loc,T data){

      if (size==0){

      1.  addFirst(data);
      2.  return;

      }

      if (loc > size){

      1.  addLast(data);
      2.  return;

      }

      Node curr = first; for (int i = 1; i < loc; i++) {

      1.  curr = curr.next;

      } Node node = new Node(data); node.next = curr.next; curr.next = node; size++; }

      /**

    • 删除第一个结点 */ public void removeFirst(){

      if (size==0){

      1.  return;

      }

      first = first.next; size—; if (size==1){

      1.  last = first;

      } }

  1. public void removeLast(){
  3.     if (size==0){
  4.         return;
  5.     }
  7.     Node cur = first;
  8.     for (int i = 1; i < size - 1; i++) {
  9.         cur = cur.next;
  10.     }
  11.     last = cur;
  12.     cur.next = null;
  13.     size--;
  14. }
  16. /**
  17.  * 删除指定位置的元素
  18.  * @param loc
  19.  */
  20. public void removeNth(int loc){
  22.     if (loc < 0 || loc > size){
  23.         throw new IllegalArgumentException();
  24.     }
  26.     Node cur = first;
  27.     for (int i = 1; i < loc; i++) {
  28.         cur = cur.next;
  29.     }
  31.     cur.next = cur.next.next;
  32. }
  34. /**
  35.  * 获取指定位置的元素值
  36.  * @param loc
  37.  * @return 元素值
  38.  */
  39. public T getNth(int loc){
  41.     if (loc >= size){
  42.         throw new IllegalArgumentException();
  43.     }
  45.     Node cur = first;
  46.     for (int i = 1; i < loc; i++) {
  47.         cur = cur.next;
  48.     }
  50.     return (T) cur.getData();
  51. }
  54. /**
  55.  * 结点
  56.  * @param <T>
  57.  */
  58. class Node<T>{
  60.     private T data;
  62.     private Node next;
  64.     public Node(T data) {
  65.         this.data = data;
  66.     }
  68.     public T getData() {
  69.         return data;
  70.     }
  72.     public void setData(T data) {
  73.         this.data = data;
  74.     }
  76.     public Node getNext() {
  77.         return next;
  78.     }
  80.     public void setNext(Node next) {
  81.         this.next = next;
  82.     }
  83. }
  86. public static void main(String[] args) {
  88.     LinkedList list = new LinkedList<String>();
  89.     list.addLast("aaaa");
  90.     list.addFirst("bbbb");
  91.     list.addLast("ccc");
  92.     list.addNth(4,"dddd");
  93.     list.addNth(4,"ffff");
  94.     list.addNth(4,"eeee");
  95.     list.addNth(4,"gggg");
  96.     list.addNth(4,"g4");
  97.     System.out.println(list);
  98.     list.removeLast();
  99.     list.removeLast();
  100.     list.removeNth(2);
  101.     System.out.println(list);
  102.     System.out.println(list.getNth(1));
  103. }

}

  1. <a name="BUFFb"></a>
  2. ### 1.3.2 双向链表
  3. 双向链表顾名思义，就是记录了两个方向的指针信息，双向链表记录上一个和下一个结点的信息。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/21857252/1626665423208-cb6de808-8283-4200-9b51-cfdaa619d1e8.png#align=left&display=inline&height=821&margin=%5Bobject%20Object%5D&name=image.png&originHeight=821&originWidth=1413&size=41140&status=done&style=none&width=1413)
  4. ```java
  5. package com.muzili.list;
  7. /**
  8.  *
  9.  * @author: muzili(李敷斌)
  10.  * @date: 2021/7/16
  11.  * @version: v0.0.1
  12.  * @description: 双向链表
  13.  */
  14. public class DoubleLinkedList<T> {
  16.     /**
  17.      * 头结点
  18.      */
  19.     private Node<T> first;
  21.     /**
  22.      * 尾结点
  23.      */
  24.     private Node<T> last;
  26.     /**
  27.      * 链表大小
  28.      */
  29.     private int size = 0;
  32.     public Node<T> getFirst() {
  33.         return first;
  34.     }
  36.     public void setFirst(Node<T> first) {
  37.         this.first = first;
  38.     }
  40.     public Node<T> getLast() {
  41.         return last;
  42.     }
  44.     public void setLast(Node<T> last) {
  45.         this.last = last;
  46.     }
  48.     public int getSize() {
  49.         return size;
  50.     }
  52.     public void setSize(int size) {
  53.         this.size = size;
  54.     }
  56.     public DoubleLinkedList() {
  57.     }
  59.     public DoubleLinkedList(T data) {
  60.         Node<T> node = new Node<>();
  61.         node.data = data;
  62.         first = node;
  63.         last = node;
  64.         size++;
  65.     }
  67.     /**
  68.      * 将数据添加到头部
  69.      * @param data
  70.      */
  71.     public void addFirst(T data){
  73.         Node node = new Node();
  74.         node.data = data;
  75.         if (first!=null){
  76.             node.next = first;
  77.             first.prev = node;
  78.         }
  79.         first = node;
  80.         if (size==0){
  81.             last = node;
  82.         }
  83.         size++;
  84.     }
  86.     /**
  87.      * 将数据添加到尾部
  88.      * @param data
  89.      */
  90.     public void addLast(T data){
  92.         if (size==0){
  93.             addFirst(data);
  94.             return;
  95.         }
  96.         Node node = new Node();
  97.         node.data = data;
  98.         node.prev = last;
  99.         last.next = node;
  100.         last = node;
  101.         size++;
  102.     }
  105.     /**
  106.      * 向指定位置添加数据
  107.      * @param loc
  108.      * @param data
  109.      */
  110.     public void addNth(int loc,T data){
  112.         if (loc < 0 || loc > size){
  113.             throw new IllegalArgumentException();
  114.         }
  116.         //如果loc为0添加到头部
  117.         if (loc==0){
  118.             addFirst(data);
  119.             return;
  120.         }
  122.         //如果loc等于链表大小 添加到尾部
  123.         if (loc == size){
  124.             addLast(data);
  125.             return;
  126.         }
  128.         Node node = new Node();
  129.         node.data = data;
  130.         //获取到待添加位置的元素
  131.         Node curr = first;
  132.         for (int i = 1; i <= loc; i++) {
  133.             curr = curr.next;
  134.         }
  135.         node.next = curr;
  136.         curr.prev = node;
  137.         size++;
  138.     }
  140.     /**
  141.      * 删除头部的元素
  142.      */
  143.     public void removeFirst(){
  145.         if (size == 0){
  146.             return;
  147.         }
  148.         first = first.next;
  149.         size--;
  150.     }
  152.     /**
  153.      * 删除尾部的元素
  154.      */
  155.     public void removeLast(){
  157.         if (size==0){
  158.             return;
  159.         }
  160.         last = last.prev;
  161.         last.next = null;
  162.         size--;
  163.     }
  165.     /**
  166.      * 删除指定位置的元素
  167.      * @param loc
  168.      */
  169.     public void removeNth(int loc){
  171.         if (loc < 0|| loc >= size){
  172.             throw new IllegalArgumentException();
  173.         }
  175.         //如果删除的元素位置为0 则删除头部元素
  176.         if (loc==0){
  177.             removeFirst();
  178.             return;
  179.         }
  181.         //如果删除元素的位置为size-1 则删除尾部的元素
  182.         if (loc == size-1){
  183.             removeLast();
  184.             return;
  185.         }
  187.         //找到指定位置的元素
  188.         Node curr = first;
  189.         for (int i = 1; i <= loc; i++) {
  190.             curr = curr.next;
  191.         }
  192.         Node next = curr.next;
  193.         Node prev = curr.prev;
  194.         if (next!=null){
  195.             next.prev = curr.prev;
  196.         }
  197.         if (prev!=null){
  198.             prev.next = next;
  199.         }
  200.         size--;
  201.     }
  203.     /**
  204.      * 获取指定位置的元素值
  205.      * @param loc
  206.      * @return
  207.      */
  208.     public T getNth(int loc){
  210.         if (loc < 0|| loc >= size){
  211.             throw new IllegalArgumentException();
  212.         }
  214.         Node<T> curr = first;
  215.         for (int i = 1; i <= loc; i++) {
  216.             curr = curr.next;
  217.         }
  218.         return curr.data;
  219.     }
  221.     class Node<T>{
  223.         /**
  224.          * 上一节点
  225.          */
  226.         private Node<T> prev;
  228.         /**
  229.          * 下一节点
  230.          */
  231.         private Node<T> next;
  233.         /**
  234.          * 数据值
  235.          */
  236.         private T data;
  238.         public Node<T> getPrev() {
  239.             return prev;
  240.         }
  242.         public void setPrev(Node<T> prev) {
  243.             this.prev = prev;
  244.         }
  246.         public Node<T> getNext() {
  247.             return next;
  248.         }
  250.         public void setNext(Node<T> next) {
  251.             this.next = next;
  252.         }
  254.         public T getData() {
  255.             return data;
  256.         }
  258.         public void setData(T data) {
  259.             this.data = data;
  260.         }
  261.     }
  264.     public static void main(String[] args) {
  266.         DoubleLinkedList<String> list = new DoubleLinkedList<>();
  267.         list.addFirst("11111");
  268.         list.addLast("22222");
  269.         list.addNth(0,"0000");
  270.         list.addLast("3333");
  272.         System.out.println(list.getNth(2));
  274.         list.removeLast();
  275.         list.removeNth(1);
  276.         list.removeFirst();
  277.         System.out.println(list);
  278.     }
  280. }

1.3.3 循环链表

循环链表是一种特殊的结构，它的最后一个结点指针不是null而是指向第一个结点。循环链表可分为循环单向链表，循环双向链表。
image.png

  1. package com.muzili.list;
  3. /**
  4.  *
  5.  * @author: muzili(李敷斌)
  6.  * @date: 2021/7/19
  7.  * @version: v0.0.1
  8.  * @description: 循环链表
  9.  */
  10. public class CurcularLinkedList<T> {
  12.     /**
  13.      * 头结点
  14.      */
  15.     private Node<T> first;
  17.     /**
  18.      * 尾结点
  19.      */
  20.     private Node<T> last;
  22.     /**
  23.      * 链表长度
  24.      */
  25.     private int size=0;
  28.     public Node<T> getFirst() {
  29.         return first;
  30.     }
  32.     public void setFirst(Node<T> first) {
  33.         this.first = first;
  34.     }
  36.     public Node<T> getLast() {
  37.         return last;
  38.     }
  40.     public void setLast(Node<T> last) {
  41.         this.last = last;
  42.     }
  44.     public int getSize() {
  45.         return size;
  46.     }
  48.     public void setSize(int size) {
  49.         this.size = size;
  50.     }
  52.     public CurcularLinkedList() {
  53.     }
  55.     public CurcularLinkedList(T data) {
  57.         Node node = new Node();
  58.         node.data = data;
  59.         first = node;
  60.         last = node;
  61.         size++;
  62.     }
  64.     /**
  65.      * 添加到头部
  66.      * @param data
  67.      */
  68.     public void addFirst(T data){
  70.         Node node = new Node();
  71.         node.data = data;
  72.         if (size >= 1){
  73.             node.next = first;
  74.         }
  75.         first = node;
  76.         if (size==0){
  77.             last = node;
  78.             last.next = first;
  79.         }
  80.     }
  82.     /**
  83.      * 添加到尾部
  84.      * @param data
  85.      */
  86.     public void addLast(T data){
  88.         Node node = new Node();
  89.         node.data = data;
  90.         if (size == 0){
  91.             first = node;
  92.             last = node;
  93.             last.next = first;
  94.             size++;
  95.             return;
  96.         }
  98.         last.next = node;
  99.         last = node;
  100.         last.next = first;
  101.         size++;
  102.     }
  104.     /**
  105.      * 添加到指定位置
  106.      * @param loc
  107.      * @param data
  108.      */
  109.     public void addNth(int loc,T data){
  111.         if (loc > size){
  112.             throw new IllegalArgumentException();
  113.         }
  115.         if (size == 0){
  116.             addFirst(data);
  117.             return;
  118.         }
  120.         if (loc == size){
  121.             addLast(data);
  122.             return;
  123.         }
  125.         Node curr = first;
  126.         for (int i = 1; i < loc; i++) {
  127.             curr = curr.next;
  128.         }
  130.         Node node = new Node();
  131.         node.data = data;
  132.         node.next = curr.next;
  133.         curr.next = node;
  134.     }
  136.     /**
  137.      * 删除头结点
  138.      */
  139.     public void removeFirst(){
  141.         if (size == 0){
  142.             throw new IllegalArgumentException();
  143.         }
  145.         first = first.next;
  146.         last.next = first;
  147.         size --;
  148.         if (size <= 1){
  149.             last = first;
  150.         }
  151.     }
  153.     /**
  154.      * 删除最后一个元素
  155.      */
  156.     public void removeLast(){
  158.         if (size == 0){
  159.             throw new IllegalArgumentException();
  160.         }
  162.         //获取最后一个元素的前一个元素
  163.         Node curr = first;
  164.         for (int i = 1; i < size - 1; i++) {
  165.             curr = curr.next;
  166.         }
  167.         curr.next = null;
  168.         last = curr;
  169.         curr.next = first;
  170.         size --;
  171.     }
  173.     /**
  174.      * 删除指定位置的元素
  175.      * @param loc
  176.      */
  177.     public void removeNth(int loc){
  179.         if (size==0 || loc < 0){
  180.             throw new IllegalArgumentException();
  181.         }
  183.         if (loc == 0){
  184.             removeFirst();
  185.             return;
  186.         }
  188.         if (loc == size-1){
  189.             removeLast();
  190.             return;
  191.         }
  193.         //获取待删除元素的前一个元素
  194.         Node curr = first;
  195.         for (int i = 1; i < loc - 1; i++) {
  196.             curr = curr.next;
  197.         }
  199.         curr.next = curr.next.next;
  200.         size --;
  201.     }
  203.     /**
  204.      * 约瑟夫问题解决
  205.      * @param factor
  206.      */
  207.     public void josephRemove(int factor){
  209.         Node<T> start = first;
  210.         int count = 0;
  211.         while (size > 1){
  212.             count ++;
  213.             Node curr = start;
  214.             for (int i = 1; i < factor - 1; i++) {
  215.                 curr = curr.next;
  216.             }
  217.             System.out.println("第"+count+"次淘汰的元素内容："+curr.next.data);
  219.             curr.next = curr.next.next;
  220.             start = curr.next;
  221.             size --;
  222.         }
  223.         System.out.println("最后留下的的元素是："+start.data);
  224.     }
  226.     public static void main(String[] args) {
  228.         CurcularLinkedList<Integer> linkedList = new CurcularLinkedList<Integer>(1);
  229.         linkedList.addLast(2);
  230.         linkedList.addLast(3);
  231.         linkedList.addLast(4);
  232.         linkedList.addLast(5);
  233.         linkedList.addLast(6);
  235.         linkedList.josephRemove(5);
  236.     }
  238.     /**
  239.      * 获取指定位置的元素
  240.      * @param loc
  241.      * @return
  242.      */
  243.     public T getNth(int loc){
  245.         if (size == 0 || loc >= size){
  246.             throw new IllegalArgumentException();
  247.         }
  249.         if (loc == 0){
  250.             return getFirst().data;
  251.         }
  253.         if (loc == size - 1){
  254.             return getLast().data;
  255.         }
  257.         Node<T> curr = first;
  258.         for (int i = 0; i <= loc; i++) {
  259.             curr = curr.next;
  260.         }
  261.         return curr.data;
  262.     }
  264.     class Node<T>{
  266.         /**
  267.          * 数据内容
  268.          */
  269.         private T data;
  271.         /**
  272.          * 下一个结点
  273.          */
  274.         private Node<T> next;
  276.         public T getData() {
  277.             return data;
  278.         }
  280.         public void setData(T data) {
  281.             this.data = data;
  282.         }
  284.         public Node<T> getNext() {
  285.             return next;
  286.         }
  288.         public void setNext(Node<T> next) {
  289.             this.next = next;
  290.         }
  291.     }
  293. }

2. 链表VS数组

时间复杂度 数组 链表
插入、删除 O(n) O(1)
随机查找 O(1) O(n)

主要区别：

  • 数组使用比较简单，存储空间是连续的；链表的存储空间是不连续的，结点与结点间通过指针建立联系。
  • 数组的大小是固定的；链表的大小不是固定的。
  • 数组可能会出现下标越界问题。
  • 声明数组时如果内存不够容易内存溢出。
  • 数组如果声明不当可能导致内存的浪费，因为即使数组声明的空间没有使用也会占用内存。

3. 链表的使用场景

  • HashMap：Java1.8中，HashMap的底层结构是，数组+链表+红黑树。
  • 红黑树
  • B+tree
  • LRU淘汰算法（最少使用淘汰算法）：通过限制链表大小，并且通过时间进行排序，超出链表大小的结点被淘汰。