Java中的LinkedList：为什么它是数据结构中的万能选择？

末蓝、 2023-10-15 21:17 50阅读 0赞

## 前言 ##

在Java中，有很多数据结构可供选择，如ArrayList、LinkedList、Stack、Queue等等。其中，LinkedList是被广泛使用的一种数据结构。在本篇文章中，我们将探讨LinkedList在Java中的广泛应用，并解释为什么它是数据结构中的万能选择。

## 摘要 ##

LinkedList是一种非常常见的数据结构，它在Java编程中有着广泛的应用。它由一系列的节点组成，每个节点包含一个指向前一个节点的引用和一个指向后一个节点的引用。LinkedList具有许多优点，如高效的插入和删除操作、动态内存分配等等。这篇文章将介绍LinkedList的优点、源代码、方法介绍、测试用例和全文小结。

## 内容 ##

### 什么是LinkedList？ ###

LinkedList是Java中的一个类，它实现了List接口，是一个双向链表。对于双向链表，每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。这使得在LinkedList中，可以在任意位置插入和删除元素，而不需要像数组一样重新分配内存。

### 为什么选择LinkedList？ ###

LinkedList提供了许多优点，使得它成为许多程序员的选择：

1.  插入和删除操作效率高。

LinkedList对于插入和删除操作有着非常高的效率，因为它不需要像ArrayList一样移动元素。相反，它只需要在链表中修改指针即可。

1.  可以动态地分配内存。

LinkedList是一个动态的数据结构，可以在运行时动态地创建节点。因此，它可以使用更有效的内存管理，减少内存浪费。

1.  随机访问操作没有ArrayList高效。

ArrayList可以通过索引来随机访问元素，而LinkedList需要从第一个节点开始遍历链表才能找到所需的节点。当然，如果您只需要顺序访问节点，那么LinkedList会比ArrayList更有效。

### 源码分析 ###

LinkedList是Java中的一个双向链表实现的集合类，包路径位置为：java.util.LinkedList 。下面是对其源码中的几个重要成员变量进行介绍：

1.  transient int size = 0;
    
    size是记录LinkedList当前的元素数量的变量。它被标记为transient（翻译为短暂的、临时的），表示当对象进行序列化时，这个变量的值不会被持久化。
2.  transient Node<E> first;
    
    first是指向LinkedList第一个元素的节点的引用。同样地，它也被标记为transient，表示当对象进行序列化时，这个引用不会被持久化。
3.  transient Node<E> last;
    
    last是指向LinkedList最后一个元素的节点的引用。同样地，它也被标记为transient，表示当对象进行序列化时，这个引用不会被持久化。

通过这三个变量，LinkedList可以方便地操作链表的头部、尾部和元素数量。在对链表进行插入、删除等操作时，这三个变量会被相应地更新以保证链表的正确性。

![13d0dd1d6c9c411bd60ddc7706a85144.jpeg][]

### LinkedList方法介绍 ###

LinkedList类提供了许多有用的方法，可以用于添加、删除、获取和搜索元素。以下是一些常用方法：

1.  add(E e)：将指定的元素添加到列表的末尾。
2.  add(int index, E element)：将指定的元素插入到列表的指定位置。
3.  addFirst(E e)：在列表开头添加元素。
4.  addLast(E e)：在列表末尾添加元素。
5.  remove(Object o)：删除指定元素的第一个出现。
6.  remove(int index)：删除指定位置的元素。
7.  removeFirst()：从列表开头删除元素，并返回删除的元素。如果列表为空，则抛出NoSuchElementException异常。
8.  get(int index)：返回指定位置的元素。
9.  getFirst()：获取列表中的第一个元素，如果列表为空，则抛出NoSuchElementException异常。
10. getLast()：获取列表中的最后一个元素，如果列表为空，则抛出NoSuchElementException异常。
11. size()：返回列表中的元素数。
12. contains(Object o)：如果列表包含指定的元素，则返回true。
13. indexOf(Object o)：返回指定元素第一次出现的位置。

### 测试用例 ###

下面是一些简单的JUnit测试用例，用于测试LinkedList的add()和remove()方法：

#### 测试add()方法 ####

java复制代码 //新增元素 @Test public void testAdd() { // 创建一个LinkedList对象 LinkedList<String> list = new LinkedList<>(); // 添加元素到列表 list.add("Java"); list.add("Python"); list.add("C++"); System.out.println("list = " + list); assertEquals(3, list.size()); }

测试用例执行截图如下：

![5d7b8ae8ef24e4e39ad592a12f01dd23.jpeg][]

#### 测试remove()方法 ####

java复制代码 //remove()方法 @Test public void testRemove() { // 创建一个LinkedList对象 LinkedList<String> list = new LinkedList<>(); // 添加元素到列表 list.add("Java"); list.add("Python"); list.add("C++"); System.out.println("移除前list = " + list); String removed = list.remove(1); System.out.println("移除后list = " + list); assertEquals("Python", removed); }

测试用例执行截图如下：

![9095bf3200c7a465c853bff7546d62bd.jpeg][]

### 全文小结 ###

在Java编程中，LinkedList是一种非常常见的数据结构。它由一系列的节点组成，每个节点包含一个指向前一个节点的引用和一个指向后一个节点的引用。LinkedList特别适用于插入和删除元素的情况，因为它不需要像ArrayList一样移动元素。此外，LinkedList可以动态地分配内存，减少内存浪费。然而，如果您需要随机访问元素，ArrayList会比LinkedList更有效。LinkedList类提供了许多有用的方法，如add、remove、get、size、contains和indexOf。在编写Java程序时，LinkedList是一个非常有用的数据结构，可以大大提高程序的效率和性能。

[13d0dd1d6c9c411bd60ddc7706a85144.jpeg]: https://img-blog.csdnimg.cn/img_convert/13d0dd1d6c9c411bd60ddc7706a85144.jpeg
[5d7b8ae8ef24e4e39ad592a12f01dd23.jpeg]: https://img-blog.csdnimg.cn/img_convert/5d7b8ae8ef24e4e39ad592a12f01dd23.jpeg
[9095bf3200c7a465c853bff7546d62bd.jpeg]: https://img-blog.csdnimg.cn/img_convert/9095bf3200c7a465c853bff7546d62bd.jpeg