当前位置： 首页 > article >正文

【Java】链表（LinkedList）（图文版）

article 2025/3/19 22:14:45

本博客总结了Java当中链表的实现，以及相关方法的使用，在最后附带了一些常见链表相关处理技巧，希望对你有帮助！

ps：可拷贝到IDEA上自行测试，代码全部完成测试。

一.链表概述

1.什么是链表？

链表（LinkedList） 是一种线性数据结构，由一系列节点（Node） 通过指针（引用）连接而成，每个节点包含两部分：

数据域：存储实际的数据（可以是任意类型）

指针域：存储指向下一个节点（或前一个节点）的引用

顾名思义，就是像链子一样的数据结构，在物理内存上不要求连续，通过引用（Next）套接连接：

想要访问链表元素，只能从头结点进入，顺着链子找到下一个节点，依次访问，直到访问到为节点（Null）

2.链表的分类

链表大致可以分为以下三类：

单链表（Singly Linked List）

双链表（Doubly Linked List）

循环链表（Circular Linked List）

（1）单链表

  • 定义：每个节点仅包含一个指向下一个节点的指针（next）。

  • 特点：单向遍历，只能从头节点开始访问后续节点。

  • 终止条件：最后一个节点的next指向null。

如上图就是一个经典的单链表。

（2）双链表

  • 每个节点包含两个指针：next（指向后一个节点）和 prev（指向前一个节点）。

  • 特点：支持双向遍历，但需要更多内存存储指针。

（3）循环链表

  • 单链表的变种：最后一个节点的next指向头节点。

  • 特点：形成一个环，适合需要循环访问的场景。

  • 终止条件：遍历时需检查是否回到头节点。

（4）有头/无头指针结构

有头指针结构会有个空的指针作为专门的头指针作为入口，插入只能在头指针之后。

无头指针结构无专门的头指针，以第一个节点作为入口，可以在入口前插入。

有头/无头指针结构与上述3种链表可以任意组合，我们推荐使用有头，因为不需要考虑变更头结点，简化了操作。

为了演示一些错误和注意事项，我们使用无头结构。

3.在集合框架中的位置

属于线性表（List）的一种，能与ArrayList与Stack互转，前提是类型声明为List（之后会介绍）。

4.优缺点

（1）优点

  • 高效的增删数据（变动链式关系即可，无需关心空间顺序）
  • 动态内存（无需指定大小，因为以节点形式存在）

（2）缺点

  • 访问效率低（只能从头访问）
  • 内存开销稍大（要存储指针）

二.链表的实现

先简单看一眼Java源码：

不难发现Java使用了内部类的形式存储节点，并且LinkedList这一集合使用的是双向无头链表。

为了便于理解与复现，我们暂且不考虑泛型与io等高阶特性，而使用int存储value。

1.单链表的实现

（1）基本实现

public class MyLinkedListTest {
    private Node head;    //入口，并非哨兵节点
    private int size;     //节点数

    //节点内部类
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    
    //构造方法
    public MyLinkedListTest() {
        this.head = null;    //head指向空节点，表示初始化为空
        this.size = 0;
    }
    
    ......

（2）添加元素

//在头部插入
public void addHead(int data) {
    Node newNode = new Node(data);  // 1
    newNode.next = this.head;       // 2 
    this.head = newNode;            // 3
    this.size++;                    
}

头插示意图：

step1：

step2：

step3：

//在尾部插入
public void addTail(int data) {
    Node newNode = new Node(data);
    Node current = this.head;
   if (head == null) {        //链表为空的情况
       this.head = newNode;
   }else{                     //链表不为空的情况
       while (current.next != null) {
           current = current.next;
       }
       //改链接
       current.next = newNode;
   }
   this.size++;
}

