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

LinkedList和链表

article 2025/3/18 22:44:04

在我们学习ArrayList时,就发现ArrayList有一定缺陷: 在插入或删除任意元素时,就需要将该元素的后序所有元素向后移或者向前移,这样的时间复杂度为: O(N)

所以ArrayList不适合做任意位置的多次插入和删除操作

所以我们又引入了链式存储结构,即链表

链表

基础概念

是一种物理存储结构上非连续,但是数据的逻辑结构连续(通过引入连接来实现)的存储结构,比如火车,就是由一节节车厢连接起来的,车厢就可以看作节点

在使用链表的时候,我们也需要注意几点:

  • 链式结构在逻辑上是连续的,但是物理上是不一定连续的

  • 节点一般都是从堆上申请出来的

  • 从堆上申请的空间,是按照一定的策略来分配,也就是说两次申请的空间可能连续也可能不连续

同时链表只是一种形式,所以他也有很多种结构

结构示例

  • 单向/双向链表

  • 带头/不带头链表

  • 循环/非循环链表

以下是重点掌握对象

  • 无头单向非循环链表

结构较简单,一般不会单独用来存数据,一般是作为其他数据结构的子结构

  • 无头双向链表

链表实现

实现的是无头单向非循环链表

构造节点

private Node head; // 链表的头节点
private int size;  // 链表的长度

// 内部节点类
private static class Node {
    int data;     // 节点存储的数据
    Node next;    // 指向下一个节点的引用

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

头插法

// 头插法
public void addFirst(int data) {
    Node newNode = new Node(data);
    newNode.next = head; // 新节点的next指向当前头节点
    head = newNode;     // 更新头节点为新节点
    size++;             // 链表长度增加
}

尾插法

public void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) { // 如果链表为空，直接设置为头节点
        head = newNode;
    } else {
        Node current = head;
        while (current.next != null) { // 遍历到链表末尾
            current = current.next;
        }
        current.next = newNode; // 在末尾插入新节点
    }
    size++; // 链表长度增加
}

任意位置插入

public void addIndex(int index, int data) {
    if (index < 0 || index > size) { // 检查索引是否合法
        throw new IndexOutOfBoundsException("Index is out of bounds");
    }
    if (index == 0) {
        addFirst(data); // 如果索引为0，调用头插法
    } else if (index == size) {
        addLast(data);  // 如果索引为链表长度，调用尾插法
    } else {
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < index - 1; i++) { // 遍历到索引的前一个节点
            current = current.next;
        }
        newNode.next = current.next; // 新节点的next指向当前节点的next
        current.next = newNode;    // 当前节点的next指向新节点
        size++; // 链表长度增加
    }
}

查找是否包含关键字key

public boolean contains(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            return true; // 找到关键字
        }
        current = current.next;
    }
    return false; // 未找到关键字
}

删除第一次出现关键字为key的节点

public void remove(int key) {
    if (head == null) { // 链表为空，直接返回
        return;
    }
    if (head.data == key) { // 如果头节点是要删除的节点
        head = head.next; // 更新头节点
        size--; // 链表长度减少
        return;
    }
    Node current = head;
    while (current.next != null) { // 遍历链表
        if (current.next.data == key) {
            current.next = current.next.next; // 删除节点
            size--; // 链表长度减少
            return;
        }
        current = current.next;
    }
}

删除所有值为key的节点

public void removeAllKey(int key) {
    while (head != null && head.data == key) { // 处理头节点为key的情况
        head = head.next;
        size--;
    }
    if (head == null) { // 如果链表为空，直接返回
        return;
    }
    Node current = head;
    while (current.next != null) { // 遍历链表
        if (current.next.data == key) {
            current.next = current.next.next; // 删除节点
            size--; // 链表长度减少
        } else {
            current = current.next;
        }
    }
}

得到单链表的长度

public int size() {
    return size;
}

清空链表

public void clear() {
    head = null; // 将头节点置为空
    size = 0;   // 链表长度重置为0
}

显示链表内容

