Java链表 – Java中的链表

教程
Java

Java LinkedList 是 List 和 Deque 接口的一种实现。它是经常使用的 List 实现类之一。它扩展了 AbstractSequentialList 并实现了 List 和 Deque 接口。它是一个有序集合，支持重复元素。它按插入顺序存储元素。它支持添加空元素。它支持基于索引的操作。如果您想了解更多关于 List 基础知识，请阅读这篇文章：Java List。

文章简要目录

在本文中，我们将讨论以下概念。

  • Java LinkedList
  • Java LinkedList 类图
  • Java LinkedList List 方法
  • Java LinkedList Deque 方法
  • Java LinkedList 基本示例
  • Java LinkedList 泛型
  • Java 数组转 LinkedList
  • Java LinkedList 转数组
  • Java LinkedList 实时用例
  • Java LinkedList 的内部表示
  • Java LinkedList 中插入操作的工作原理？
  • Java LinkedList 中删除操作的工作原理？
  • Java LinkedList Deque 操作
  • Java SE 8：Java LinkedList 转流
  • Java SE 9 LinkedList

Java LinkedList

在这一部分，我们将讨论一些关于Java LinkedList的重要要点：

  • Java LinkedList类是Java集合框架的成员之一。
  • 它是List和Deque接口的实现。
  • 在内部，它是使用双向链表数据结构实现的。
  • 它支持重复元素。
  • 它以插入顺序存储或维护其元素。
  • 我们可以添加任意数量的空元素。
  • 它是不同步的，这意味着它不是线程安全的。
  • 我们可以使用Collections.synchronizedList()方法创建同步的LinkedList。
  • 在Java应用程序中，我们可以将其用作列表、堆栈或队列。
  • 它不实现RandomAccess接口。因此，我们只能按顺序访问元素。它不支持随机访问元素。
  • 当我们尝试从LinkedList中访问元素时，搜索该元素从LinkedList的开头或结尾开始，取决于该元素的位置。
  • 我们可以使用ListIterator迭代LinkedList元素。
  • 从Java SE 8开始，我们可以将LinkedList转换为Stream，反之亦然。
  • Java SE 9将添加一对工厂方法来创建不可变的LinkedList。

Java LinkedList 类图

众所周知，Java LinkedList 是 List 实现类之一。它还实现了 Deque。如下所示的类图中，它并没有直接继承自 AbstractList 类，而是继承自 AbstractSequentialList 类。

Java LinkedList 列表方法

在这一部分中，我们将讨论一些有用且经常使用的 Java LinkedList 方法。以下方法是从 List 或 Collection 接口继承的：

  1. int size(): 获取列表中元素的数量。
  2. boolean isEmpty(): 检查列表是否为空。
  3. boolean contains(Object o): 如果列表包含指定的元素，则返回 true。
  4. Iterator iterator(): 返回此列表中元素的迭代器，按适当的顺序。
  5. Object[] toArray(): 返回包含此列表中所有元素的数组，按适当的顺序。
  6. boolean add(E e): 将指定的元素追加到此列表的末尾。
  7. boolean remove(Object o): 从此列表中移除首次出现的指定元素。
  8. boolean retainAll(Collection c)：仅保留此列表中包含在指定集合中的元素。
  9. void clear()：从列表中移除所有元素。
  10. E get(int index): Returns the element at the specified position in the list.
  11. E set(int index, E element): Replaces the element at the specified position in the list with the specified element.
  12. ListIterator listIterator()：返回列表中元素的列表迭代器。
  13. List subList(int fromIndex, int toIndex)：返回列表中从指定的fromIndex（包括）到toIndex（不包括）之间的部分视图。返回的列表由此列表支持，因此返回列表中的非结构性更改会反映在此列表中，反之亦然。

Java LinkedList Deque 方法

