程序员经验分享-hwhale

深入理解链表：一种动态的线性数据结构

2023-11-18

前言

链表是我们在日常编程中经常使用的一种数据结构，它相比于数组具有更好的动态性能。但是，对链表的深入理解需要我们掌握其内在的逻辑结构和操作原理。本文将带领读者一起深入理解链表的概念、种类、特性及其在Java中的具体实现方式。

我们将从最简单的单向链表开始，探讨如何通过Java代码实现它的主要操作，如添加、遍历、插入和删除节点等。然后，我们会讨论更复杂的链表类型，如带有哨兵节点的链表，双向链表和环形链表，分析它们的优缺点以及适用的场景。

1. 概述

链表是一种基本的数据结构，用于维护数据元素的线性集合。链表中的元素（通常称为节点）不一定在内存中是连续存储的。相反，每个元素都包含了指向其下一个元素的指针或引用。这种数据结构的特性，使得插入或删除元素的操作相对于数组等连续存储的数据结构来说，更加方便和高效。

链表的类型主要有以下几种：
在这里插入图片描述

  • 单向链表，每个元素只知道其下一个元素是谁

image-20221110083407176

  • 双向链表，每个元素知道其上一个元素和下一个元素

image-20221110083427372

  • 循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head

image-20221110083538273

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

image-20221110084611550
随机访问性能

链表的随机访问性能并不强大。如果需要根据索引查找特定的元素，必须从头节点开始，逐一遍历节点直到找到目标节点。因此，此操作的时间复杂度为 O ( n ) O(n) O(n)，其中 n n n 为链表的长度。

插入或删除性能

链表在插入或删除节点时的性能主要取决于操作的位置：

  • 在头节点进行插入或删除：由于头节点可以被立即访问，因此在链表的起始位置进行插入或删除操作的时间复杂度为 O ( 1 ) O(1) O(1)。

  • 在尾节点进行插入或删除：如果已知尾节点（即尾节点的引用已经被保存），则在链表的结束位置进行插入或删除操作的时间复杂度为 O ( 1 ) O(1) O(1)。然而，如果尾节点未知，我们需要从头节点开始遍历链表以找到尾节点，这使得时间复杂度升至 O ( n ) O(n) O(n)。

  • 在中间位置进行插入或删除：这涉及两个步骤，首先需要找到目标位置（这部分的时间复杂度为 O ( n ) O(n) O(n)），然后进行实际的插入或删除操作（这部分的时间复杂度为 O ( 1 ) O(1) O(1)）。因此，总的时间复杂度为 O ( n ) + O ( 1 ) = O ( n ) O(n) + O(1) = O(n) O(n)+O(1)=O(n)。

2. 单向链表

根据单向链表的定义，首先定义一个存储 value 和 next 指针的类 Node，和一个描述头部节点的引用

public class SinglyLinkedList {
    
    private Node head; // 头部节点
    
    private static class Node { // 节点类
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
  • Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构
  • 定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义

头部添加

public class SinglyLinkedList {
    // ...
    public void addFirst(int value) {
		this.head = new Node(value, this.head);
    }
}
  • 如果 this.head == null，新增节点指向 null，并作为新的 this.head
  • 如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.head
    • 注意赋值操作执行顺序是从右到左

while 遍历

public class SinglyLinkedList {
    // ...
    public void loop() {
        Node curr = this.head;
        while (curr != null) {
            // 做一些事
            curr = curr.next;
        }
    }
}

for 遍历

public class SinglyLinkedList {
    // ...
    public void loop() {
        for (Node curr = this.head; curr != null; curr = curr.next) {
            // 做一些事
        }
    }
}
  • 以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来
    • Consumer 的规则是一个参数，无返回值，因此像 System.out::println 方法等都是 Consumer
    • 调用 Consumer 时，将当前节点 curr.value 作为参数传递给它

迭代器遍历

public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    private class NodeIterator implements Iterator<Integer> {
        Node curr = head;
        
        public boolean hasNext() {
            return curr != null;
        }

        public Integer next() {
            int value = curr.value;
            curr = curr.next;
            return value;
        }
    }
    
    public Iterator<Integer> iterator() {
        return new NodeIterator();
    }
}
  • hasNext 用来判断是否还有必要调用 next
  • next 做两件事
    • 返回当前节点的 value
    • 指向下一个节点
  • NodeIterator 要定义为非 static 内部类，是因为它与 SinglyLinkedList 实例相关，是对某个 SinglyLinkedList 实例的迭代

递归遍历

public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    public void loop() {
        recursion(this.head);
    }

    private void recursion(Node curr) {
        if (curr == null) {
            return;
        }
        // 前面做些事
        recursion(curr.next);
        // 后面做些事
    }
}

