Java数据结构基础丨链表

链表的基本知识

  • 链表对应的英文名称是 Linked List,是一种物理存储单元上非连续、非顺序的数据结构,由若干个节点(node)组成。每个结点包括两个部分:一个是存储数据元素的数据域(data),另一个是存储下一个结点地址的指针域(next)。
  • 链表的第一个节点被称为头结点,最后一个节点被称为尾结点,尾结点的next指针指向一个空地址 NULL。
  • 链表有很多种不同的类型:单向链表,双向链表以及循环链表......
  • 不同于数组的顺序存储,链表在内存中是随机存储

    // 链表节点,变量data存放数据,指针next指向下一个节点
     private static class Node{
         int data;
         Node next;
         Node(int data){
             this.data = data;
         }
     }

    链表的基本操作

    • 查找——时间复杂度:O(n)

      /**
      * 链表操作:查找元素
      * @param index 查找的位置
      **/
       public Node get(int index)throws Exception{
      if (index < 0 || index >= size){
          throw new IndexOutOfBoundsException("超出链表节点实际范围!");
      }
      Node temp = head;
      for(int i = 0; i < index; i++){
         temp = temp.next;
      }
      return temp;
       }
    • 插入——时间复杂度:O(1)
    /**
     * 链表操作:插入元素
     * @param data 插入的元素
     * @param index 插入的位置
     * */
    public void insert(int data, int index)throws Exception{
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("超出链表节点实际范围!!!");
        }
        Node insertedNode = new Node(data);
        if (size == 0){
            //空链表
            head = insertedNode;
            last = insertedNode;
        }else if (index == 0){
            //插入头部
            insertedNode.next = head;
            head = insertedNode;
        }else if (size == index){
            //插入尾部
            last.next = insertedNode;
            last = insertedNode;
        }else{
            //插入中间
            Node prevNode = get(index-1);
            //将新结点的 next指针指向原来旧结点的 next指针指向的内存地址
            insertedNode.next = prevNode.next;
            //将原来旧结点的 next指针指向新结点的内存地址
            prevNode.next = insertedNode;
        }
        size++;
    }
    • 删除——时间复杂度:O(1)

      /**
      * 链表操作:删除元素
      * @param index 删除的位置
      **/
       public Node remove(int index)throws Exception{
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("超出链表节点实际范围!!!");
        }
        Node removedNode = null;
        if (index == 0){
            //删除头部节点
            removedNode = head;
            head = head.next;
        }else if (index == size-1){
            //删除尾部节点
            Node prevNode = get(index-1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        }else {
            //删除中间节点
            Node prevNode = get(index-1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            //即 a>>b>>c,删除 b,只需要将 c赋值给 a.next即可
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
       }

    单向链表的应用场景

  • 撤销和回退功能。
  • 实现LRU缓存淘汰算法。
  • 判断某个字符串是否为回文字符串。
  • 实现图、HashMap等一些高级数据结构。
  • ...

循环链表

可以说,循环链表是一种特殊的单链表。它与单链表的唯一区别在于尾结点,循环链表的尾结点指针指向链表的头结点。当要处理的数据具有环形结构特点时,特别适合采用循环链表。例如,约瑟夫问题

循环链表的实现

public class CircleLinkedList {
    //指向循环链表的第一个结点
    private Node head;
    // 循环链表的长度
    private int length;
    public CircleLinkedList() {
        head = null;
        length = 0;
    }
    public Node getHead() {
        return head;
    }
    public int getLength() {
        return length;
    }

    /**
     * 尾部插入
     * @param newNode
     */
    public void insert(Node newNode) {
        if (head == null) {
            // 循环链表为空时,head 指向新的节点
            head = newNode;
        } else {
            Node temp = head;
            // 找到循环链表最后一个节点
            while (temp.next != head) {
                temp = temp.next;
            }
            // 插入新的节点
            temp.next = newNode;
        }
        // 循环链表新的结点指向 NULL
        newNode.next = head;
        // 循环链表长度加 1
        length++;
    }

    /**
     * 将新的结点插入到指定结点后
     * @param preNode 指定节点
     * @param newNode 新的节点
     */
    public void insert(Node preNode, Node newNode) {
        newNode.next = preNode.next;
        preNode.next = newNode;
        length++;
    }

    /**
     * 删除数据域为指定值的元素
     * @param e
     */
    public void del(int e) {
        Node temp = head;
        while (length >= 0) {
            // 找到数据域为 e 的结点
            if (temp.data == e) {
                if (temp.next == head) {
                    // 第一个节点
                    head = null;
                } else {
                    // 最后一个节点
                    temp.next = temp.next.next;
                }
                // 循环链表长度减 1
                length--;
                return;
            }
            // 找到下一个结点
            temp = temp.next;
        }
    }

    /**
     * 给定被删除元素的前一个结点,删除指定元素
     * @param preNode
     */
    public Node del(Node preNode) {
        Node delNode = preNode.next;
        if (delNode == head) {
            // 维护 head 的指向
            head = head.next;
        }
        // 删除
        preNode.next = preNode.next.next;
        length--;
        return delNode;
    }

    /**
     * 随机访问第 k 个结点
     * @param k
     * @return
     */
    public Node find(int k) {
        if (k <= 0) {
            throw new RuntimeException("输入的参数 k 必须大于 0");
        }
        int cnt = 1;
        Node temp = head;
        // 找到第 k 个元素
        while (cnt != k) {
            temp = temp.next;
            cnt++;
        }
        return temp;
    }

    /**
     * 打印循环链表所有有效节点
     * @return
     */
    public String printCircleLinkedList() {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        Node temp = head;
        while (head != null && cnt < getLength()) {
            sb.append(temp.data);
            sb.append(" -> ");
            temp = temp.next;
            cnt++;
        }
        sb.append(", length = ");
        sb.append(length);
        return sb.toString();
    }
}
掘金

循环链表的应用场景

  1. 约瑟夫问题。
  2. 操作系统的分时问题。
  3. 键盘的缓冲,网络收发数据包的缓冲。
  4. ...

双向链表

双向链表它的每一个节点除了有数据(data)、后继指针(next),还有前驱指针(prev)——指向前一个节点的指针。由于多了一个前驱指针,所以双向链表要更占内存,但它的效率更高,也更加实用(支持双向遍历),可以说是“空间换时间”了。
删除情况

  1. 删除节点中含有特定值的节点;
  2. 删除给定指针指向的节点。

对于第1种情况,无论是单向链表还是双向链表,都需要从头节点开始遍历查找,查找到后,再执行删除操作。
对于第2种情况,因为双向链表中拥有前驱指针,只需要O(1)的时间复杂度;而单向链表为了找到前驱节点需要遍历,则需要O(n)。同理,对于“在某个指定节点前插入一个节点”这种情况,双向链表也是O(1),单向链表也是O(n)。除此之外,对于一个有序链表,双向链表的按值查询的效率也比单向链表高一些。

双向循环链表

“缝合怪”:循环链表+双向链表(双向链表首尾相接)。

链表的优劣

  • 相较于数组,链表的内存空间消耗更大,用于储存结点指针信息。
  • 链表可以克服数组需要预先知道数据大小的缺点,充分利用计算机内存空间,实现灵活的内存动态管理。但是(单向)链表失去了数组根据下标随机读取的优点,想要找到某节点Z只能通过前一个节点Y的next指针来寻找,而想要找到节点 Y,又必须通过Y节点的前一个节点X的next指针来寻找...要找一个某一节点,必须要从头开始遍历,十分麻烦。链表的随机访问的性能没有数组好,需要O(n)的时间复杂度。
  • 数组在进行插入、删除操作时,为了保持内存数据的连续性,需要搬移大量数据,所以时间复杂度为O(n);而由于不必须按顺序存储,链表在纯粹的插入、删除操作的时候可以达到O(1);而如果考虑插入、删除操作之前需要遍历查找到元素,那么删除“特定值”操作也需要O(n)。
  • 由于链表的每个结点在内存里都是随机分布的,只是通过指针联系在一起,所以这些结点的地址并不相邻,无法利用 程序的局部性原理 来提前加载到缓存中来提升程序性能。所以,链表的查找、读取性能不及数组。如果数据以查找为主,很少涉及到增加和删除操作,那么选择数组,如果涉及到频繁的插入和删除,或元素所需分配空间过大,那么倾向于选择链表。

拓展

帅地玩编程-反转链表
码农有道-LRU缓存
掘金-链表练习
打赏
评论区
头像
文章目录