MENU

Java 集合类 - 源码分析(二)LinkedList

July 12, 2018 • Code

前言:LinkedList 是 Java 中非常重要的集合类,底层是用链表实现。

注意与 ArrayList 类对比,Java 版本:1.8

继承关系

常用方法 & 内部类 & 变量

变量

transient int size = 0;
    
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
    
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

维护了链表的节点大小及首尾指针。

注意三个变量均为 transient,即三个变量均不能被序列化,同 ArrayList 一样,LinkedList 同样自定义了序列化过程(添加 writeObjectreadObject 方法)。

内部类

Node 内部类(三元组)

  • E:节点包含的对象
  • 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;
    }
}

方法

构造方法

LinkedList()

空构造方法,什么也不干。

/**
 * Constructs an empty list.
 */
public LinkedList() {
}
LinkedList(Collection<? extends E> c)

将传入的集合元素转为链表节点元素,如果传入集合为空,则报 NullPointerException。生成的链表节点由传入集合的迭代器返回顺序决定。

关键在于 addAll 方法,具体查看下面增加元素部分。

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

增加元素方法

add(E e):boolean
public boolean add(E e) {
    // 将节点 e 增加到链表的最后
    linkLast(e);
    return true;
}
add(int index, E element):void
/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    //在指定的位置增加节点
    
    // index >= 0 && index <= size 就报错 IndexOutOfBoundsException
    checkPositionIndex(index);
    
    // 索引值正好等于节点个数,则直接调用 linkLast 增加在节点的最尾处
    // 如果不相等,则调用 node 方法返回对应索引的结点,然后 调用 linkBefore 方法,
    // 将新元素加到 原结点之前
    // 注意这果 node 方法返回的节点一点非空,因为索引值在最开始就检查过了
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

上面调用了 linkLast 方法及 linkBefore 方法:

  • linkLast 方法:将节点添加到链表最后。
/**
 * Links e as last element.
 */
void linkLast(E e) {
    // 保存一下尾指点
    final Node<E> l = last;
    
    // 生成新的结点,新结点的前置指针指向链表的最后,后置为空
    final Node<E> newNode = new Node<>(l, e, null);
    
    // 将 last 指向新生成的结点
    last = newNode;
    
    // 如果 l 为空,换言之,这是添加的第一个节点,则将 first 指向新结点
    // 如果不为空,则将链表的最后结点的后置指针指向新结点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 链表大小 + 1
    size++;
    modCount++;
}
  • linkBefore 方法:将节点添加到指定节点后。

主要过程:

  1. 先保存前一个节点指针。
  2. 生成新结点,新结点前置指针指向前一个节点,后置指针指向传入节点。
  3. 传入节点的前置指针修改为新结点。
  4. 判断前上个节点是否存在,如果不存在,则说明新生成的节点应该在最开始,直接将链表首指针指向新结点;如果存在,则前一个节点的后置指针指向新生成的节点。
/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;

     // 1. 先保存前一个节点指针
    final Node<E> pred = succ.prev;
    // 2. 生成新结点,新结点前置为前一个节点,后置为传入节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 3. 传入节点的前置修改为新结点
    succ.prev = newNode;
    
    // 4. 判断前上个节点是否存在,如果不存在,则说明新生成的节点应该在最开始,直接将链表首指针指向新结点;如果存在,则前一个节点的后置指针指向新生成的节点。
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
addAll 方法
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

/* -------------------------------------------- */

public boolean addAll(int index, Collection<? extends E> c) {
    /**
     * index >= 0 && index <= size 否则抛出异常
     */
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 传入的 index 为需插入节点的位置。
    // 如果等于链表大小,则只需在链表的最后添加节点
    // 如果不等,则在链表的中间添加节点
    // succ 保存当前 index 位置上的节点
    // pred 保存 succ 前置节点。
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 使用迭代器进行添加操作,所以链节点的顺序取决于迭代器返回的顺序。
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 生成新结点
        Node<E> newNode = new Node<>(pred, e, null);
        // 前置结点为空,代表链表此时为空,将头指针指向新结点即可,否则将前置结点的后置指针指向新结点
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        // 移动 pred 指针到新结点,进行循环
        pred = newNode;
    }

    // succ 为 null,表明是在最后添加节点,直接将尾指针指向最后的结点即可。
    // succ 不为空,则是在链表的中间添加节点,需要把 succ 及后面的节点「接到」 pred 节点后面完成添加。
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    // 修正链表大小
    size += numNew;
    modCount++;
    return true;
}

删除元素方法

remove(): E

默认移除第一个节点。

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E remove() {
    // 默认移除第一个
    return removeFirst();
}

/*---------------------------------*/
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/*---------------------------------*/
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    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;
}
remove(int index): E

删除指定索引位置节点。

public E remove(int index) {
    checkElementIndex(index);
    // node 方法找到对应结点,unlink 方法除掉它
    return unlink(node(index));
}
  • unlinkLast 及 unlink 方法
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    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;
}

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

indexOf 方法

从头指针开始寻找,返回相同对象节点的索引位置。如果不存在则返回 -1。
传入 null 则返回链表中第一个为 null 的节点。

采用的是直接遍历。

public int indexOf(Object o) {
    // 寻找索引,没有什么意外,遍历
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

小结

通过源码分析 LinkedList 的操作过程,同时加深对链表的认识。

Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment