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

Java——链表（LinkedList）

article 2025/2/22 2:29:22

简介

在 Java 中，链表（LinkedList）是一种常见的线性数据结构，它的元素（节点）通过指针（或引用）连接在一起，通常有一个头节点（head）作为入口。链表的主要特点是，它在插入和删除元素时比数组更高效，因为这些操作不需要移动其他元素。

1、链表的基本概念

链表由一系列节点（Node）组成，每个节点包含两个部分：
数据部分：存储节点的数据。
指针部分：指向下一个节点的引用。
链表有几个常见的变种：
单向链表：每个节点只包含指向下一个节点的引用。
双向链表：每个节点包含指向下一个节点和前一个节点的引用。
循环链表：最后一个节点指向头节点，形成一个环。

2、Java中的LinkedList类

在 Java 中，LinkedList 类是 List 接口和 Deque 接口的实现，它基于双向链表实现。因此，LinkedList 既可以作为一个队列使用，也可以作为一个双向列表使用。

LinkedList 实现了常见的列表接口 List，所以它支持按索引访问元素。
LinkedList 也实现了 Deque 接口，支持双端队列操作（从两端插入和删除元素）。

3、LinkedList的常见方法

3-1、创建一个LinkedList

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个空的 LinkedList
        LinkedList<String> list = new LinkedList<>();
        
        // 添加元素
        list.add("Alice");
        list.add("Bob");
        list.add("Charlie");
        
        // 打印链表
        System.out.println("链表元素: " + list);
    }
}

3-2、添加元素

add(E e)：将元素 e 添加到链表的末尾。
addFirst(E e)：将元素 e 添加到链表的开头。
addLast(E e)：将元素 e 添加到链表的末尾。
offer(E e)：将元素 e 插入到链表的末尾，和 add 类似，但是在某些情况下返回 false 以指示失败。

3-3、删除元素

remove()：删除链表中的第一个元素。
removeFirst()：删除链表的第一个元素。
removeLast()：删除链表的最后一个元素。
poll()：删除并返回链表中的第一个元素。如果链表为空，返回 null。
pollFirst()：删除并返回链表的第一个元素。
pollLast()：删除并返回链表的最后一个元素。

3-4、获取元素

get(int index)：获取指定位置的元素。
getFirst()：获取第一个元素，但不移除它。
getLast()：获取最后一个元素，但不移除它。
peek()：查看链表的第一个元素，若链表为空则返回 null。
peekFirst()：查看链表的第一个元素，若链表为空则返回 null。
peekLast()：查看链表的最后一个元素，若链表为空则返回 null。