掘金 后端 ( ) • 2024-04-10 09:42
全网最全Java数据结构教程——线性表
线性 全网 教程 数据

列表(List)/线性表

综述：

List是一种有序的集合，它是Java集合框架的一部分，它允许我们执行一系列集合操作（增、删、查），是最为基础的集合。

但是，需要特别指出的是，List是一个接口，这也意味着，它没有办法通过它自身的构造方法完成构造，需要依靠其他方法完成，例如ArrayList和LinkedList

列表有两种形式:

  1. 一种是顺序结构的顺序表
  2. 另一种是链式结构的链表

顺序表

  • 优点：高效的随即访问和快速尾部插入。
  • 缺点：中间插入和删除相对较慢；内存需求严格，需要连续内存地址。

链表

  • 优点：

1. 内存占用并不严格，不需要连续内存地址；

2.插入和删除元素效率高，迭代器性能好。

  • 缺点：随即访问较慢。

Java实现

Java提供了多种方式实现列表，如Arrays、ArrayList、LinkedList等。

在下面的文章中，我们会重点介绍这几种实现方式，也许还会有我们自己实现这些功能的章节…

List 接口的常用实现类:

  • **ArrayList**: 基于动态数组的实现，提供快速的随机访问和高效的遍历。
  • **LinkedList**: 基于双向链表的实现，提供更高效的元素插入和删除。
  • **Vector**: 和 ArrayList 类似，但它是同步的，适用于多线程环境。
  • **Stack**: 继承自 Vector，表示后进先出（LIFO）的堆栈。

一些简单的示例：

在Java中创建List的方式有很多，这取决于您想要使用的具体List类型。以下是一些创建List的常见方法：

  1. 使用ArrayList：

    List<String> arrayList = new ArrayList<>();

  2. 使用LinkedList：

    List<String> linkedList = new LinkedList<>();

  3. 使用Vector：

    List<String> vector = new Vector<>();

  4. 使用Arrays.asList：

    List<String> fixedSizeList = Arrays.asList("元素1", "元素2", "元素3");

  5. 使用Collections工具类：

    List<String> emptyList = Collections.emptyList();
List<String> singletonList = Collections.singletonList("单一元素");

  6. 使用Java 9+的of()方法：

    List<String> streamList = List.of("元素1", "元素2", "元素3");

每种方法都有其特定的用途和优势。例如，ArrayList适合频繁的随机访问，而LinkedList更适合频繁的插入和删除操作。Arrays.asList和Collections工具类提供的列表是不可变的，适合创建固定内容的列表。of()方法则提供了一种现代且灵活的方式来创建和操作列表。

在Java中，of() 方法是Java 9及更高版本中引入的，用于创建不可变的集合。这个方法可以用于 List、Set 和 Map 接口，以一种简洁的方式一次性添加多个元素。以下是支持 of() 方法的集合接口：

  • List：可以使用 List.of() 创建一个包含任意数量元素的不可变列表。
  • Set：可以使用 Set.of() 创建一个包含任意数量元素的不可变集合，但不能有重复的元素。
  • Map：可以使用 Map.of() 或 Map.ofEntries() 创建一个包含任意数量键值对的不可变映射。

请注意，使用 **of()** 方法创建的集合是不可变的，这意味着一旦创建，就不能再添加、删除或修改集合中的元素。如果您尝试修改这些集合，将会抛出 **UnsupportedOperationException**。

例如，创建一个不可变的 List：

List<String> immutableList = List.of("Element1", "Element2", "Element3");

创建一个不可变的 Set：

Set<String> immutableSet = Set.of("Element1", "Element2", "Element3");

创建一个不可变的 Map：

Map<String, Integer> immutableMap = Map.of("Key1", 1, "Key2", 2, "Key3", 3);

---分割线---这里是分割线---分割线---

接下来我将进一步介绍两种列表格式的实现细节

---分割线---这里是分割线---分割线---

顺序表(Arrays/ArraysList)

顺序表的简介

引入

什么是顺序表？

在上一章中我们介绍了List接口的相关信息，我们了解了，我们无法通过直接使用接口对应的构造方法来构造一个List实例，但是，我们可以借助于其他类来实现。

我们还知道，List有两种结构——顺序表式和链表式，它们分别用不同的类完成实例构造。接下来的本章将着重介绍顺序表式的实例构建、使用。

Java中的顺序表

在 Java 中，顺序表通常是指用数组实现的线性表。顺序表是一种基本的数据结构，它通过一段连续的存储空间来存储元素，使得数据元素在物理位置上也是连续的。这种结构使得顺序表在随机访问元素时非常高效，因为可以直接通过索引来访问任何元素。