 尾插示意图：

step1：

step2：

step3：

//在指定位置插入
public void addIndex(int index, int data) {
    //下标合法性判断
    if (index < 0 || index > size) {        
        System.out.println("illegal index");
        return;
    }
    Node newNode = new Node(data);
    //是否头插？
    if (index == 0) {
        addHead(data);
        return;
    }
    //是否尾插
    if (index == size) {
        addTail(data);
        return;
    }
    Node prev = this.head;
    Node cur = prev.next;
    //找位置
    for (int i = 1; i < index; i++) {
        prev = cur;
        cur = cur.next;
    }
    //改链接
    prev.next = newNode;
    newNode.next = cur;
}

指定位置插入示意图：

（3）遍历输出

public void display() {
    Node current = head;
    System.out.print("Head -> ");
    while (current != null) {
        System.out.print(current.val + " -> ");
        current = current.next;
    }
    System.out.println("null");
}

（4）删除元素

//删除第一个遇见的元素
public void remove(int key) {
    if (this.head == null) {
        return;
    }
    if (this.head.val == key) {
        this.head = this.head.next;
    }
    Node prev = this.head;       //当前节点的前驱节点
    Node cur = prev.next;        //当前节点
    while (cur != null) {
        if (cur.val == key) {
            //改链接
            prev.next = cur.next;
            this.size--;
            return;
        }
        //指针遍历
        prev = cur;
        cur = cur.next;
   }
   System.out.println("not find");
}

//删除所有value == key的元素
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    //头结点 val == key的情况，循环删除直到头val不为key
    while (head.val == key && head.next != null) {
        this.head = this.head.next;
    }
    //指针遍历
    Node prev = this.head;
    Node cur = prev.next;
    while (cur != null) {
        if (cur.val == key) {
            //改链接
            prev.next = cur.next;
            cur = cur.next;
            this.size--;
        }else {
            //指针遍历
            prev = cur;
            cur = cur.next;
        }
    }
}

//删除所有元素
public void clean(){
    this.head = null;
    this.size = 0;
}

删除元素示意图（cur：当前要删除的元素）：

（5）查找元素

public boolean contains(int key) {
    Node current = this.head;
    while (current != null) {
        if (current.val != key) {
            current = current.next;
            continue;
        }
        return true;
    }
    return false;
}

2.双链表的实现

（1）基本实现

public class MyLinkedList {
    //节点内部类
    private static class Node {
        int data;
        Node next;
        Node prev;

        public Node(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;
    private Node tail;
    private int size;
    
    //构造方法
    public MyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    ......

（2）添加元素

//头插法
public void addFirst(int data) {
    Node newNode = new Node(data);
    //空链表情况下
    if (this.head == null) {
        this.head = newNode;
        this.tail = newNode;

    }else{
        //非空链表情况下
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
    }
    size++;
}

//尾插法，类似头插
public void addLast(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {
        this.head = newNode;
        this.tail = this.head;
    }else{
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    size++;
}

//辅助方法，寻找下标为index的节点
private Node getNode(int index) {
    Node temp = this.head;
    for (int i = 0; i < index; i++) {
        temp = temp.next;
    }
    return temp;
}

//按下标插入
public void addAt(int index, int data) {
    Node newNode = new Node(data);
    //合法性判断
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("bad index");
    }
    if (index == 0) {
        this.addFirst(data);
    }else if(index == size){
        this.addLast(data);
    }else{
        Node place = getNode(index);
        //改链接
        newNode.next = place;
        newNode.prev = place.prev;
        place.prev.next = newNode;
        place.prev = newNode;
        size++;
    }
}

添加元素示意图：

（3）删除元素

//删除第一个元素
public void removeFirst(){
    if (this.head == null) return;
    if (this.head == tail) {
        this.head = null;
        this.tail = null;
    }else{
        this.head = this.head.next;
        this.head.prev = null;
    }
    size--;
}

//删除最后一个元素
public void removeLast(){
    if (this.tail == null) return;

    if (head == tail) {
        head = null;
        tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }
    size--;
}

//删除第一个 data == key 的元素
public void remove(int key){
    Node cur = this.head;
    //遍历
    while(cur != null){
        //判断是否找到
        if(cur.data == key){
            if(this.head == cur){
                removeFirst();
            }else if(this.tail == cur){
                removeLast();
            }else{
                //改链接
                cur.next.prev = cur.prev;
                cur.prev.next = cur.next;
                size--;
            }
            return;
        }
        //指针遍历
        cur = cur.next;
    }
}

删除元素示意图：

（4）遍历输出

// 正向遍历打印链表
public void printForward() {
    Node cur = head;
    System.out.print("Forward: null <-> ");
    while (cur != null) {
        System.out.print(cur.data + " <-> ");
        cur = cur.next;
    }
    System.out.println("null");
}

// 反向遍历打印链表
public void printBackward() {
    Node cur = tail;
    System.out.print("Backward: null <-> ");
    while (cur != null) {
        System.out.print(cur.data + " <-> ");
        cur = cur.prev;
    }
    System.out.println("null");
}

（5）其他

public int getSize() {
    return size;
}

public boolean isEmpty() {
    return size == 0;
}

......

3.循环链表的实现

循环链表就是把尾节点指向头结点，循环链表在实际开发中的使用频率相对较低，这里不过多描述，仅做简单介绍。

class CircularLinkedList {
    private Node head;
    private Node tail;

    privat static class Node {
        int data;
        Node next;

        Node(int data) { 
            this.data = data; 
        }
    }

    // 添加节点到尾部
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            tail.next = head; // 循环指向自身
        } else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head; // 新尾部指向头
        }
    }

