当前位置：首页 > news >正文

LinkedList数据结构链表

news 2025/7/10 3:13:17

LinkedList在Java中是一个实现了List和Deque接口的双向链表。它允许我们在列表的两端添加或删除元素，同时也支持在列表中间插入或移除元素。在分析LinkedList之前，需要理解链表这种数据结构：

链表：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据部分和指向列表中下一个节点的引用。
双向链表：每个节点都有两个链接，一个指向前一个节点，另一个指向后一个节点。

`LinkedList` 的数据结构

在LinkedList中，每个元素都是一个节点，每个节点包含三个部分：存储的数据项、指向前一个节点的引用和指向后一个节点的引用。

private static class Node<E> {E item; // 存储的数据Node<E> next; // 指向后一个节点的引用Node<E> prev; // 指向前一个节点的引用Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}

`LinkedList` 的核心方法

LinkedList实现了List接口，所以它具有诸如add, remove, get, set等方法，同时也实现了Deque接口，这意味着它也具有offer, poll, push, pop等方法。

源码解析（简化版）

以下是LinkedList中一些关键方法的简化版源码：

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {transient int size = 0;transient Node<E> first;transient Node<E> last;public LinkedList() {}public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}public E remove() {return unlinkFirst(first);}private E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; first = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}public E get(int index) {checkElementIndex(index);return node(index).item;}Node<E> node(int index) {if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}// 省略其他细节实现
}

代码演示

下面是LinkedList的一个简单使用示例：

import java.util.LinkedList;public class Main {public static void main(String[] args) {LinkedList<String> friends = new LinkedList<>();// 添加元素friends.add("Alice");friends.add("Bob");friends.add("Charlie");// 打印所有元素System.out.println("Initial LinkedList: " + friends);// 删除第一个元素friends.remove();// 打印删除元素后的列表System.out.println("After removal: " + friends);// 获取特定位置的元素String friend = friends.get(1);System.out.println("Second friend: " + friend);}
}