【面试算法笔记】0201-链表-链表理论基础

面试算法笔记 2026年5月·算法 LeetCode

zbhgis 浩瀚地学307 字2 分钟

创建于 2026/5/2更新于 2026/5/2

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

链表的概念

什么是链表？链表是一种物理存储单元上非连续、非顺序的线性结构。

组成：每个节点（Node）包含两部分。

数据域 (val)：存储具体的值。

指针域 (next)：存放指向下一个节点的地址（指针）。

终止条件：最后一个节点的指针域通常指向 null（空指针），表示链表结束。

链表的类型

单链表：每个节点只有一个指针指向下一个节点

双链表：每个节点有两个指针，分别指向前驱和后继

循环链表：尾节点指向头节点，形成一个环

链表的存储方式

在内存中是散乱分布的，通过指针将各个节点连接起来。

链表的基本操作

删除节点

添加节点

单链表定义（操作见算法）

Java

public class ListNode {
    int val;
    ListNode next;
    
    public ListNode() {};
    public ListNode(int val) {this.val = val;}
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

双链表定义（操作见算法）

Java

public class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    
    public ListNode() {};
    public ListNode(int val) {this.val = val;}
    public ListNode(int val, ListNode prev, ListNode next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

链表的性能分析

查询O(n) 增删O(1)

参考

https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html