顺序表的特点:

  • 随机访问: 可以快速访问任何位置的元素。
  • 空间效率: 由于元素存储在连续的内存空间中，所以空间利用率高。
  • 插入和删除操作: 在顺序表中间插入或删除元素需要移动后续的所有元素，因此这些操作的时间复杂度为 O(n)。

顺序表的基本操作:

  • 添加元素: 可以在顺序表的末尾或指定位置添加元素。
  • 删除元素: 可以删除顺序表中的特定元素或指定位置的元素。
  • 查找元素: 可以根据值或索引查找元素。
  • 修改元素: 可以修改顺序表中指定位置的元素。
  • 清空顺序表: 可以清除顺序表中的所有元素。

数组（Arrays）

没错！你没有看错，又是我们的老朋友——数组哒！！😉

😼数组妹妹：没想到吧~人家还是一种数据结构嘞！昨日你对我爱答不理，今日我让你高攀不起，哼~~

其实啊，这句话还真没错，毕竟大部分的线性结构都可以用数组来进行模拟…

好了，玩笑话也差不多了，该正经开始今天的学习环节喽。接下来我将更深入的介绍数组在数据结构中使用的种种方式。

数组本身其实就是一种线性的数据结构，大家可以回忆一下之前所学过的关于数组的知识_（如果需要的话，可以看我之前的关于数组基础介绍的文章）_

我们都了解，数组中一般只能存放同种类型的数据元素。这是由于我们在定义数组时，需要告诉编译器数组的大小，所以会有类似：int [] IsIntArrays的声明语句，这是编译器定量分配大小的前提。

但是，如果我的项目需要实现在一个数组中放入不同类型的元素时我该怎么做？有两种方式可以完成这个需求：其一就是下文即将介绍的ArrayList线性列表类（这种方式之后会具体介绍）；其二便是使用一个叫做对象数组的东西来完成。

下面我将用例子说明对象数组：

// Java @SecopraX
// Object数组
Object [] arr = new Object[3];
		
arr[0] = "Hello,World";
arr[1] = 147456;
arr[2] = 3.14159265758;

System.out.println(Arrays.toString(arr));  //输出：[Hello,World, 147456, 3.14159265758]

根据上面的代码我们不难发现，以Object为类型的数组完美的实现了在一个数组中存储多种类型变量的需求，怎么你不信？那我们不妨在加一段代码：

System.out.println(arr[0] instanceof String);
System.out.println(arr[1] instanceof Integer);
System.out.println(arr[2] instanceof Float);
System.out.println(arr[2] instanceof Double);

/*输出：

true
true
false  //说明这里的浮点数并不是float类型
true

*/

看了上面的代码，聪明的你是不是已经发现端倪了呢？还是说你要暴跳而起地指正我：你不能这么用instanceof你之前地教程里还信誓旦旦地开了个小标题，专门强调不能这么用嘞，在这里你自己怎么还往坑里跳！嘿嘿~这么想地同学一定不少吧，没错，同学们说的对instanceof不可以用于基本数据类型的判定，但是原因咱也得说明：那是因为instanceof只能判断对象实例所在的类是否与你提供的类(或子类)一致，而_基本数据类型它并不是对象实例_，自然没法用instanceof来进行判断喽。

那这个例子中为啥能这么用，而且用起来看着也很有道理啊？

这是因为我们创建的数组是一个Object类型的数组，顾名思义，这个数组中的所有元素都是对象，我们给arr[0]、arr[1]、arr[2]分别赋值了不同类型的元素，但这些元素并不是以基本类型的形式存在的，而是自动装箱成它们的包装类String、Integer和Double。所以在这时再使用instanceof时判断的就是对应对象类型的它们了。

Object数组

下面我将补充完备了对象数组介绍。

在 Java 中，Object[] 是一个对象数组，它可以存储任何类型的对象。由于 Object 类是 Java 中所有类的根类，因此 Object[] 数组可以引用任何类型的对象。

创建语法

Object[] 数组的创建语法如下：

Object[] objArray = new Object[arraySize];

其中 arraySize 是数组的大小，即它可以存储的对象数量。

特点:

  • 动态分配: Java 中的所有数组都是动态分配的。
  • 连续内存: 数组可能存储在连续的内存位置。
  • 长度属性: 由于数组是对象，我们可以使用 length 属性来获取数组的长度。
  • 随机访问: 存储数组的方式支持随机访问元素。

初始化

数组声明后，需要使用 new 关键字来分配内存，并初始化数组中的每个元素。例如：

Object[] objArray = new Object[3];
objArray[0] = new String("Hello, World");
objArray[1] = new Integer(147456);
objArray[2] = new Double(3.14159265758);

在上面的例子中，我们创建了一个大小为 3 的 Object[] 数组，并分别用 String、Integer 和 Double 对象初始化了它。