public void display() {
    Node current = head;
    while (current != null) { // 遍历链表
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null"); // 链表末尾
}

输出结果

public static void main(String[] args) {
    LinkedTest list = new LinkedTest();
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.addIndex(2, 5);
    list.display(); // 输出: 0 -> 1 -> 5 -> 2 -> 3 -> null

    System.out.println("Contains 2: " + list.contains(2)); // 输出: true
    list.remove(2);
    list.display(); // 输出: 0 -> 1 -> 5 -> 3 -> null

    list.addLast(3);
    list.addLast(3);
    list.removeAllKey(3);
    list.display(); // 输出: 0 -> 1 -> 5 -> null

    System.out.println("Size: " + list.size()); // 输出: 3
    list.clear();
    list.display(); // 输出: null
}

LinkedList

基本概念

对于LinkedList的底层实现是双向链表

同时我们也要注意:

  • LinkedList实现了List接口

  • LinkedList的底层使用了双向链表

  • LinkedList没有实现RandomAccess接口,因为不支持随机访问

  • 任意位置插入和删除元素时效率比较高,时间复杂度为 O(1)

  • 当需要多次插入和删除操作时,我们可以使用LinkedList

模拟实现

构造节点

private Node head; // 链表的头节点
private Node tail; // 链表的尾节点
private int size;  // 链表的长度

// 内部节点类
private static class Node {
    int data;     // 节点存储的数据
    Node prev;    // 指向前一个节点的引用
    Node next;    // 指向下一个节点的引用

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

头插法

public void addFirst(int data) {
    Node newNode = new Node(data);
    if (head == null) { // 如果链表为空
        head = tail = newNode;
    } else {
        newNode.next = head; // 新节点的next指向当前头节点
        head.prev = newNode; // 当前头节点的prev指向新节点
        head = newNode;     // 更新头节点为新节点
    }
    size++; // 链表长度增加
}

尾插法

public void addLast(int data) {
    Node newNode = new Node(data);
    if (tail == null) { // 如果链表为空
        head = tail = newNode;
    } else {
        newNode.prev = tail; // 新节点的prev指向当前尾节点
        tail.next = newNode; // 当前尾节点的next指向新节点
        tail = newNode;     // 更新尾节点为新节点
    }
    size++; // 链表长度增加
}

任意位置插入

public void addIndex(int index, int data) {
    if (index < 0 || index > size) { // 检查索引是否合法
        throw new IndexOutOfBoundsException("Index is out of bounds");
    }
    if (index == 0) {
        addFirst(data); // 如果索引为0，调用头插法
    } else if (index == size) {
        addLast(data);  // 如果索引为链表长度，调用尾插法
    } else {
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < index; i++) { // 遍历到索引的节点
            current = current.next;
        }
        newNode.prev = current.prev; // 新节点的prev指向当前节点的prev
        newNode.next = current;     // 新节点的next指向当前节点
        current.prev.next = newNode; // 当前节点的前一个节点的next指向新节点
        current.prev = newNode;      // 当前节点的prev指向新节点
        size++; // 链表长度增加
    }
}

查找是否包含关键字key

public boolean contains(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            return true; // 找到关键字
        }
        current = current.next;
    }
    return false; // 未找到关键字
}

删除第一次出现关键字为key的节点

public void remove(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            if (current == head) { // 如果要删除的是头节点
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    tail = null; // 如果链表只有一个节点
                }
            } else if (current == tail) { // 如果要删除的是尾节点
                tail = tail.prev;
                tail.next = null;
            } else { // 如果要删除的是中间节点
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            size--; // 链表长度减少
            return;
        }
        current = current.next;
    }
}

删除所有值为key的节点

public void removeAllKey(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            if (current == head) { // 如果要删除的是头节点
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    tail = null; // 如果链表只有一个节点
                }
            } else if (current == tail) { // 如果要删除的是尾节点
                tail = tail.prev;
                tail.next = null;
            } else { // 如果要删除的是中间节点
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            size--; // 链表长度减少
        }
        current = current.next;
    }
}

