Java中LinkedList数据结构怎么实现

在Java中，LinkedList是一种常用的数据结构，它实现了List接口和Deque接口。LinkedList基于双向链表实现，因此它在插入和删除操作上具有较高的效率，但在随机访问元素时性能较差。本文将详细介绍LinkedList的实现原理及其在Java中的使用。

1. LinkedList的基本结构

LinkedList内部使用一个静态内部类Node来表示链表中的节点。每个Node节点包含三个部分：

• item：存储当前节点的数据。
• next：指向下一个节点的引用。
• prev：指向前一个节点的引用。

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类中维护了两个重要的属性：

• first：指向链表的第一个节点。
• last：指向链表的最后一个节点。

transient Node<E> first;
transient Node<E> last;

2. LinkedList的常用操作

2.1 添加元素

LinkedList提供了多种添加元素的方法，常用的有add(E e)、add(int index, E element)和addFirst(E e)等。

2.1.1 在链表末尾添加元素

add(E e)方法用于在链表的末尾添加元素。具体实现如下：

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

在这个方法中，首先获取链表的最后一个节点l，然后创建一个新的节点newNode，并将其prev指向l。如果l为null，说明链表为空，此时newNode既是第一个节点也是最后一个节点。否则，将l的next指向newNode。

2.1.2 在指定位置插入元素

add(int index, E element)方法用于在链表的指定位置插入元素。具体实现如下：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

在这个方法中，首先检查索引是否合法。如果索引等于链表的长度，则调用linkLast方法在链表末尾添加元素。否则，调用linkBefore方法在指定节点succ之前插入新节点。

2.2 删除元素

LinkedList提供了多种删除元素的方法，常用的有remove()、remove(int index)和removeFirst()等。

2.2.1 删除链表末尾的元素

removeLast()方法用于删除链表的最后一个元素。具体实现如下：

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

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

在这个方法中，首先获取链表的最后一个节点l。如果l为null，说明链表为空，抛出NoSuchElementException异常。否则，调用unlinkLast方法删除最后一个节点，并返回该节点的元素。

2.2.2 删除指定位置的元素

remove(int index)方法用于删除链表中指定位置的元素。具体实现如下：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

在这个方法中，首先检查索引是否合法。然后调用node(index)方法获取指定位置的节点x，最后调用unlink方法删除该节点，并返回该节点的元素。

2.3 获取元素

LinkedList提供了多种获取元素的方法，常用的有get(int index)、getFirst()和getLast()等。

2.3.1 获取指定位置的元素

get(int index)方法用于获取链表中指定位置的元素。具体实现如下：

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

在这个方法中，首先检查索引是否合法。然后调用node(index)方法获取指定位置的节点，并返回该节点的元素。node(index)方法通过遍历链表来获取指定位置的节点，为了提高效率，它根据索引的位置决定是从头开始遍历还是从尾开始遍历。

3. LinkedList的优缺点

3.1 优点

• 插入和删除效率高：由于LinkedList基于双向链表实现，插入和删除操作只需要修改相邻节点的引用，时间复杂度为O(1)。
• 动态扩容：LinkedList不需要预先分配内存空间，可以根据需要动态增加或减少节点。

3.2 缺点

• 随机访问效率低：由于LinkedList是基于链表实现的，访问指定位置的元素需要从头或尾开始遍历，时间复杂度为O(n)。
• 内存占用较高：每个节点除了存储数据外，还需要存储前后节点的引用，因此内存占用较高。

4. 总结

LinkedList是Java中一种常用的数据结构，它基于双向链表实现，具有插入和删除效率高的优点，但在随机访问元素时性能较差。在实际开发中，应根据具体需求选择合适的数据结构。如果需要频繁进行插入和删除操作，LinkedList是一个不错的选择；如果需要频繁进行随机访问操作，ArrayList可能更为合适。