本文共 1335 字，大约阅读时间需要 4 分钟。

链表的介绍

链表是一种数据结构，通过链的方式将一系列的元素连接起来，每一个元素通常被称为 Node 节点。每个 Node 节点由两部分组成：数据值的变量和一个指向下一个节点的指针。

链表的分类

单链表、双链表、循环链表是链表的三个主要分类。

链表的核心概念

链表和数组的主要区别：

• 查询效率不同：链表没有索引，查询速度较慢，但增删操作较快。

自定义单向链表的实现

为了实现复用和代码的完整性，我们设计了一个通用的链表接口和抽象类。

链表接口（List）

该接口包含共性方法：

• size()
• isEmpty()
• contains(E element)
• add(E element)
• get(int index)
• set(int index, E element)
• add(int index, E element)
• remove(int index)
• indexOf(E element)
• clear()
• toString()

AbstractList 抽象类

该抽象类实现了 List 接口的共性方法，并为具体的链表实现提供了基础功能。

LinkedList 实现

LinkedList 类继承自 AbstractList，并通过 Node 类实现链表的具体功能。Node 类包含以下属性：

• next：指向下一个节点
• element：节点的数据值

关键实现方法：

• get(index)：根据索引获取节点数据
• indexOf(E element)：查找节点的索引
• set(index, E element)：修改节点数据
• add(index, E element)：在指定位置插入节点
• remove(index)：根据索引删除节点
• clear()：清空链表
• toString()：链表字符串表示

测试结果

以下代码展示了 LinkedList 类的基本使用：

package com.example.demo;import com.example.demo.Linked.LinkedList;public class TestLinkedList {    public static void main(String[] args) {        LinkedList linkedList = new LinkedList();        linkedList.add(11);        linkedList.add(22);        linkedList.add(33);        System.out.println(linkedList);    }}

代码执行后，输出为 [11, 22, 33]，验证了链表的基本操作功能。

链表与数组的区别总结

• 访问方式：链表用指针定位元素，效率较慢；数组直接索引用素时间复杂度更低。
• 增删效率：链表增删操作较快，尾部操作无需翻转链表。
• 空间复杂度：链表的空间复杂度较低，适合内存有限的环境。

链表的优缺点：

• 优点：增删效率高，适合动态数据结构。
• 缺点：查询效率低，需要遍历至目标节点。

这种对比帮助我们更好地理解链表的应用场景。