以下方法专门针对继承自 Deque 接口的 LinkedList 类：

  1. void addFirst(E e)：将指定的元素插入到此列表的开头。
  2. void addLast(E e)：将指定的元素插入到此列表的末尾。
  3. E getFirst(): Retrieves, but does not remove, the first element of this list. This method differs from peekFirst only in that it throws an exception if this list is empty.
  4. E getLast(): Retrieves, but does not remove, the last element of this list. This method differs from peekLast only in that it throws an exception if this list is empty.
  5. E remvoeFirst(): Removes and returns the first element from this list.
  6. E removeLast(): Removes and returns the last element from this list.
  7. boolean offerFirst(E e)：将指定的元素插入到此列表的开头。
  8. boolean offerLast(E e)：将指定的元素插入到此列表的末尾。
  9. E pollFirst(): Retrieves and removes the first element of this list, or returns null if this list is empty.
  10. E pollLast(): Retrieves and removes the last element of this list, or returns null if this list is empty.
  11. E peekFirst(): Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
  12. E peekLast(): Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

Java LinkedList 基本示例

在这一部分，我们将讨论 Java LinkedList 的基本示例。我们将在接下来的部分中探讨一些更有用的操作。示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListDemo 
{
  public static void main(String[] args) 
  {
	List names = new LinkedList();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        names.add(2011);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

输出：

LinkedList content: [Rams, Posa, Chinni, 2011]
LinkedList size: 4

在这里，我们创建了一个 LinkedList 对象并添加了4个项。正如我们讨论过的，LinkedList.size() 方法用于获取列表中元素的数量。注意：在没有使用泛型的情况下，Java LinkedList 支持异构元素。然而，不推荐在没有泛型的情况下使用集合。让我们在接下来的部分中通过一个简单的示例探讨 Java 泛型的优势和用法。

Java LinkedList 泛型

在这一部分，我们将讨论如何在 Java LinkedList 中使用泛型。正如我们所知，Java 泛型对于编写类型安全的程序和在编译时进行更强的类型检查非常有用。它们还有助于消除类型转换的开销。示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListGenericsDemo
{
  public static void main(String[] args) 
  {
	List names = new LinkedList<>();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        // 我们不能添加除了字符串以外的其他元素
        // names.add(2011);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

输出：

LinkedList content: [Rams, Posa, Chinni]
LinkedList size: 3

在这里，我们创建了一个带有泛型的 LinkedList 对象并添加了3个项。当我们尝试为 LinkedList 添加一个数字时，它会引发编译时错误。

Java 数组转 LinkedList

在这一部分，我们将探讨如何将 Java 数组转换为 LinkedList 对象。我们可以用多种方式来实现，但我这里只给出了一种方法。 示例：


import java.util.LinkedList;
import java.util.List;

public class JavaArrayToLinkedListDemo 
{
	public static void main(String[] args) 
	{
		Integer[] numbers = {1,2,3,4,5};
		List<Integer> numbersList = new LinkedList<>();
		for(Integer s : numbers){
			numbersList.add(s);
		}
		System.out.println(numbersList);
	}
}

输出：

[1, 2, 3, 4, 5]

Java LinkedList 到 Array

在这一部分，我们将探讨如何将 Java LinkedList 转换为数组。我们可以用多种方式来实现，但我这里只给出了一种方法。 示例：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LinkedListToJavaArrayDemo 
{
	public static void main(String[] args) 
	{		
		List<Integer> numbersList = new LinkedList<>();
		numbersList.add(1);
		numbersList.add(2);
		numbersList.add(3);
		numbersList.add(4);
		numbersList.add(5);
		Integer[] numbers = new Integer[numbersList.size()];
		
		numbers = numbersList.toArray(numbers);
		System.out.println(Arrays.toString(numbers));

	}
}

输出：

[1, 2, 3, 4, 5]

Java LinkedList 实时用例

在这一部分，我们将讨论在 Java 应用程序中使用 LinkedList 的最佳和最坏情况。 最佳用例场景：

  • 当我们经常使用的操作是在列表中间添加或删除元素时，LinkedList 是最适合使用的类。

为什么？ 因为我们不需要对列表中间的元素进行更多的移动来添加或删除元素。请参考“Java LinkedList 中的插入操作是如何工作的？”部分，以详细了解。 最坏用例场景：

  • 当我们经常使用的操作是从列表中检索元素时，LinkedList是最差的选择。

为什么呢？因为LinkedList仅支持顺序访问，不支持随机访问。请参考“Java LinkedList中删除操作的工作原理”部分，以详细了解。注意：LinkedList实现了List、Deque、Cloneable和Serializable接口。但它不实现RandomAccess接口。

Java LinkedList的内部表示

正如我们所知，Java LinkedList在内部使用双向链表实现。因此，Java LinkedList将其元素表示为节点。每个节点分为以下3部分，如下所示。在这里，每个节点都用于特定的目的。

  1. 左侧节点部分用于指向LinkedList中的前一个节点（或元素）。
  2. 右侧节点部分用于指向LinkedList中的下一个节点（或元素）。
  3. 中间节点部分用于存储实际数据。

注意：在JVM中，LinkedList并不是按连续顺序存储其元素的。它会将元素存储在任何可用的空间，并且通过左侧和右侧的节点部分将它们相互连接，如下图所示。

Java LinkedList中的插入操作是如何工作的？

我们已经在前一节中看到了LinkedList如何将其元素作为节点存储。在本节中，我们将讨论Java LinkedList的插入操作是如何内部工作的。

  1. 假设我们最初的LinkedList包含以下数据。3. 对这个LinkedList执行以下插入操作
linkedList.add(2,54);

这里我们尝试执行插入操作，在索引2处添加值为“54”的新元素。5. 更新后的LinkedList如下所示。

Java LinkedList中的删除操作是如何工作的？

我们已经在前面的部分看到了LinkedList如何在内部执行插入操作。在本节中，我们将讨论Java LinkedList的删除操作在内部是如何工作的。

  1. 让我们假设我们的初始LinkedList具有以下数据。3. 执行以下插入操作在这个LinkedList上
linkedList.remove(3);

这里我们试图执行删除操作来删除索引为3.5的元素。更新后的LinkedList如下所示。

Java LinkedList Deque操作

在这里，我们将探讨LinkedList对象如何作为Deque工作。我们使用这些操作来实现队列或栈。我将在接下来的帖子中深入讨论栈或队列的工作原理。例子：-

import java.util.LinkedList;
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeOperationsDemo 
{
  public static void main(String[] args) 
  {
	Deque names = new LinkedList();
	names.add(2);
	names.addFirst(1);
	names.addLast(3);
	names.addFirst(0);
	names.addLast(4);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
	names.removeFirst();
	names.removeLast();
	
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());	
  }
}

输出：-

LinkedList content: [0, 1, 2, 3, 4]
LinkedList size: 5
LinkedList content: [1, 2, 3]
LinkedList size: 3

Java SE 8：Java LinkedList转Stream

在这里，我们将探讨如何将LinkedList对象转换为Java SE 8中的Stream概念。例子：-

import java.util.LinkedList;
import java.util.List;

public class LinkedListToStreamDemo 
{
  public static void main(String[] args) 
  {		
	List numbersList = new LinkedList<>();
	numbersList.add(1);
	numbersList.add(2);
	numbersList.add(3);
	numbersList.add(4);
	numbersList.add(5);
		
	//将List转换为流
	numbersList.stream().forEach(System.out::println);
  }
}

输出：

1
2
3
4
5

Java SE 9 LinkedList

在Java SE 9中，Oracle Corp将添加一些有用的实用方法来创建不可变列表。如果您希望通过一些有用的示例深入了解它们，请阅读我的帖子：Java SE 9：不可变列表的工厂方法这就是关于Java中LinkedList的一个快速概述。我希望这些Java LinkedList示例能帮助您开始学习LinkedList编程。感谢您阅读我的教程。如果您喜欢我的教程，或者有任何问题、建议或任何类型的错误，请给我留言。

Source:
https://www.digitalocean.com/community/tutorials/java-linkedlist-linkedlist-java