Java中LinkedList數據結構怎么實現

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可能更為合適。