首页 💻 数据结构,🔴 Java

LinkedList

成员变量

transient int size = 0;    // 容量
transient Node<E> first;    // 头节点
transient Node<E> last;    // 尾节点

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

其中Node为每个节点的数据结构, 是 LinkedList 中的内部类, 定义了数据元素, 头节点和尾节点, 是典型的双向链表结构


构造方法

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList 提供了两个构造方法:

  • 第一个构造方法仅仅构造一个空的列表, 没有任何元素, size = 0, first 和 last 都为 null
  • 第二个构造方法构造一个包含指定 Collection 中所有元素的列表, 该构造方法首先会调用空的构造方法, 然后通过 addAll() 的方式把 Collection 中的所有元素添加进去

主要操作方法

1. add操作

添加元素到链表末尾

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

此 add 方法直接调用了 linkLast 方法, 该方法做了三件事情: 1. 创建一个新的节点; 2. 改变其前后引用; 3. 将 size 加1, 时间复杂度O(1)

在指定位置添加元素

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) {
    // assert succ != null;
    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++;
}

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

首先判断索引时候合法, 如果索引和 size 相等则将元素添加到最后, 否则将该元素插入的 index 的位置, 其中node(index) 是获取 index 位置的节点, linkBefore 负责把元素 e 插入到 succ 之前, 时间复杂度O(n)
ps: 这里的node函数写的很好, 不是傻乎乎的从前往后遍历来寻找, 而是和 size 的一半比较一下大小, 如果较小则从前往后找; 如果较大则从后往前找, 这在数据量大的情况下是会节约时间的

2. get操作
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

首先判断索引是否合法, 如果合法则调用node方法获取节点位置, 然后进行返回

3. remove操作

移除指定位置的元素

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

E unlink(Node<E> x) {
    // assert x != null;
    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;
}

首先判断索引是否合法, 如果合法则调用 unlink 释放节点, 具体实现是判断一下前后有没有元素, 然后将前面的元素指向后面, 后面的元素指向前面, 时间复杂度O(n)

移除指定元素

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

判断要移除的元素是否为 null, 然后在遍历链表, 找到该元素第一次出现的位置, 移除


总结

一般情况下, LinkedList 与 ArrayList 相比, 插入和删除速度更快, 但随机访问速度就慢了许多, 虽然这是一般情况, 但多数情况不是, 具体问题还是具体分析, 看看这两个的利与弊, 再决定用哪种数据结构




文章评论