526互联

LinkedList的常用方法

发布时间 2023-12-02 09:32:18作者: べ微熏の斜陽べ

介绍

LinkedList 类是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。

Java 的 LinkedList 底层是一个双向链表，位于 java.util 包中，使用前需要引入它

LinkedList

  • LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  • LinkedList 实现 List 接口，能对它进行队列操作。
  • LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
  • LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
  • LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
  • LinkedList 是非同步的。

缺陷：
LinkedList 是链表，与ArrayList相比，LinkedList插入、删除元素操作方便，性能高。但如果访问、查找元素，是遍历链表方式的，开销大，所以应尽量减少get(int location)、indexOf(Object object)的使用。

在实际运用中ArrayList 和 LinkedList 怎么选择？
查询、访问频繁：ArrayList
插入、删除频繁：LinkedList

LinkedList使用

LinkedList 实例化方式

1、无参构造法

LinkedList <Integer> linkedList = new LinkedList <>();

2、有参数——参数是其他 Collection

Collection是集合框架中的一个接口，实现了这个接口的类的对象就可以作为参数，说白了就是
可以把其他的顺序表，链表，栈，队列等等 作为参数传参，例如：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
LinkedList<Integer> linkedList= new LinkedList<arrayList >(arrayList );

我先 new 了一个顺序表对象 arrayList ，在这个表中插入了 “1” “2” 两个数据，顺序表中的数据是顺序存储的
当 arrayList 作为参数传递时，linkedList 对象中就有了 arrayList 中的所有数据，linkedList 中的数据是链式

LinkedList 常用方法

3.1 、添加元素

3.1.1 add 方法

要向 LinkedList 中添加元素，您可以使用 add 方法。它将元素添加到列表的末尾。

linkedList.add("橙子");
3.1.2 在指定位置添加元素

您还可以使用 add 方法在指定位置插入元素。指定位置是通过索引来确定的，索引从 0 开始。

linkedList.add(1, "葡萄"); // 在索引 1 处插入 "葡萄"

3.2 、获取元素

3.2.1 get 方法

要获取 LinkedList 中的元素，可以使用 get 方法，指定元素的索引。

String fruit = linkedList.get(0); // 获取第一个元素

3.3、 删除元素

3.3.1 remove 方法

要删除 LinkedList 中的元素，可以使用 remove 方法。可以指定要删除的元素或要删除的元素的索引。

linkedList.remove("香蕉"); // 删除 "香蕉"
linkedList.remove(1); // 删除索引 1 处的元素

4、遍历 LinkedList

遍历 LinkedList 可以使用不同的方式，最常见的是使用 for-each 循环或迭代器。

4.1 使用 for-each 循环
for (String fruit : linkedList) {
    System.out.println(fruit);
}
4.2 使用迭代器
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String fruit = iterator.next();
    System.out.println(fruit);
}

5、特殊操作

5.1 在开头和末尾添加元素

LinkedList 允许在开头和末尾高效添加元素。

5.1.1 在开头添加元素
linkedList.addFirst("草莓");
5.1.2 在末尾添加元素
linkedList.addLast("樱桃");
5.2 在特定位置插入元素

LinkedList 也允许在特定位置插入元素。

linkedList.add(2, "葡萄"); // 在索引 2 处插入 "葡萄"
5.3 替换元素

您可以使用 set 方法来替换 LinkedList 中的元素。

linkedList.set(1, "蓝莓"); // 将索引 1 处的元素替换为 "蓝莓"

6、性能考虑

6.1 LinkedList与 ArrayList 的比较

在考虑使用 LinkedList 时，需要权衡性能。与 ArrayList 相比，LinkedList 在插入和删除操作方面通常更快，因为它不需要移动大量元素。然而，它在随机访问元素时的性能较差，因为需要从头部或尾部开始遍历链表。

6.2 时间复杂度
  • 添加和删除元素：平均时间复杂度为 O(1)（在已知位置的情况下），最坏情况下为 O(n)（如果需要遍历整个链表）。
  • 获取元素：平均时间复杂度为 O(n/2)（在平均情况下，需要遍历一半的链表）。
  • 随机访问元素：最坏情况下为 O(n)（需要从头或尾遍历整个链表）。

7、使用注意事项

在使用 LinkedList 时，需要注意以下事项：

  • LinkedList 不是线程安全的。如果在多个线程中使用，必须采取适当的同步措施，或者考虑使用线程安全的替代品。
  • 避免过多的随机访问，因为它的性能较差。如果需要频繁的随机访问，请考虑使用 ArrayList。
  • 谨慎使用大型 LinkedList，因为它可能会占用大量内存。

8、高级用法

8.1 双向链表

LinkedList 是一种双向链表的实现，这意味着每个节点都包含指向前一个节点和后一个节点的引用。这种双向连接使得在链表中向前和向后遍历都非常高效。以下是关于双向链表的高级用法示例：

8.1.1 逆序遍历链表

LinkedList 的双向性质使得逆序遍历变得容易。您可以从链表的尾部开始遍历，不断跟随前一个节点的引用，直到达到链表的头部。

LinkedList<String> linkedList = new LinkedList<>();
// 添加元素到链表
// ...
// 逆序遍历链表
ListIterator<String> iterator = linkedList.listIterator(linkedList.size());
while (iterator.hasPrevious()) {
    String item = iterator.previous();
    System.out.println(item);
}
8.1.2 在特定位置插入元素

双向链表的特性使得在特定位置插入元素更加高效，因为您可以从两个方向进行遍历。这可以在需要在链表中间插入元素时提供性能优势。

LinkedList<String> linkedList = new LinkedList<>();
// 添加元素到链表
// ...
// 在中间位置插入元素
ListIterator<String> iterator = linkedList.listIterator(linkedList.size() / 2); // 在中间位置开始
iterator.add("新元素");
8.2 循环链表

LinkedList 也可以用作循环链表，即链表的最后一个节点指向第一个节点，形成一个闭环。这种结构在某些算法和数据结构中非常有用，例如循环队列。

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

// 构建循环链表，将最后一个元素指向第一个元素
circularList.getLast().setNext(circularList.getFirst());

// 遍历循环链表
Node<String> currentNode = circularList.getFirst();
do {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
} while (currentNode != circularList.getFirst());

示例代码

以下是一些使用 LinkedList 的基础示例代码：

// 创建一个 LinkedList
LinkedList<String> linkedList = new LinkedList<>();

// 添加元素
linkedList.add("苹果");
linkedList.add("香蕉");

// 获取元素
String fruit = linkedList.get(0);

// 删除元素
linkedList.remove("香蕉");

// 遍历 LinkedList
for (String item : linkedList) {
    System.out.println(item);
}

总结

LinkedList 是 Java 中强大的数据结构，它在插入和删除操作方面非常高效。但是，在随机访问元素时性能较差，因此需要谨慎选择使用。希望本篇博客能够帮助您更好地理解和使用 LinkedList，并在编写 Java 代码时做出明智的选择。无论您是初学者还是有经验的开发者，掌握 LinkedList 都将为您的编程旅程增添新的工具和技巧。