    // 遍历打印
    public void print() {
        if (head == null) return;
        Node current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head); // 终止条件
    }

    ......

}

三.相关oj题

详情请见LeetCode

1.反转一个单链表。

206. 反转链表 - 力扣（LeetCode）

2. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

876. 链表的中间结点 - 力扣（LeetCode）

3. 输入两个链表，找出它们的第一个公共结点。

160. 相交链表 - 力扣（LeetCode）

4. 给定一个链表，判断链表中是否有环。

141. 环形链表 - 力扣（LeetCode）

四.LinkedList的使用

请参考如下代码：

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        // 1. 创建LinkedList
        LinkedList<String> linkedList = new LinkedList<>();

        // 2. 添加元素
        linkedList.add("Apple");      // 添加到末尾
        linkedList.addFirst("Banana");// 添加到头部
        linkedList.addLast("Cherry"); // 添加到末尾（同add）
        linkedList.add(1, "Durian");  // 插入到指定位置

        System.out.println("初始化链表: " + linkedList);
        // 输出: [Banana, Durian, Apple, Cherry]

        // 3. 访问元素
        System.out.println("\n访问元素演示:");
        System.out.println("getFirst(): " + linkedList.getFirst()); // Banana
        System.out.println("getLast(): " + linkedList.getLast());   // Cherry
        System.out.println("get(2): " + linkedList.get(2));         // Apple

        // 4. 删除元素
        System.out.println("\n删除操作演示:");
        linkedList.removeFirst();     // 删除头部
        linkedList.removeLast();      // 删除尾部
        linkedList.remove("Apple");   // 删除指定元素
        System.out.println("删除后: " + linkedList); // [Durian]

        // 5. 其他常用方法
        System.out.println("\n其他方法演示:");
        System.out.println("contains('Durian'): " + linkedList.contains("Durian")); // true
        System.out.println("size(): " + linkedList.size());                   // 1
        System.out.println("indexOf('Durian'): " + linkedList.indexOf("Durian"));       // 0

        // 6. 遍历方式
        System.out.println("\n遍历演示:");
        System.out.println("1. for-each循环:");
        for (String fruit : linkedList) {
            System.out.print(fruit + " ");
        }
        
        System.out.println("\n\n2. 迭代器遍历:");
        Iterator<String> it = linkedList.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }

    }
}

更多方法请参考官方api文档：LinkedList (Java Platform SE 8 )

结语

链表的理解难度算是数据结构当中比较难的了，oj题更是，对于初学者来说不建议死磕。可以等熟练了做专项练习，毕竟链表也是笔试的重难点了，难题基本都有它的影子（博主本人也被这么的不轻......）。

OK，那么本博客到此结束，下篇我们讲栈和队列，它们就友好多了。

觉得有帮助不妨点个赞，我们下期见！(*´∀ ˋ*)


http://www.kler.cn/a/591720.html

相关文章：

  • QT学习笔记1
  • c语言笔记 存储期
  • 【实习经历Two:参与开源项目，学习并应用Git】
  • 解决qt中自定插件加载失败，不显示问题。
  • 报数游戏/补种未成活胡杨[E卷-hw_od]
  • HTML 新手入门：从零基础到搭建第一个静态页面（二）
  • 将温度预测的神经网络部署到服务器端，封装成api接口步骤
  • 高级java每日一道面试题-2025年3月04日-微服务篇[Eureka篇]-Eureka是什么？
  • Blender-MCP服务源码2-依赖分析
  • 再学：函数可见性、特殊函数、修饰符
  • ArcGIS Pro 制作风台路径图：从数据到可视化
  • MySQL5.7主从复制教程
  • 【HTML】三、表单与布局标签
  • 群体智能优化算法- 豪猪优化算法 (Crested Porcupine Optimization, CPO，含Matlab源代码）
  • 深入学习恩智浦 GoPoint：探索 AI Demo 与嵌入式 AI 开发
  • IPD解读——IPD重构产品研发与产品管理
  • 25届二本：春招希望不大，要做两手准备了
  • 【多线程】线程不安全问题
  • Couchbase Analytics 的结构
  • CRM企业客户关系管理系统产品原型方案