得到单链表的长度

public int size() {
    return size;
}

显示链表内容

public void display() {
    Node current = head;
    while (current != null) { // 遍历链表
        System.out.print(current.data + " <-> ");
        current = current.next;
    }
    System.out.println("null"); // 链表末尾
}

清空链表

public void clear() {
    head = tail = null; // 将头节点和尾节点置为空
    size = 0;           // 链表长度重置为0
}
结果
public static void main(String[] args) {
    LinkedTest list = new LinkedTest();
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.addIndex(2, 5);
    list.display(); // 输出: 0 <-> 1 <-> 5 <-> 2 <-> 3 <-> null

    System.out.println("Contains 2: " + list.contains(2)); // 输出: true
    list.remove(2);
    list.display(); // 输出: 0 <-> 1 <-> 5 <-> 3 <-> null

    list.addLast(3);
    list.addLast(3);
    list.removeAllKey(3);
    list.display(); // 输出: 0 <-> 1 <-> 5 <-> null

    System.out.println("Size: " + list.size()); // 输出: 3
    list.clear();
    list.display(); // 输出: null
}

使用

构造方法

构造方法

说明

LinkedList()

这是一个无参构造方法，用于创建一个空的 LinkedList 实例。

public LinkedList(Collection<? extends E> c)

  • 这是一个带参构造方法，接受一个集合 c 作为参数。

  • 它会使用集合 c 中的元素来构造一个新的 LinkedList 实例。

  • 集合 c 中的元素类型必须是 LinkedList 元素类型 E 或其子类型。

public static void main(String[] args) {
    // 使用无参构造方法创建一个空的LinkedList
    LinkedList<String> list1 = new LinkedList<>();
    list1.add("A");
    list1.add("B");
    System.out.println("list1: " + list1); // 输出: list1: [A, B]

    // 使用ArrayList作为集合容器
    Collection<String> collection = new ArrayList<>();
    collection.add("C");
    collection.add("D");

    // 使用带参构造方法创建LinkedList
    LinkedList<String> list2 = new LinkedList<>(collection);
    System.out.println("list2: " + list2); // 输出: list2: [C, D]
}

常用方法

方法

说明

boolean add(E e)

将元素 e 插入到列表的末尾。

void add(int index, E element)

将元素 element 插入到列表的指定 index 位置。

boolean addAll(Collection<? extends E> c)

将集合 c 中的所有元素插入到列表的末尾。

E remove(int index)

删除并返回列表中指定 index 位置的元素。

boolean remove(Object o)

删除列表中第一次出现的指定元素 o。

E get(int index)

返回列表中指定 index 位置的元素。

E set(int index, E element)

将列表中指定 index 位置的元素替换为 element，并返回原来的元素。

void clear()

清空列表中的所有元素。

boolean contains(Object o)

判断列表中是否包含指定元素 o。

int indexOf(Object o)

返回列表中第一个出现的指定元素 o 的索引，如果不存在则返回 -1。

int lastIndexOf(Object o)

返回列表中最后一个出现的指定元素 o 的索引，如果不存在则返回 -1。

List<E> subList(int fromIndex, int toIndex)

返回列表中从 fromIndex（包含）到 toIndex（不包含）之间的子列表。

