LinkedList与链表-EW帮帮网

文章目录

前言
1. ArrayList的局限性
2. 链表
3. LinkedList源码分析与使用
4. ArrayList和LinkedList的区别

前言

本文基于课堂课件与个人学习体会，系统梳理了Java语言中线性表的核心实现——LinkedList与链表。链表作为一种基础的线性数据结构，在实现方式和应用场景上与ArrayList存在显著差异。本文将深入分析LinkedList的实现原理、特性及使用场景。

1. ArrayList的局限性

在介绍LinkedList之前，先简要回顾ArrayList的底层实现特点。ArrayList底层使用数组存储元素，这决定了其特有的优缺点。

核心源码片段（JDK 17）：

/**
 * 增加ArrayList的容量（如有必要），以确保至少能容纳指定数量的元素。
 */
public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

/**
 * 实际扩容方法，分配更大的数组并复制原有元素。
 */
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 新容量为原容量的1.5倍或满足最小需求
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 初始扩容
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

由于ArrayList底层使用的是连续内存空间，在任意位置插入或删除元素时，需要移动插入点后的所有元素，时间复杂度为O(n)。这使得ArrayList不适合频繁进行中间位置的插入和删除操作。为解决这一问题，Java集合框架提供了LinkedList链表结构。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续的数据结构，数据元素的逻辑顺序通过节点间的引用链接实现。

如图所示：

链表在逻辑上保持元素的顺序关系，但在物理存储上各节点可能分散在内存的不同位置
每个节点通常动态分配在堆内存中，节点间的物理位置没有规律性

链表结构多样，主要可从以下三个维度进行分类：

单向链表 / 双向链表
带头结点 / 不带头结点
循环链表 / 非循环链表

说明：

"头结点"是指链表中的哨兵节点，它不存储有效数据，仅作为链表入口点

"循环"指的是链表尾节点是否指回链表头部，形成环状结构

单向链表

双向循环链表

在实际应用中，以下两种链表结构最为常用：

无头单向非循环链表：结构简单，常作为其他数据结构的基础组件（如哈希表的链式地址法、图的邻接表等），也是面试中的高频考点

双向链表：Java集合框架中的LinkedList采用的就是双向链表结构，支持从两端高效访问和操作元素

2.2 链表的实现

下面以无头单向非循环链表为例，实现一个常见操作的链表结构：

// 单向无头非循环链表实现
public class SingleLinkedList implements IList {
    // 节点类，包含数据域和指向下一个节点的引用
    static class ListNode {
        public int val;         // 节点存储的数据
        public ListNode next;   // 指向下一个节点的引用

        public ListNode(int val) {
            this.val = val;
        }
    }
    
    public ListNode head; // 链表头指针
    
    // 头插法：在链表头部插入新节点
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    
    // 尾插法：在链表尾部插入新节点
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    
    // 按索引插入：在指定位置插入新节点
    @Override
    public void addIndex(int index, int data) {
        int len = size();
        if (index < 0 || index > len) {
            System.out.println("index位置不合法");
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == len) {
            addLast(data);
            return;
        }
        // 找到插入位置的前一个节点
        ListNode cur = head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }
    
    // 查找链表中是否包含指定值
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    
    // 删除第一个值等于key的节点
    @Override
    public void remove(int key) {
        if (head == null) {
            return;
        }
        // 处理头节点为目标值的情况
        if (head.val == key) {
            head = head.next;
            return;
        }
        // 查找目标节点的前驱节点
        ListNode cur = head;
        while (cur.next != null && cur.next.val != key) {
            cur = cur.next;
        }
        if (cur.next != null) {
            cur.next = cur.next.next;
        }
    }
    
    // 删除所有值等于key的节点
    @Override
    public void removeAllKey(int key) {
        if (head == null) {
            return;
        }
        // 删除头部连续等于key的节点
        while (head != null && head.val == key) {
            head = head.next;
        }
        if (head == null) return;
        
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
    }
    