注意事项

  1. 数组中存储的是对象的引用，而不是对象本身。
  2. 对于基本数据类型，如 int、double 等，它们会被自动装箱为它们对应的包装类，如 Integer、Double 等，然后存储在 Object[] 数组中。
  3. 可以使用 instanceof 关键字来检查数组中的元素是否属于特定的类型。

经过系统的介绍，相比大家对于Object数组的使用有了更深刻的理解，大家也可以回去再看一看之前的例子，回顾一下是否觉得醍醐灌顶呢？

线性列表（ArrayList）

好了，终于补充完了对象数组的相关内容，可以开始介绍更常在List接口实现中会使用的类型——ArrayList了。

ArrayList 属于 Java 集合框架（Java Collections Framework）。在Java中，ArrayList 是一个可调整大小的数组，它是 java.util 包中的一部分。与内置数组不同，ArrayList 的大小可以动态修改，这意味着我们可以随时向 ArrayList 添加或删除元素。

Java 集合框架（Java Collections Framework，JCF）是一组类和接口的集合，它提供了在 Java 程序中表示和操作集合的标准方法。集合框架的设计目的是为了提高开发效率，统一编程模型，并提供高性能的数据结构和算法。

集合框架的核心组成:

  • 集合接口 (Collection interfaces): 定义了不同类型的集合，如列表（List）、集合（Set）和映射（Map）等。
  • 通用实现 (General-purpose implementations): 提供了集合接口的主要实现，例如 ArrayList、LinkedList、HashSet 和 HashMap。
  • 遗留实现 (Legacy implementations): 早期版本的集合类，如 Vector 和 Hashtable，已经被更新以实现新的集合接口。
  • 特殊用途实现 (Special-purpose implementations): 为特定情况设计的实现，可能具有非标准的性能特征、使用限制或行为。
  • 并发实现 (Concurrent implementations): 为高并发使用而设计的实现。
  • 包装实现 (Wrapper implementations): 为其他实现添加功能，如同步。
  • 便利实现 (Convenience implementations): 高性能的小型集合接口实现。
  • 抽象实现 (Abstract implementations): 提供部分实现的集合接口，以便于自定义实现。
  • 算法 (Algorithms): 对集合执行有用功能的静态方法，如对列表进行排序。
  • 基础设施 (Infrastructure): 为集合接口提供必要支持的接口。
  • 数组工具 (Array Utilities): 为原始类型和引用对象数组提供的实用功能。

集合接口的分类:

  • **Collection**: 是最基本的集合接口，它有几个子接口，如 Set、List、Queue 和 Deque。
  • **Map**: 不是 Collection 的子接口，但也是集合框架的一部分，它表示键值对的映射。

集合框架不仅提高了程序的性能，还通过提供互操作性、减少设计和学习新 API 的努力，以及促进软件重用，使得 Java 编程更加高效和简洁。

好了，我们继续来完成那个问题——怎么在一个数组中添加类型不同的元素嘞？前文中，我们通过对象数组实现了这个功能，接下来，我将介绍通过ArrayList来实现这个功能_(关于通过使用*_**LinkedList**_*类来实现，将在链表章节中详细介绍)_

顺序表的构建

不指定泛型式

通过使用不指定泛型式构建的顺序表，可以解决在一个数组中存储多种类型元素的需求。

例子：

// Java 不指定范式构造顺序表
import java.util.ArrayList;

ArrayList objectName = new ArrayList();

如此，我们就构造了一个不指定范式的ArrayList实例——objectName。我们可以对它进行一些线性表操作，如增、删、查。

 objectName.add("SecoopraX");
 objectName.add(147456);
 objectName.add(3.1415926);
 objectName.add(true);
 objectName.add(new Object());
 
 //add()方法暂时不明白也没有关系后面有详细介绍
 //现在你只需要知道我们完成了把不同数据添加进顺序表的操作即可

以上，我们向objectName顺序表中添加了所有类型的数据各一个。接下来让我们进行顺序表的遍历，完成存储检验吧。

Iterator it = objectName.iterator();
while(it.hasNext())
{
	Object temp = it.next();
	System.out.println(temp); //输出顺序表中的每一个元素，以完成检验
}

很显然的，ArrayList类支持迭代器Iterator完成遍历迭代，输出结果为：

/*
SecoopraX
147456
3.1415926
true
java.lang.Object@6d06d69c
*/

在以上输出中，我们很直观的看到，在objectName顺序表中实现了在一个数组中存储不同类型的需求。

需要特殊声明的是：

我们并不常进行这种操作！！！

原因如下：

  • 类型安全性：使用Object作为类型会失去类型安全性，这意味着在编译时无法检查是否将错误类型的对象放入列表。

  • 类型转换：需要在检索元素时进行显式的类型转换，这增加了运行时错误的风险。

ArrayList list = new ArrayList();
list.add(10); // 自动装箱为Integer