使用
public static void main(String[] args) {
    List<String> list = new ArrayList<>();

    // 添加元素
    list.add("A"); // 尾插
    list.add(0, "B"); // 在索引0处插入
    System.out.println("After add: " + list); // 输出: [B, A]

    // 添加集合
    List<String> anotherList = new ArrayList<>();
    anotherList.add("C");
    anotherList.add("D");
    list.addAll(anotherList); // 尾插集合
    System.out.println("After addAll: " + list); // 输出: [B, A, C, D]

    // 删除元素
    list.remove(1); // 删除索引1的元素
    System.out.println("After remove by index: " + list); // 输出: [B, C, D]
    list.remove("C"); // 删除第一个出现的"C"
    System.out.println("After remove by object: " + list); // 输出: [B, D]

    // 获取和设置元素
    System.out.println("Element at index 1: " + list.get(1)); // 输出: D
    list.set(1, "E"); // 设置索引1的元素为"E"
    System.out.println("After set: " + list); // 输出: [B, E]

    // 判断是否包含元素
    System.out.println("Contains 'B': " + list.contains("B")); // 输出: true

    // 查找元素索引
    System.out.println("Index of 'E': " + list.indexOf("E")); // 输出: 1

    // 清空列表
    list.clear();
    System.out.println("After clear: " + list); // 输出: []

    // 子列表
    list.add("F");
    list.add("G");
    list.add("H");
    List<String> subList = list.subList(1, 3); // 获取子列表
    System.out.println("SubList: " + subList); // 输出: [G, H]
}
结果

遍历

有两种遍历,for循环遍历和使用迭代器遍历(正向+反向)

public static void main(String[] args) {
    List<String> list = new ArrayList<>();

    list.add("A");
    list.add("B");
    list.add("C");
    list.add("D");
    list.add("E");
    list.add("F");
    list.add("G");
    System.out.println(list);

    // for循环遍历
    for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i)+" ");
    }
    System.out.println();

    // 使用迭代器遍历---正向遍历
    ListIterator<String> it = list.listIterator();
    while (it.hasNext()) {
        System.out.print(it.next() + " ");
    }
    System.out.println();

    // 使用反向迭代器---反向遍历
    ListIterator<String> rit = list.listIterator(list.size());
    while (rit.hasPrevious()) {
        System.out.print(rit.previous() + " ");
    }
    System.out.println();
}

ArrayList和LinkedList区别

特性

ArrayList

LinkedList

底层数据结构

动态数组

双向链表

内存占用

较少（仅存储数据和部分容量）

较多（每个节点需要存储前后指针）

随机访问性能

快（通过索引直接访问，时间复杂度 O(1)）

慢（需要遍历链表，时间复杂度 O(n)）

插入/删除性能

慢（需要移动元素，时间复杂度 O(n)）

快（只需修改指针，时间复杂度 O(1)）

头插/头删性能

慢（需要移动所有元素）

快（只需修改头节点指针）

尾插/尾删性能

快（直接操作尾部）

快（直接操作尾部）

中间插入/删除性能

慢（需要移动元素）

快（只需修改指针）

内存连续性

连续内存空间

非连续内存空间

适用场景

频繁随机访问、少量插入删除

频繁插入删除、少量随机访问

扩容机制

动态扩容（默认 1.5 倍）

无需扩容（动态添加节点）

空间浪费

可能存在（预留容量）

无（按需分配节点）

实现接口

实现 List 接口

实现 List 和 Deque 接口

线程安全

非线程安全

非线程安全


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

相关文章：

  • 【MySQL】从零开始：掌握MySQL数据库的核心概念
  • containerd 拉取镜像的工具以及优劣
  • 系统架构设计师—案例分析—架构评估
  • LLM论文笔记 24: A Theory for Length Generalization in Learning to Reason
  • QT非UI设计器生成界面的国际化
  • Java 买百鸡问题
  • Google内购 Java服务端（Springboot）校验订单详细流程
  • 日志存储与分析
  • [贪心算法] 摆动序列
  • Matlab 汽车ABS实现模糊pid和pid控制
  • JVM垃圾回收器全面解析：从核心概念到选型指南
  • Matlab 经验模态分解和时频图绘制
  • 结构型模式之外观模式：让复杂系统变简单的利器
  • golang中的结构体
  • FlowGram 简介：开源前端流程搭建引擎
  • iPaaS集成平台轻量化架构的重要性
  • 国际数字影像产业园，超甲级地标招商进行中​
  • 重生之我在学Vue--第17天 Vue 3 项目优化与部署
  • 本地部署github上资源可能出现问题总结
  • 以太坊AI代理与PoS升级点燃3月市场热情，2025年能否再创新高？