尾部添加

public class SinglyLinkedList {
    // ...
    private Node findLast() {
        if (this.head == null) {
            return null;
        }
        Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }
    
    public void addLast(int value) {
        Node last = findLast();
        if (last == null) {
            addFirst(value);
            return;
        }
        last.next = new Node(value, null);
    }
}
  • 注意，找最后一个节点，终止条件是 curr.next == null
  • 分成两个方法是为了代码清晰，而且 findLast() 之后还能复用

尾部添加多个

public class SinglyLinkedList {
    // ...
	public void addLast(int first, int... rest) {
        
        Node sublist = new Node(first, null);
        Node curr = sublist;
        for (int value : rest) {
            curr.next = new Node(value, null);
            curr = curr.next;
        }
        
        Node last = findLast();
        if (last == null) {
            this.head = sublist;
            return;
        }
        last.next = sublist;
    }
}
  • 先串成一串 sublist
  • 再作为一个整体添加

根据索引获取

public class SinglyLinkedList {
    // ...
	private Node findNode(int index) {
        int i = 0;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (index == i) {
                return curr;
            }
        }
        return null;
    }
    
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }
    
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return node.value;
        }
        throw illegalIndex(index);
    }
}
  • 同样，分方法可以实现复用

插入

public class SinglyLinkedList {
    // ...
	public void insert(int index, int value) {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1); // 找到上一个节点
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        prev.next = new Node(value, prev.next);
    }
}
  • 插入包括下面的删除，都必须找到上一个节点

删除

public class SinglyLinkedList {
    // ...
	public void remove(int index) {
        if (index == 0) {
            if (this.head != null) {
                this.head = this.head.next;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }
    }
}
  • 第一个 if 块对应着 removeFirst 情况
  • 最后一个 if 块对应着至少得两个节点的情况
    • 不仅仅判断上一个节点非空，还要保证当前节点非空

3. 单向链表（带哨兵）

观察之前单向链表的实现，发现每个方法内几乎都有判断是不是 head 这样的代码，能不能简化呢？

用一个不参与数据存储的特殊 Node 作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表

public class SinglyLinkedListSentinel {
    // ...
    private Node head = new Node(Integer.MIN_VALUE, null);
}
  • 具体存什么值无所谓，因为不会用到它的值

加入哨兵节点后，代码会变得比较简单，先看几个工具方法

public class SinglyLinkedListSentinel {
    // ...
    
    // 根据索引获取节点
    private Node findNode(int index) {
        int i = -1;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (i == index) {
                return curr;
            }
        }
        return null;
    }
    
    // 获取最后一个节点
    private Node findLast() {
        Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }
}
  • findNode 与之前类似，只是 i 初始值设置为 -1 对应哨兵，实际传入的 index 也是 [ − 1 , ∞ ) [-1, \infty) [−1,∞)
  • findLast 绝不会返回 null 了，就算没有其它节点，也会返回哨兵作为最后一个节点

这样，代码简化为

public class SinglyLinkedListSentinel {
    // ...
    
    public void addLast(int value) {
        Node last = findLast();
        /*
        改动前
        if (last == null) {
            this.head = new Node(value, null);
            return;
        }
        */
        last.next = new Node(value, null);
    }
    
    public void insert(int index, int value) {
        /*
        改动前
        if (index == 0) {
            this.head = new Node(value, this.head);
            return;
        }
        */
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1);
        if (prev != null) {
            prev.next = new Node(value, prev.next);
        } else {
            throw illegalIndex(index);
        }
    }
    
    public void remove(int index) {
        /*
        改动前
        if (index == 0) {
            if (this.head != null) {
                this.head = this.head.next;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        */
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }
    }
    
    public void addFirst(int value) {
        /*
        改动前
        this.head = new Node(value, this.head);
        */
		this.head.next = new Node(value, this.head.next);
        // 也可以视为 insert 的特例, 即 insert(0, value);
    }
}
  • 对于删除，前面说了【最后一个 if 块对应着至少得两个节点的情况】，现在有了哨兵，就凑足了两个节点