// 如果直接使用，需要类型转换
int num = (Integer) list.get(0);


/*
如果不进行类型转换，尝试将Object直接当作int使用，
就会出现编译错误，因为Java编译器需要知道对象的确切类型才能正确地处理它。
*/

  • 代码可读性：使用Object存储多种类型的数据会降低代码的可读性和可维护性。

  • 性能问题：频繁的类型转换可能会影响程序的性能。

因此，更好的做法是使用泛型来确保类型安全，或者创建自定义类来封装复杂的数据结构。这样可以提高代码的可读性、可维护性和性能，同时减少运行时错误的可能性。

指定泛型式

接下来我们将介绍ArrayList类在构建List时更为常使用的指定泛型式构造。

例子：

// Java @SecopraX

import java.util.ArrayList; //引入顺序表的包
ArrayList<String> linearlist1 = new ArrayList<>();

// 也可以把ArrayList当作List的一种实现方式
List<String> linearlist2 = new ArrayList<>();

// ArrayList类也支持使用Array.asList()方法来完成便捷的链表创建和初始化
ArrayList<String> linearlist3 =  new ArrayList<>(Arrays.asList("Hello", ", ", "world!"));

//还可以通过使用List.of()方法实现,(只有Java9+版本支持)
import java.util.List;
ArrayList = linearlist4 = new ArrayList<>(List.of(""Hello", ", ", "world!");

顺序表的基本属性

  • capacity：ArrayList 的容量，即用于存储列表元素的数组的大小。

顺序表的基本操作（基本方法）

添加元素

  • add() 方法:添加元素到列表末尾；在指定位置添加元素。
ArrayList<String> list = new ArrayList<>();
list.add("Java"); // 在列表末尾添加元素
list.add("Python");
list.add(0, "C++"); // 在指定索引处添加元素
  • addAll(Collection<? extends E> c)方法：添加一个集合中的所有元素到列表。
ArrayList<String> list1 = new ArrayList<>();
list1.add("A");
list1.add("B");

ArrayList<String> list2 = new ArrayList<>();
list2.add("C");
list2.add("D");

// 将list2中的所有元素添加到list1的末尾
list1.addAll(list2); //不指定插入位置，则默认末尾插入
// // //
// // //
ArrayList<String> list3 = new ArrayList<>();
list3.add("1");
list3.add("2");

ArrayList<String> list4 = new ArrayList<>();
list4.add("3");
list4.add("4");

// 在索引1的位置将list4中的所有元素插入到list3中
list3.addAll(1, list4); //指定插入位置在索引为1处插入list4

访问元素

  • get(int index) 方法：获取指定位置的元素。
String element = list.get(0); // 获取索引0处的元素
System.out.println(element); // 输出 C++

修改元素

  • set(int index, E e) 方法：替换指定位置的元素。
list.set(0, "C#"); // 修改索引0处的元素

删除元素

  • remove() 方法：移除某个元素；或移除指定位置的元素
list.remove("Python"); // 删除指定元素
list.remove(0); // 删除索引0处的元素

检查元素是否存在

  • contains() 方法：判断列表是否包含某个元素并返回布尔值。
boolean exists = list.contains("Java"); // 检查"Java"是否在列表中
System.out.println(exists); // 输出 true 或 false
  • indexOf() 方法：用于返回列表中指定元素首次出现的索引位置。如果列表中不包含该元素，则返回 -1。
//Java @SecoopraX
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Date");

// 使用indexOf()方法查找元素的索引
int index = list.indexOf("Cherry");

// 输出结果
if (index != -1) {
     System.out.println("元素 'Cherry' 在列表中的索引位置是: " + index);
} else {
     System.out.println("元素 'Cherry' 不在列表中。");
}

获取列表大小

  • size() 方法：获取列表的元素个数。
int size = list.size(); // 获取列表的大小
System.out.println(size); // 输出列表的元素数量

清空列表

  • clear() 方法：
list.clear(); // 移除列表中的所有元素

遍历列表

  • 使用 for 循环：
for (String str : list) {
    System.out.println(str); // 输出列表中的每个元素
}
  • 使用迭代器遍历：

1. iterator()：返回一个迭代器，用于遍历列表。

提供方法：

  • 提供remove()方法来删除元素。
///结点操作
  • hasNext()：返回布尔值，判断是否还有下一项。
  • next()：将迭代器光标移动到下一项，并返回列表中下一个元素
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

2.listIterator()：返回一个列表迭代器，用于遍历列表。

listIterator()方法有两种形式：

  1. listIterator()：不带参数，返回列表的列表迭代器。
  2. listIterator(int index)：带有一个整型参数index，返回从列表中指定位置开始的列表迭代器。如果调用next()，返回的将是index位置的元素；如果调用previous()，返回的将是index-1位置的元素。

提供方法：

  • 提供add()和set()方法来添加和替换元素。
  • 提供remove()方法来删除元素。
///结点操作
  • hasNext()：如果列表迭代器在向前遍历列表时具有更多元素，则返回 true。
  • hasPrevious()：如果列表迭代器在反向遍历列表时具有更多元素，则返回 true。
  • next()：返回列表中的下一个元素并前后光标位置。
  • nextIndex()：返回后续调用 next() 将返回的元素的索引。
  • previous()：返回列表中的上一个元素并向前移动光标位置。
ListIterator<String> listit = list.listIterator();
while(listit.hasNext())
{
	String temp = listit.next();
	System.out.println(temp); //最简单的遍历列表
}
//由于ListIterator类的特性，我们还可以完成逆向遍历的操作

注意：在迭代器创建后，一旦对原数组、列表等集合进行修改，Java将会抛出**ConcurrentModificationException**。正确的方式为，对创建的迭代器本身进行修改。而且_**ListIterator**_提供的_**add()**_和_**remove()**_方法允许您直接修改原始的_**ArrayList**_。当您通过_**ListIterator**_添加或删除元素时，这些改动会反映在原始的_**ArrayList**_上。

特殊的：与ArrayList类自带的**add()**方法不同，使用迭代器对原列表进行删改时是在表头处进行的。**ArrayList**类的方法是在表尾进行修改。

（~心好累，好多好麻烦~~不过还是学到了不少的对吧😎）

列表排序
  • 使用sort()方法：

在Java中，ArrayList的sort()方法用于根据指定的比较器对列表中的元素进行排序。这个方法需要一个实现了Comparator接口的比较器对象作为参数。如果没有提供比较器，它将使用元素的自然顺序进行排序。

在Java中，Comparator接口是用于定义对象排序的比较函数的。它位于java.util包中，允许我们对那些没有自然顺序的对象集合进行排序，或者需要按照特定的顺序进行排序的对象集合。

Comparator接口定义了以下几个方法：(Java8后进行了加强)

  1. int compare(T o1, T o2)：比较用来排序的两个对象。如果o1小于、等于或大于o2，则分别返回负整数、零或正整数。

  2. boolean equals(Object obj)：判断某个对象是否与比较器相等。

  3. reverseOrder():是Java中用于比较对象的接口，可以用于对集合中的元素进行排序。reverseOrder是Comparator接口的一个静态方法，用于返回一个逆序排序的比较器。

  4. naturalOrder()：是Comparator接口的一个静态方法，用于返回自然顺序排序比较器。

  5. comparing(``Function<? super T,? extends U> keyExtractor):是Comparator接口的一个静态方法，将keyExtractor列表按其方法Function返回值顺序排序，返回该比较器。

通常，compare()方法是唯一需要实现的方法，因为equals()方法已经在Object类中有实现。

使用Comparator可以非常灵活地控制排序的逻辑。例如，如果你有一个Student类，你可以根据学生的年龄、姓名或其他属性来排序。你可以创建多个不同的Comparator类，每个类按照不同的属性来排序。

一些示例：

按自然顺序排序：
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(13);
numbers.add(7);
numbers.add(2);
numbers.add(21);

// 使用自然顺序排序
numbers.sort(Comparator.naturalOrder());
按逆序排序：
ArrayList<String> languages = new ArrayList<>();
languages.add("Java");
languages.add("Python");
languages.add("C++");

// 使用逆序排序
languages.sort(Comparator.reverseOrder());
使用自定义比较器排序：
ArrayList<Student> students = new ArrayList<>();

// 假设Student类有一个getAge方法
students.sort(Comparator.comparing(Student::getAge));

在第一个示例中，整数列表将按升序排序。在第二个示例中，字符串列表将按字母降序排序。第三个示例中，如果Student类有一个getAge方法，学生列表将按年龄排序。

请注意，**sort()**方法会修改原始的**ArrayList**，排序后的结果将直接反映在原列表中

这些是ArrayList中一些最常用的基本操作。通过这些操作，您可以管理列表中的元素，包括添加、删除、修改、查询和排序。

其它一些方法：
  • isEmpty()：如果列表不包含元素，则返回true。
  • toArray()：返回一个包含列表中所有元素的数组。

链表(LinkedList)

链表的介绍

链表的构成

链表由一串相连的结点构成，结点中储存着我们的数据和结点的链接指向等信息。每个结点都是一个单独的存储单元，它是链表的基本组成单位。

有几个特殊的结点需要强调：

  • 头结点(Head)：链表的第一个结点处称之为头结点，头结点中不存储数据，只存储指向第一个数据结点的引用，作为这个链表的标记赋值给一个变量。这样我们就可以通过操作这个变量来操作链表了。
  • 尾结点(Tail)：链表的最后一个结点，与头结点不同，它是存储有数据的，特殊的点在于它的引用指向为空(null)。

链表的分类

链表有多种存在形式，这可能导致它们的头结点和尾结点有所不同，但是同样的它们的基本组成仍然是结点。

  • 单向链表：最基本的链表形式，符合上面介绍的头结点和尾结点的形式。它的结点中引用往往指向它的下一项（尾结点除外）
  • 双向链表：与单向链表不同，它的每一个结点有两个引用，分别指向它的前一项和后一项。这使得它可以在任意位置很简单的访问它的前一项，不用遍历一个周期。提高了运行效率。
  • 循环链表：它与单向链表不同的是，它的尾结点指向它的头结点，使得它可以从任意位置访问该链表内的所有元素。

链表的优缺点

  • 优点：

1. 内存占用并不严格，不需要连续内存地址；

2.插入和删除元素效率高，迭代器性能好。

  • 缺点：随即访问较慢。

所以很明确的当我们需要经常删改列表数据，但不常进行任意访问时，使用链表是明智的。

LinkedList类的介绍

Java中的LinkedList类是集合框架的一部分，它提供了双向链表的实现，这意味着每个元素都有指向前一个和后一个元素的引用。

LinkedList类继承自AbstractSequentialList类，并实现了List和Deque接口。说明，我们可以通过LinkedList类实现列表和栈、队列。

在Java中，LinkedList类是一个双向链表的实现，它提供了链表数据结构的功能。LinkedList类实现了以下接口：

  • List接口：允许LinkedList作为一个列表使用，提供了标准的列表操作，如添加、删除和访问元素。
  • Deque接口：使得LinkedList可以作为一个双端队列使用，提供了在头部和尾部添加或删除元素的方法。
  • Queue接口：允许LinkedList作为队列使用，提供了标准的队列操作，如插入、检索和删除元素。

LinkedList中的每个元素都称为节点，包含三个字段：前一个元素的地址（Prev）、下一个元素的地址（Next）和实际数据（Data）。由于元素是通过链接（Prev和Next）连接的，所以LinkedList在任意位置插入或删除元素时效率较高。

在本章接下来的内容将着重介绍LinkedList在实现List接口的操作，其余接口的实现将在其他章节展开说明。

链表的构造

不指定泛型式

我们也可以和顺序表中ArrayList一样，通过不指定泛型来完成在一个表中储存多种类型元素的操作。但需要注意的是，这样方法构造的LInkedList链表中，所有的元素均被视为Object类型，在内存中存储的是引用。

不指定泛型式构造示例：

// Java @SecoopraX
List list = new LinkedList();
list.add("字符串");
list.add(123); // 自动装箱为Integer
list.add(45.67); // 自动装箱为Double
list.add(true); // 自动装箱为Boolean
list.add(new Object());  //返回哈希值
		
Iterator it = list.iterator();
while(it.hasNext())
{
	Object temp = it.next();
	System.out.println(temp);
}

/*输出：
字符串
123
45.67
true
java.lang.Object@6d06d69c
*/

在这个例子中，我们创建了一个未指定类型的LinkedList，并添加了不同类型的元素。由于没有指定泛型，这些元素都被视为Object类型。一般情况下需要多种类型列表的情况，我们使用对象数组完成，当对象数组无法满足时才考虑其他方式实现。

  • 注意：

在Java中，虽然我们可以使用LinkedList或ArrayList来存储不同类型的元素，但这种做法并不常见，原因主要有以下几点：

类型安全：不指定集合的泛型类型会失去类型检查的好处。这意味着在编译时期无法检测到类型错误，可能会导致运行时错误。

代码可读性：使用泛型可以使代码更加清晰和易于理解。其他开发者可以轻松地知道集合中应该存储什么类型的元素。

性能：不必要的类型转换会影响性能。如果集合中存储了不同类型的元素，每次检索时都需要进行类型转换。

维护和扩展：随着项目的发展，如果集合中存储了不同类型的元素，后期维护和扩展会变得更加困难。

因此，通常建议使用泛型来指定集合中元素的类型，这样可以提高程序的类型安全性、可读性和性能。当然，如果您有特殊的需求，需要在一个集合中存放多种类型的元素，这种做法也是可以接受的，只是需要更加小心地处理元素的类型。

故我们更常使用下面指定泛型式来进行LinkedList类型的构造。

指定泛型式（常用）

链表在Java中有现成的封装好的类——LinkedList

与顺序表ArrayList类似的：

// Java @SecopraX

import java.util.LinkedList; //引入链表的包
LinkedList<String> linklist_S = new LinkedList<>();

// 也可以把LinkedList当作List的一种实现方式
List<String> list_linked_S = new LinkedList<>();

// LinkedList类也支持使用Array.asList()方法来完成便捷的链表创建和初始化
LinkedList<String> linklist_S1 =  new LinkedList<>(Arrays.asList("Hello", ", ", "world!"));

//还可以通过使用List.of()方法实现,(只有Java9+版本支持)
import java.util.List;
LinkedList = linklist_S2 = new LinkedList<>(List.of(""Hello", ", ", "world!");

以上，我们就构建了一个名为linklist_S的链表，这个链表可以存储的元素类型为String。同时我们通过new完成了对LinkedList的初始化、创造了一个LinkedList实例。

我们还可以使用现有的集合对LinkedList进行构造：

// Java  @SecoopraX

List<String> list_S = new ArrayList<>();
list_S.add("Hello, ");
list_S.add("world!");

List<String> linkedlist_S = new LinkedList<>(list_S);
System.out.println(linkedlist_S.get(0)+linkedlist_S.get(1));
//输出：
//Hello, world!

链表的基本操作

LinkedList 提供了丰富的方法来操作列表数据，使其成为实现栈、队列或双端队列的理想选择。我们接下来将对它所提供的所有方法进行介绍，可能有部分方法并不会在链表中使用。但在接下来关于队列和栈的操作中可能涉及。

**LinkedList** 类中一些常用方法：

添加元素:

  • add(E e): 在列表末尾添加一个元素。
LinkedList<String> list = new LinkedList<>();
list.add("元素1");
  • add(int index, E element): 在列表的指定位置插入一个元素。(插入并不是替换，并不改变原来索引处的数据，原来索引处的数据被移后了一位) 
list.add(1, "元素2");
  • addFirst(E e): 在列表开头添加一个元素。
list.addFirst("首部元素");
  • addLast(E e): 在列表末尾添加一个元素。
list.addLast("尾部元素");

访问元素:

  • get(int index): 返回列表中指定位置的元素。
String element = list.get(1); //返回 "元素2"
  • getFirst(): 返回列表中的第一个元素。
String firstElement = list.getFirst(); // 返回 "首部元素"
  • getLast(): 返回列表中的最后一个元素。
String lastElement = list.getLast(); // 返回 "尾部元素"

删除元素:

  • remove(): 删除并返回列表的第一个元素。默认从头部开始删除。
String removedElement = list.remove(); // 删除并返回 "首部元素"
  • remove(int index): 删除指定位置的元素。
list.remove(1); // 删除 "元素2"（此时“首部元素”已被删除）
  • removeFirst(): 删除并返回列表的第一个元素。
list.removeFirst();  //删除并返回 "首部元素"
  • removeLast(): 删除并返回列表的最后一个元素。
list.removeLast(); // 删除并返回 "尾部元素"

元素替换

  • set(int index，E e):该方法可将索引处的元素数据进行替换（替换数据为所给出的参数）
list.set(1, "元素替换"); // 将索引 1 处的元素替换为 "元素替换"

队列操作:（不一定用得上）

  • offer(E e): 在列表末尾添加一个元素（如果有空间）。
list.offer("新元素");
  • poll(): 删除并返回列表的第一个元素。
String polledElement = list.poll(); // 删除并返回 "首部元素"
  • peek(): 返回列表的第一个元素，但不删除。
String peekedElement = list.peek(); // 返回 "首部元素"

栈操作:

  • push(E e): 将一个元素推入栈顶（列表开头）。
list.push("栈顶元素");
  • pop(): 移除并返回栈顶元素（列表开头的元素）。
String poppedElement = list.pop(); // 删除并返回 "栈顶元素"

其他方法:

  • clear(): 清空列表。
  • contains(Object o): 检查列表是否包含指定的元素。
boolean contains = list.contains("元素1"); // 检查是否包含 "元素1"
  • size(): 返回列表中的元素数量。
  • toArray(): 将列表转换为数组。
Object[] array = list.toArray(); // 将 LinkedList 转换为数组
//由于列表中元素类型可能并不单一所以我们使用了对象数组

遍历迭代

在 Java 中，遍历 LinkedList 的常用方法有以下几种：

1. 使用 for-each 循环:

LinkedList<String> list = new LinkedList<>();
list.add("元素1");
list.add("元素2");
list.add("元素3");

for(String item : list) {
    System.out.println(item);
}

这种方法简单直观，适用于不需要修改列表时的遍历。

2. 使用迭代器 (Iterator) 推荐:

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);
}

迭代器提供了一种安全的方式来遍历列表，同时可以在遍历过程中修改列表。(具体介绍在基础语法章节中有更为详细的介绍）

3. 使用 ListIterator:

ListIterator<String> listIterator = list.listIterator();
while(listIterator.hasNext()) {
    String item = listIterator.next();
    System.out.println(item);
}

ListIterator 允许您在列表中向前或向后遍历，并且可以在遍历过程中添加、替换或删除元素。支持逆序遍历链表。

ListIterator 是 Java 中的一个接口，它扩展了 Iterator 接口的功能，允许我们在列表中双向遍历（前进和后退）。这是 List 接口特有的迭代器，提供了在列表的迭代期间修改列表并获取迭代器在列表中的当前位置的能力。以下是 ListIterator 的一些主要方法：

  • add(E e)：将指定的元素插入列表（可选操作）。
  • hasNext()：如果列表迭代器在向前遍历列表时具有更多元素，则返回 true。
  • hasPrevious()：如果列表迭代器在反向遍历列表时具有更多元素，则返回 true。
  • next()：返回列表中的下一个元素并前后光标位置。
  • nextIndex()：返回后续调用 next() 将返回的元素的索引。
  • previous()：返回列表中的上一个元素并向前移动光标位置。
  • previousIndex()：返回后续调用 previous() 将返回的元素的索引。
  • remove()：从列表中删除 next() 或 previous() 返回的最后一个元素（可选操作）。
  • set(E e)：用指定的元素替换 next() 或 previous() 返回的最后一个元素（可选操作）。

ListIterator 还有其他方法，但这些是最常用的。使用 ListIterator 可以在遍历列表时更灵活地操作元素，例如在遍历过程中插入或删除元素。

注意：在迭代器(**Iterator**/**ListIterator**)创建后，一旦对原数组、列表等集合进行修改，Java将会抛出**ConcurrentModificationException**。正确的方式为，对创建的迭代器本身进行修改。而且_**ListIterator**_提供的_**add()**_和_**remove()**_方法允许您直接修改原始的_**ArrayList**_。当您通过_**ListIterator**_添加或删除元素时，这些改动会反映在原始的_**ArrayList**_上。

特殊的：与ArrayList类自带的**add()**方法不同，使用迭代器对原列表进行删改时是在表头处进行的。**ArrayList**类的方法是在表尾尽心修改的。

4. 使用传统的 for 循环:

for(int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

这种方法可以通过索引访问元素，但对于 LinkedList 来说效率较低，因为它每次 get(i) 都需要从头开始遍历到第 i 个元素。

5. 使用 forEach() 方法:

list.forEach((item) -> {
    System.out.println(item);
});

这是 Java 8 引入的方法，可以更方便地进行遍历操作。

每种方法都有其适用场景，我们需要根据实际情况选择最合适的一种。

用LinkedList实现链表

双向链表

Java中LinkedList本身就是一种双向链表的实现形式，它支持指向前一个结点和后一个结点的两个引用形式。

特殊的迭代方式——逆序遍历

由于LinkedList类型是天然的双向链表，自然的它支持通过逆序方式进行元素内容的遍历。我们可以从链表的尾结点开始，按位向前遍历整个链表：

// Java @SecoopraX
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Arrays;

//创建链表
LinkedList<String> linklist_S = new LinkedList<>(Arrays.asList("Hello", ", ", "world!"));
//使用Arrays.asList()方法完成便捷的链表构建和初始化

//构建迭代器
ListIterator<String> it = linklist_S.listIterator(linkedlist_S.size());
//构建了一个双向链表迭代器，这个迭代器指向的引用为linklist_S链表最后一位（尾结点）

while(it.hasPrevious())  
{
	String item = it.previous(); //逆序遍历，previous()方法可以返回前一项，并同时向前移动引用
	System.out.print(item);
}

同理，我们也可以借助双向链表迭代器ListIterator完成元素的插入和删除（遍历操作罢了）

写在最后：

线性表章节这就算是正式完结了，我花费了大量时间整理和完善整体的知识框架，尽可能地让知识无盲点地展现在大家面前。虽然，我很清楚，所谓新手我仍存在许多的不足（比如，行文枯燥、活力和趣味性不佳，大家应该读起来也很痛苦吧——都是字，没图片，真难看！；而且就知识叙述来讲有些地方确实存在一定地缺陷，这是我个人表述的不足，还有就是对于某些知识点并不熟练导致的）

所以，包容以上的种种问题仍然读到这里的朋友们，我真心非常感谢你们。哦，对了，还得恭喜下屏幕前的你，我有自信的说，这篇文章是你在国内能找到的最完善的线性表教程了，能通读下来（最好多读几遍，有地方我讲的可能真不清楚，实在看不明白的私信我也好，我会尽力解释的）肯定能有所收获。对于掌握一定Java基础谋求进阶的朋友一定能有所帮助。

最后的最后，都读到这里了，点点赞、点点关注吧，也算对我这个新人的鼓励了。要是有大佬看到，文章中有什么问题也请不吝赐教，在评论区评论出我的错误（私信也行啊）

在此，感谢！

2024年4月9日
相关内容
亚德客看好电子车用气动元件 下半年线性滑轨出货佳
数据结构复习指导之线性表的链式表示（单链表的定义以及操作实现）