Java数据结构之LinkedList：从链表到实现的方法

引言

在Java编程中，数据结构是构建高效、可维护代码的基石之一。链表（LinkedList）作为一种常见的数据结构，广泛应用于各种场景中。本文将深入探讨Java中的LinkedList，从其基本概念到实现方法，帮助读者全面理解并掌握这一重要数据结构。

1. 链表的基本概念

1.1 什么是链表？

链表是一种线性数据结构，由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针链接在一起。

1.2 链表的类型

链表主要有以下几种类型：

• 单向链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
• 双向链表（Doubly Linked List）：每个节点有两个指针，分别指向前一个节点和后一个节点。
• 循环链表（Circular Linked List）：尾节点的指针指向头节点，形成一个环。

2. Java中的LinkedList

2.1 LinkedList的类结构

在Java中，LinkedList是java.util包中的一个类，实现了List和Deque接口。它基于双向链表实现，提供了丰富的操作方法。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.2 LinkedList的内部结构

LinkedList的内部结构由节点（Node）组成，每个节点包含三个部分：

• 数据（item）：存储实际的数据。
• 前驱指针（prev）：指向前一个节点。
• 后继指针（next）：指向下一个节点。

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;
    }
}

3. LinkedList的常用方法

3.1 添加元素

• add(E e)：在链表末尾添加元素。
• add(int index, E element)：在指定位置插入元素。
• addFirst(E e)：在链表头部添加元素。
• addLast(E e)：在链表尾部添加元素。

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add(1, "B");
list.addFirst("C");
list.addLast("D");

3.2 删除元素

• remove()：删除并返回链表头部的元素。
• remove(int index)：删除指定位置的元素。
• remove(Object o)：删除链表中首次出现的指定元素。
• removeFirst()：删除并返回链表头部的元素。
• removeLast()：删除并返回链表尾部的元素。

list.remove();
list.remove(1);
list.remove("B");
list.removeFirst();
list.removeLast();

3.3 获取元素

• get(int index)：获取指定位置的元素。
• getFirst()：获取链表头部的元素。
• getLast()：获取链表尾部的元素。

String firstElement = list.getFirst();
String lastElement = list.getLast();
String element = list.get(1);

3.4 其他常用方法

• size()：返回链表的大小。
• contains(Object o)：判断链表是否包含指定元素。
• clear()：清空链表。
• indexOf(Object o)：返回指定元素首次出现的索引。
• lastIndexOf(Object o)：返回指定元素最后一次出现的索引。

int size = list.size();
boolean contains = list.contains("A");
list.clear();
int index = list.indexOf("B");
int lastIndex = list.lastIndexOf("C");

4. LinkedList的实现原理

4.1 添加元素的实现

当调用add(E e)方法时，LinkedList会在链表末尾添加一个新节点。具体步骤如下：

1. 创建一个新节点，其prev指向当前尾节点，next为null。
2. 将当前尾节点的next指向新节点。
3. 更新链表的尾节点为新节点。

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;
    else
        l.next = newNode;
    size++;
    modCount++;
}

4.2 删除元素的实现

当调用remove()方法时，LinkedList会删除链表头部的节点。具体步骤如下：

1. 获取头节点的next节点。
2. 将头节点的item和next置为null，帮助垃圾回收。
3. 更新链表的头节点为next节点。
4. 如果链表为空，将尾节点也置为null。

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

5. LinkedList的优缺点

5.1 优点

• 动态大小：链表的大小可以动态调整，不需要预先分配内存。
• 插入和删除高效：在链表中插入和删除元素的时间复杂度为O(1)，特别是在头部和尾部操作时。

5.2 缺点

• 随机访问效率低：链表不支持随机访问，访问某个元素需要从头节点开始遍历，时间复杂度为O(n)。
• 内存开销大：每个节点需要额外的内存空间存储指针。

6. 总结

LinkedList是Java中一个重要的数据结构，适用于频繁插入和删除操作的场景。通过理解其内部实现和常用方法，开发者可以更好地利用LinkedList来构建高效、灵活的应用程序。希望本文能帮助读者深入理解LinkedList，并在实际开发中灵活运用。