4. 双向链表（带哨兵）

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    private final Node head;
    private final Node tail;

    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.prev = head;
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void removeFirst() {
        remove(0);
    }

    public void addLast(int value) {
        Node prev = tail.prev;
        Node added = new Node(prev, value, tail);
        prev.next = added;
        tail.prev = added;
    }

    public void removeLast() {
        Node removed = tail.prev;
        if (removed == head) {
            throw illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    public void insert(int index, int value) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }

    public void remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = prev.next;
        if (removed == tail) {
            throw illegalIndex(index);
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}

5. 环形链表（带哨兵）

双向环形链表带哨兵，这时哨兵既作为头，也作为尾

image-20221229144232651

image-20221229143756065

image-20221229153338425

在这里插入图片描述

参考实现

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private final Node sentinel = new Node(null, -1, null); // 哨兵

    public DoublyLinkedListSentinel() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    /**
     * 添加到第一个
     * @param value 待添加值
     */
    public void addFirst(int value) {
        Node next = sentinel.next;
        Node prev = sentinel;
        Node added = new Node(prev, value, next);
        prev.next = added;
        next.prev = added;
    }

    /**
     * 添加到最后一个
     * @param value 待添加值
     */
    public void addLast(int value) {
        Node prev = sentinel.prev;
        Node next = sentinel;
        Node added = new Node(prev, value, next);
        prev.next = added;
        next.prev = added;
    }
    
    /**
     * 删除第一个
     */
    public void removeFirst() {
        Node removed = sentinel.next;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个
     */
    public void removeLast() {
        Node removed = sentinel.prev;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    /**
     * 根据值删除节点
     * <p>假定 value 在链表中作为 key, 有唯一性</p>
     * @param value 待删除值
     */
    public void removeByValue(int value) {
        Node removed = findNodeByValue(value);
        if (removed != null) {
            Node prev = removed.prev;
            Node next = removed.next;
            prev.next = next;
            next.prev = prev;
        }
    }

    private Node findNodeByValue(int value) {
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

}

6. 结语

通过对链表的深入学习和理解，我们可以看到，链表并不只是一个简单的数据结构，它在解决许多编程问题上具有独特的优势。学会有效地使用和优化链表，可以帮助我们写出更高效、更易维护的代码。

希望本文能够帮助读者更好地理解链表这一数据结构，并能在实际编程中灵活运用。链表只是数据结构中的一小部分，接下来我们将继续深入探讨其他更复杂的数据结构，如树、图等。让我们共同期待！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

链表

深入理解链表：一种动态的线性数据结构 的相关文章

  • Linux面试题

    文章目录 Linux 概述 什么是Linux Unix和Linux有什么区别 什么是 Linux 内核 Linux的基本组件是什么 Linux 的体系结构 BASH和DOS之间的基本区别是什么 Linux 开机启动过程 Linux系统缺省的

  • 存储器3-DDR SDRAM双倍速率同步动态存储器

    1 信号电平 采用STTL 2电平 2 5V 标准 VIH AC Vref 0 31 VIH DC Vref 0 15 VIL DC Vref 0 15 VIL AC Vref 0 31 高于VIH AC 为高 纹波只要不低于VIL DC

  • Angular_项目完善搜索功能(表单处理)

    在商品名称和商品价格以及商品类别都输入或者选择合法的情况下才能进行搜索 一 product service ts添加一个新的方法 获取所有商品类别 getAllCategories string return 电子产品 硬件设备 其他 二

  • 57 KVM工具使用指南-制作 LibcarePlus 热补丁

    文章目录 57 KVM工具使用指南 制作 LibcarePlus 热补丁 57 1 概述 57 2 手动制作 57 3 通过脚本制作 57 KVM工具使用指南 制作 LibcarePlus 热补丁 57 1 概述 LibcarePlus 支

随机推荐

  • 常见JDBC连接数据库字符串

    1 Mysql 驱动类 com mysql jdbc Driver 连接字符串 jdbc mysql localhost 3306 dbname 2 Oracle 驱动类 oracle jdbc driver OracleDriver 连接

  • 【数据库】Sqlite数据库

    1 sqlite数据库简介 SQLite是内嵌在Python中的轻量级 基于磁盘文件袋额数据库管理系统 就是一个文件 不需要安装和配置服务 支持使用SQL语句来访问数据库 该数据库使用C语言开发 支持大多数SQL91标准 支持原子的 一致的

  • c++ 共享内存方法实现windows进程通信

    主要逻辑 1 进程1 2通过读写一块共享内存完成这2个进程间的通信 2 进程互斥锁Mutex作用是实现进程同步 防止进程2一直读 实现进程1写一次进程2读一次 进程1代码 发送数据 include

  • keil新工程编译问题

    1 新建工程 找不到first和last 需要在工程中添加相对应芯片的start XXX swenjian 2 移植操作系统 error L6200E Symbol SysTick Handler multiply defined 这是在操

  • cuda矩阵乘法(简单理解)

    提示 文章写完后 目录可以自动生成 如何生成可参考右边的帮助文档 CUDA矩阵乘法 矩阵规模 一 一维并行 1 一维线程并行 thread 2 一维块线程并行 block 3 一维共享A一行程并行 shared 二 二维并行 1 共享存储二

  • 差分 【一维差分和二维差分】

    全文目录 一维差分 差分数组的构建 二维差分 差分矩阵的构建 一维差分 首先来了解一下差分的性质 差分是前缀和的逆运算 如果说前缀和是 S f n 那么差分就是 D f 1 n 也就是说 原数组是差分数组的前缀和 原数组 a i 差分数组

  • 自动化测试系列 —— UI自动化测试

    UI 测试是一种测试类型 也称为用户界面测试 通过该测试 我们检查应用程序的界面是否工作正常或是否存在任何妨碍用户行为且不符合书面规格的 BUG 了解用户将如何在用户和网站之间进行交互以执行 UI 测试至关重要 通过执行 UI 测试 测试人

  • 全球及中国可穿戴医疗设备市场潜力分析与投资动态调研报告2022-2028年

    全球及中国可穿戴医疗设备市场潜力分析与投资动态调研报告2022 2028年 修订日期 2022年2月 出版单位 鸿晟信合研究院 对接人员 周文文 内容分析有删减 了解详情可查看咨询鸿晟信合研究院专员 目录 第一章 可穿戴医疗设备行业相关概述

  • VS2019或者VS2017创建ASP.NET项目

    最近在学 NET Web应用程序开发 做个记录 默认大家的本机的IIS服务已经搭建好了 没有搭建好的自行百度 文章目录 首先是VS的相关配置 然后是项目的创建 发布网站 项目的发布 IIS配置 一 首先是VS的相关配置 首先打开VS2019

  • C# 获取本地主机IP地址

  • 数据库----------唯一约束、默认约束、零填充约束

    目录 1 唯一约束 Unique 1 概念 2 语法 3 添加唯一约束 4 删除唯一约束 2 默认约束 default 1 概念 2 语法 3 添加默认约束 4 删除默认约束 3 零填充约束 zerofill 了解即可 1 概念 2 操作

  • R语言基础

    专注系列化 高质量的R语言教程 推文索引 联系小编 付费合集 本篇总结一些关于工具包的问题 所指的 工具包 对应的英文原文是package s 本篇目录如下 1 工具包简介 2 安装工具包 2 1 CRAN 2 2 GitHub 2 3 离

  • SQL注入——DNSLOG注入

    SQL注入 DNSLOG注入 SQL注入 DNSLOG注入 SQL注入 DNSLOG注入 一 原理 一 原理 当我们遇到盲注漏洞的时候 注入过程没有回显 手工测试会花费大量的时间 如果用sqlmap跑数据的话 实际应用中很可能被目标服务器直

  • 如何在PyCharm中对自己的pySC2 Agent代码进行Debug

    PySC2环境在Win10系统上的部署与安装 请参考 https blog csdn net qq 38962621 article details 112798659 spm 1001 2014 3001 5501 PySC2自定义Age

  • docker单机编排工具docker-compose

    编排工具安装 本文为在linux系统中操作 首先是安装epel源 然后安装python的pip组件 利用pip安装docker compose 在安装完毕后 可以使用查看版本命令以及帮助命令查看所支持的子命令 wget O etc yum

  • CRM管理软件有哪些？这5款好用的CRM软件值得推荐！

    CRM软件最常在销售部门实施 作为销售人员自动化的中心枢纽 包括联系人 客户和机会管理 CRM软件通常与其他企业解决方案 例如ERP系统 营销自动化软件和客户服务软件 分开交付 但通常与其他业务应用程序集成以促进增强和协调的客户体验 目前市

  • 嵌入式常用通讯协议1（UART 、RS232、RS485、SPI、IIC）

    目录 1 常用通讯协议汇总 2 常见的电平信号及其电气特性 2 1 TTL电平 2 2 CMOS电平标准 2 3 RS232标准 2 4 RS485标准 3 UART 通用异步收发器 协议 3 1 UART定义 3 2 UART作用 3 3

  • LeetCode刷题C++

    5 最长回文字符串 给你一个字符串 s 找到 s 中最长的回文子串 划定步长 遍历判断 class Solution public string longestPalindrome string s if s size lt 2 retur

  • Vue 引入G2图表

    安装G2依赖 npm install antv g2 npm install antv data set vue ge 在Vue main js文件中引入G2 import G2 from antv g2 Vue use G2 模板中使用完

  • 深入理解链表：一种动态的线性数据结构

    文章目录 前言 1 概述 2 单向链表 3 单向链表 带哨兵 4 双向链表 带哨兵 5 环形链表 带哨兵 6 结语 前言 链表是我们在日常编程中经常使用的一种数据结构 它相比于数组具有更好的动态性能 但是 对链表的深入理解需要我们掌握其内在

热门标签