    // 计算链表长度
    @Override
    public int size() {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
    
    // 清空链表
    @Override
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode nextNode = cur.next;
            cur.next = null;  // 断开引用，便于垃圾回收
            cur = nextNode;
        }
        head = null;
    }
    
    // 打印链表
    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    
    // 打印指定链表（用于算法结果展示）
    public void display2(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

实现说明：

链表操作中需特别注意边界情况的处理，如空链表、对头节点的操作等
removeAllKey方法能够删除链表中所有值为key的节点，包括连续的头节点
clear方法通过断开节点间的引用关系，便于Java垃圾回收机制回收节点内存
这种实现为通用框架，可通过扩展增加更多功能或支持其他链表变种（如带头结点链表、双向链表等）

2.2.1 链表功能测试示例

以下是使用SingleLinkedList类进行基本操作的测试代码：

public class LinkedListTest {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        
        // 头插法测试
        list.addFirst(10);
        list.addFirst(20);
        list.addFirst(30);
        System.out.print("头插法后: ");
        list.display(); // 输出: 30 20 10
        
        // 尾插法测试
        list.addLast(40);
        list.addLast(50);
        System.out.print("尾插法后: ");
        list.display(); // 输出: 30 20 10 40 50
        
        // 按索引插入测试
        list.addIndex(2, 99);
        System.out.print("索引2插入99后: ");
        list.display(); // 输出: 30 20 99 10 40 50
        
        // 查找测试
        System.out.println("是否包含40: " + list.contains(40)); // 输出: true
        System.out.println("是否包含100: " + list.contains(100)); // 输出: false
        
        // 删除单个元素测试
        list.remove(99);
        System.out.print("删除99后: ");
        list.display(); // 输出: 30 20 10 40 50
        
        // 删除所有指定元素测试
        list.addLast(10);
        list.addLast(10);
        list.removeAllKey(10);
        System.out.print("删除所有10后: ");
        list.display(); // 输出: 30 20 40 50
        
        // 获取长度测试
        System.out.println("链表长度: " + list.size()); // 输出: 4
        
        // 清空链表测试
        list.clear();
        System.out.print("清空后: ");
        list.display(); // 输出为空行
    }
}

3. LinkedList源码分析与使用

3.1 LinkedList的基本特性

LinkedList JDK 17官方文档

Java中的LinkedList采用双向链表作为底层实现。节点间通过引用链接，使得在任意位置插入或删除元素时，只需修改相关节点的引用，无需像数组那样移动元素，因此时间复杂度为O(1)。

在这里插入图片描述

如上图所示：

每个节点包含三部分：prev（前驱指针）、element（数据域）、next（后继指针）
链表通过prev和next实现双向连接，首尾节点分别由first和last引用管理
LinkedList类本身维护size、first、last等属性，便于快速访问链表状态和端点

LinkedList在Java集合框架中的继承关系如下：

在这里插入图片描述

LinkedList的核心特点：

LinkedList实现了List和Deque接口，兼具列表和双端队列的功能
底层数据结构为双向链表，适合频繁的插入和删除操作
未实现RandomAccess接口，不支持高效的随机访问（通过索引访问的时间复杂度为O(n)）
在链表两端进行操作（如addFirst、removeFirst等）的时间复杂度为O(1)
适合用作栈或队列，但如果只需要这些功能，应考虑使用专用的ArrayDeque

3.2 LinkedList的使用

3.2.1 LinkedList的构造方法

LinkedList提供了两种构造方法：

方法签名	说明
`public LinkedList()`	创建一个空链表
`public LinkedList(Collection<? extends E> c)`	使用指定集合中的元素创建一个链表

public static void main(String[] args) {
    // 创建空LinkedList
    List<Integer> numbers = new LinkedList<>();
    
    // 使用已有集合创建LinkedList
    List<String> courseList = new ArrayList<>();
    courseList.add("数据结构");
    courseList.add("操作系统");
    courseList.add("计算机网络");
    
    List<String> courses = new LinkedList<>(courseList);
}

3.2.2 LinkedList的常用方法

LinkedList同时实现了List和Deque接口，提供丰富的操作方法。

1. 添加元素

方法签名	说明
`public void addFirst(E e)`	在链表头部插入元素，时间复杂度O(1)
`public void addLast(E e)`	在链表尾部插入元素，时间复杂度O(1)
`public boolean add(E e)`	在链表尾部插入元素，等同于`addLast`
`public void add(int index, E e)`	在指定索引位置插入元素，平均O(n)

2. 删除元素

方法签名	说明
`public E removeFirst()`	移除并返回链表头部元素，时间复杂度O(1)
`public E removeLast()`	移除并返回链表尾部元素，时间复杂度O(1)
`public E remove()`	移除并返回链表头部元素，等同于`removeFirst`
`public E remove(int index)`	移除指定索引位置的元素，平均O(n)
`public boolean remove(Object o)`	移除第一个与指定对象相等的元素，平均O(n)

3. 获取元素

方法签名	说明
`public E getFirst()`	获取链表头部元素但不移除，O(1)
`public E getLast()`	获取链表尾部元素但不移除，O(1)
`public E get(int index)`	获取指定索引位置的元素，平均O(n)

4. 其他常用方法

方法签名	说明
`public int size()`	返回链表中的元素数量
`public boolean contains(Object o)`	判断链表是否包含指定元素
`public void clear()`	清空链表中的所有元素

3.2.3 LinkedList 使用示例

