LinkedList数据结构链表_linklist数据结构

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

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;
        else
            l.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;
        else
            next.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;
        }
    }

    // 省略其他细节实现
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

代码演示

下面是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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

细节分析

使用LinkedList时，有几个细节需要注意：

• 动态扩展：由于LinkedList是基于节点的，因此它可以动态地添加或删除节点而不需要像数组那样重新分配整个数据结构。
• 随机访问效率低：获取特定索引的元素时，LinkedList必须从头开始（或从尾开始，取决于哪边更近）遍历节点。因此，随机访问的效率远低于数组。
• 插入和删除效率高：在任何位置插入或删除元素时，LinkedList只需要改变几个引用，这使得插入和删除操作非常快速。
• 内存开销：与数组相比，LinkedList的每个元素都需要额外的内存空间来存储前后节点的引用。

通过以上解析，我们可以深入理解LinkedList的工作原理和设计。这有助于开发者在需要适合的数据结构时作出明智的选择。对于需要频繁插入和删除操作的场景，LinkedList可能是一个不错的选择。然而，如果需要快速通过索引访问元素，那么ArrayList可能是更好的选择。