【算法之旅】基础数据结构之链表(一)

简介: 【算法之旅】基础数据结构之链表(一)

一、概述


定义


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


In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.


可以分类为


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


dbd4f8a2705770bc8b81bff14b92cb2b_3173af5e66d56d59dd889a20b79b7fbe.png


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


ae8b3308000ca3c9da68722524a12359_0096ba478c631ba2adc080f9bbae6948.png


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


2533de4298344697cbffc0b07146cd7b_4371c3320cf4e2b654c997f88b5274f4.png


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


ca3aa59a597b30a4e9da2601ef0d15f4_468502cf4ce00a2f8b91bbf682578da9.png


随机访问性能


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


插入或删除性能


起始位置:O ( 1 ) O(1)O(1)

结束位置:如果已知 tail 尾节点是 O ( 1 ) O(1)O(1),不知道 tail 尾节点是 O ( n ) O(n)O(n)

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


二、单向链表


根据单向链表的定义,首先定义一个存储 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 块对应着至少得两个节点的情况

不仅仅判断上一个节点非空,还要保证当前节点非空

相关文章
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
69 1
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
81 0
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
188 10
 算法系列之数据结构-二叉树
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
191 22
|
5月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
102 0
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
199 30
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
305 25
|
7月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
282 23
|
5天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)

热门文章

最新文章