下面通过一个综合示例展示LinkedList的主要用法：

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        // 创建LinkedList实例
        LinkedList<String> courses = new LinkedList<>();
        
        // 添加元素示例
        courses.add("数据结构");           // 使用add方法在尾部添加元素
        courses.addLast("操作系统");       // 明确指定在尾部添加
        courses.addFirst("计算机网络");    // 在头部添加元素
        System.out.println("当前课程列表: " + courses);
        
        // 在指定位置添加元素
        courses.add(1, "计算机组成原理");  // 在索引1处添加元素
        System.out.println("添加组成原理后: " + courses);
        
        // 获取元素示例
        String firstCourse = courses.getFirst();  // 获取第一个元素
        String lastCourse = courses.getLast();    // 获取最后一个元素
        String indexCourse = courses.get(1);      // 获取索引为1的元素
        System.out.println("第一门课: " + firstCourse);
        System.out.println("最后一门课: " + lastCourse);
        System.out.println("索引1的课程: " + indexCourse);
        
        // 删除元素示例
        String removed = courses.removeFirst();   // 删除并返回第一个元素
        System.out.println("已移除课程: " + removed);
        System.out.println("移除后的列表: " + courses);
        
        courses.remove(1);                      // 移除索引为1的元素
        System.out.println("移除索引1后: " + courses);
        
        boolean isRemoved = courses.remove("数据结构");  // 移除特定元素
        System.out.println("数据结构是否已移除: " + isRemoved);
        System.out.println("当前列表: " + courses);
        
        // 判断元素是否存在
        boolean containsOS = courses.contains("操作系统");
        System.out.println("是否包含操作系统: " + containsOS);
        
        // 获取列表大小
        System.out.println("当前列表大小: " + courses.size());
        
        // 清空列表
        courses.clear();              // 移除所有元素
        System.out.println("清空后列表大小: " + courses.size());
    }
}

3.2.4 LinkedList的遍历

LinkedList作为一种集合类型，提供了多种遍历方式。由于LinkedList不支持随机访问，因此使用迭代器或增强for循环通常比使用索引访问更高效。下面介绍几种常用的遍历方式：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListTraversal {
    public static void main(String[] args) {
        // 创建并初始化一个LinkedList
        LinkedList<String> cities = new LinkedList<>();
        cities.add("北京");
        cities.add("上海");
        cities.add("广州");
        cities.add("深圳");
        cities.add("杭州");
        
        System.out.println("===== 方式1: foreach循环 =====");
        // 最简洁的遍历方式，适合只读场景
        for (String city : cities) {
            System.out.println(city);
        }
        
        System.out.println("===== 方式2: Iterator迭代器 =====");
        // 使用Iterator遍历，可以在遍历过程中安全地删除元素
        Iterator<String> iterator = cities.iterator();
        while (iterator.hasNext()) {
            String city = iterator.next();
            System.out.println(city);
            // 如果需要删除元素，可以使用iterator.remove()
            // 例如: 删除"广州"
            if (city.equals("广州")) {
                iterator.remove();  // 安全删除当前元素
            }
        }
        
        System.out.println("删除后的列表: " + cities);
        
        System.out.println("===== 方式3: ListIterator =====");
        // ListIterator支持双向遍历
        ListIterator<String> listIterator = cities.listIterator();
        System.out.println("正向遍历:");
        while (listIterator.hasNext()) {
            System.out.println(listIterator.next());
        }
        
        System.out.println("反向遍历:");
        while (listIterator.hasPrevious()) {
            System.out.println(listIterator.previous());
        }
        
        System.out.println("===== 方式4: 传统for循环+索引 =====");
        // 不推荐用于LinkedList，因为get(index)操作需要O(n)时间
        for (int i = 0; i < cities.size(); i++) {
            System.out.println(cities.get(i));
        }
    }
}

遍历方式性能比较：

foreach循环：简洁易读，适合大多数场景
Iterator：当需要在遍历过程中删除元素时，这是唯一安全的方式
ListIterator：需要双向遍历时使用
传统for循环：对LinkedList而言效率较低，每次get(i)都需要从头/尾遍历至目标位置

在实际开发中，应根据具体场景选择合适的遍历方式。如果只是简单遍历，foreach循环是不错的选择；如果需要在遍历过程中修改集合，则应使用迭代器。

实际应用时，LinkedList的遍历性能通常不如ArrayList，这是由于内存访问局部性原理导致的。如果应用场景中遍历操作频繁，而插入删除操作较少，可能需要考虑使用ArrayList替代。

4. ArrayList和LinkedList的区别

特性	ArrayList	LinkedList
存储结构	数组（物理上连续）	链表（逻辑上连续，物理上分散）
随机访问	支持O(1)	不支持（需O(n)时间）
插入/删除	需移动元素，平均O(n)	只需修改引用，O(1)（如已有位置）
内存占用	较少（仅存储元素）	较多（每个元素额外存储引用）
扩容机制	空间不足时需要扩容并复制	无容量限制，按需分配节点
应用场景	读取频繁，随机访问多	频繁插入删除，特别是两端操作
迭代性能	较好（内存连续）	较差（内存分散，缓存命中率低）

LinkedList与链表