LinkedList源码分析

2020 年 11 月 23 日
筆記
JAVA, Java基础, linkedlist

LinkedList

LinkedList 底层数据结构

是一个双向链表

链表结构的优缺点:

链表查询慢，需要遍历链表
链表增删快，每次只需要对链表中的一个结点添加或删除

LinkedList继承关系

Serializable 标记性接口
Cloneable 标记性接口
Deque双向队列

LinkedList源码分析

构造方法

无参构造

/**
     * 构造一个空列表。
     */
public LinkedList() {
}

带单列集合的构造

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

// 将集合插入到链表尾部，所以插入位置为size
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 将集合从指定位置开始插入
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查index位置是否合法，当index>=0并且index<=size链表中元素个数才合法，
    // 否则抛出IndexOutOfBoundsException异常
    checkPositionIndex(index);

    // 将单列集合转为Object[]数组得到集合数据
    Object[] a = c.toArray();
    // 要添加的元素数量
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 如果插入位置为尾部，前驱节点为last，后继节点为null
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 否则，调用node方法得到后继节点，再得到前驱节点
        succ = node(index);
        pred = succ.prev;
    }
	// 遍历数据将数据插入
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 初始化一个Node节点newNode，其中pre指向前一个节点pred，next指向null
        Node<E> newNode = new Node<>(pred, e, null);
        // 当插入位置为链表头部时，让first指向newNode节点
        if (pred == null)
            first = newNode;
        else
            // 否则，让前一个节点pred的后继节点指向newNode节点
            pred.next = newNode;
        // pred向前移动到新节点
        pred = newNode;
    }

    // 如果插入的位置在链表尾部，重置last指向pred
    if (succ == null) {
        last = pred;
    } else {
        // 否则，将插入的链表和之前的链表连接起来
        pred.next = succ;
        succ.prev = pred;
    }

    // 修改节点个数
    size += numNew;
    // 并发修改次数+1
    modCount++;
    return true;
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

Node<E> node(int index) {
    // 当下标位置小于元素数量的一半时，从linkedlist左边开始向后遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 当下标位置大于元素数量的一半时，从linkedlist右边开始向前遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

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

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指向新节点
    last = newNode;
    // 如果链表为空，将first指向新节点
    if (l == null)
        first = newNode;
    else
        // 如果不为空，将原链表尾部指向新节点
        l.next = newNode;
    // 节点个数+1
    size++;
    // 并发修改次数+1
    modCount++;
}

在链表指定位置插入一个新节点

public void add(int index, E element) {
    // 调用checkPositionIndex检查index位置是否合法，当index>=0并且index<=size节点数，合法；否则，抛出indexOutOfBoundsException异常
    checkPositionIndex(index);

    // 添加到链表尾部
    if (index == size)
        linkLast(element);
    else
        // 添加到链表中间, 调用node方法得到index插入位置的节点
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 先得到插入位置的前驱节点pred
    final Node<E> pred = succ.prev;
    // 新建一个节点，前驱节点指向pred，后继节点指向插入位置的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 修改插入位置节点的前驱节点指向新建的节点
    succ.prev = newNode;
    // 如果新节点是头节点，让first指向新节点
    if (pred == null)
        first = newNode;
    else
        // 如果不是，将pred的后继节点指向新建节点
        pred.next = newNode;
    // 节点个数+1
    size++;
    // 并发修改次数+1
    modCount++;
}

在链表头部插入一个节点

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    // 先得到first指向的头节点
    final Node<E> f = first;
    // 创建一个新节点，前驱节点为null，后继节点指向first
    final Node<E> newNode = new Node<>(null, e, f);
    // 让first指向新节点
    first = newNode;
    // 如果是空链表，last也要指向新节点
    if (f == null)
        last = newNode;
    else
        // 如果不是，将头节点的前驱节点指向新节点
        f.prev = newNode;
    // 节点个数+1
    size++;
    // 并发修改次数+1
    modCount++;
}

在链表尾部追加一个节点

public void addLast(E e) {
    linkLast(e);
}

void linkLast(E e) {
    // 先得到last指向的尾节点
    final Node<E> l = last;
    // 创建一个新节点，前驱节点指向last，后继节点为null
    final Node<E> newNode = new Node<>(l, e, null);
    // 让last指向新节点
    last = newNode;
    // 如果是空链表，first也要指向新节点
    if (l == null)
        first = newNode;
    else
        // 如果不是，将尾节点的后继节点指向新节点
        l.next = newNode;
    // 节点个数+1
    size++;
    // 并发修改次数+1
    modCount++;
}

get源码解析

获取指定位置的数据

public E get(int index) {
    //调用checkElementIndex检查index位置是否合法，当indexindex >= 0 && index < size节点个数时合法，否则抛出IndexOutOfBoundsException异常
    checkElementIndex(index);
    //调用node方法获取index位置的节点，返回节点的元素
    return node(index).item;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

获取链表中的第一个元素

public E getFirst() {
    final Node<E> f = first;
    // 如果头节点first为空，抛出NoSuchElementException
    if (f == null)
        throw new NoSuchElementException();
    // 否则返回头节点数据
    return f.item;
}

获取链表中的最后一个元素

public E getLast() {
    // 如果尾节点last为空，抛出NoSuchElementException
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    // 否则返回尾节点数据
    return l.item;
}

set源码分析

修改指定位置节点的元素

public E set(int index, E element) {
    // 调用checkElementIndex检查index位置是否合法，当indexindex >= 0 && index < size节点个数时合法，否则抛出IndexOutOfBoundsException异常
    checkElementIndex(index);
    // 获取指定位置index的节点
    Node<E> x = node(index);
    // 记录节点的旧值
    E oldVal = x.item;
    // 给节点赋新值
    x.item = element;
    // 返回旧值
    return oldVal;
}

indexOf源码解析

返回指定元素第一次出现的索引

public int indexOf(Object o) {
    // 初始化index=0，找不到就自增，找到就返回index
    int index = 0;
    // 如果指定元素为null，从头节点开始遍历链表，调用==进行比较
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        // 如果指定元素不为null，从头节点开始遍历链表，调用equals进行比较
        for (Node<E> x = first; x != null; x = x.next) {
            // 如果是x.item.equals(o)会有NULLPointException空指针异常
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    // 如果链表中没有该元素，返回-1
    return -1;
}

返回指定元素最后一次出现的索引

public int lastIndexOf(Object o) {
    // 初始化index=size节点个数，找不到就自减，找到就返回index
    int index = size;
    // 如果指定元素为null，从尾节点开始遍历链表，调用==进行比较
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            // 如果是先判断等于null再自减，在判断等于null的时候出现了异常，就无法进行自减操作	
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        // 如果指定元素不为null，从尾节点开始遍历链表，调用equals进行比较
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            // 如果是x.item.equals(o)会有NULLPointException空指针异常
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

remove源码解析

删除链表的第一个元素

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    // 如果头节点为null，抛出NoSuchElementException异常
    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;
    // 先记录头节点的值element
    final E element = f.item;
    // 和头节点的下一个节点next
    final Node<E> next = f.next;
    // 将头节点的数据和后继节点置为null，便于垃圾回收
    f.item = null;
    f.next = null; // help GC
    // 修改头节点为第二个节点，让first指向next
    first = next;
    // 如果next为空，说明当前链表只有一个节点，last也需要置为null
    if (next == null)
        last = null;
    else
        // 如果next不为空，将next的前驱节点置为null
        next.prev = null;
    // 节点个数+1
    size--;
    // 并发修改次数+1
    modCount++;
    // 返回记录的element值
    return element;
}

删除指定节点

public E remove(int index) {
    // 调用checkElementIndex检查index位置是否合法，当indexindex >= 0 && index < size节点个数时合法，否则抛出IndexOutOfBoundsException异常
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    // 先记录删除位置节点的数据element，前驱节点prev和后继节点next
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 如果删除的节点是头节点，first要指向删除节点的后继节点next
    if (prev == null) {
        first = next;
    } else {
        // 如果不是头节点，则让删除节点的前驱节点指向后继节点
        prev.next = next;
        // 删除节点的前驱节点置为null，方便垃圾回收
        x.prev = null;
    }

    // 如果删除的节点是尾节点，last要指向删除节点的前驱节点prev
    if (next == null) {
        last = prev;
    } else {
        // 如果不是尾节点，则让删除节点的后继节点指向前驱节点
        next.prev = prev;
        // 删除节点的后继节点置为null，方便垃圾回收
        x.next = null;
    }

    // 删除节点元素也置为null
    x.item = null;
    // 节点个数减1
    size--;
    // 并发修改次数+1
    modCount++;
    // 返回删除节点的值
    return element;
}

删除指定元素

public boolean remove(Object o) {
    // 如果删除元素是null，则从头节点开始遍历链表，调用==进行比较，再调用unlink方法删除，返回true
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 如果删除元素不是null，则从头节点开始遍历链表，调用equals进行比较，再调用unlink方法删除，返回true
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    // 如果没有删除元素，返回false
    return false;
}

iterator源码分析

public Iterator<E> iterator() {
    return listIterator();
}

public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    // 检查index
    rangeCheckForAdd(index);

    return new ListItr(index);
}

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size())
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        cursor = index;
    }

private class Itr implements Iterator<E> {
        /**
         * 后续调用next返回的元素索引。
         */
        int cursor = 0;

        /**
         * 最近一次调用next或返回的元素的索引
         * 以前。 如果此元素被调用删除，则重置为-1
         * 去除。
         */
        int lastRet = -1;

        /**
         * 检测并发修改
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            // 如果游标cursor不等于链表节点的个数，说明还有元素
            return cursor != size();
        }

        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                // 获取当前游标的值
                E next = get(i);
                lastRet = i;
                // 游标向下移
                cursor = i + 1;
                // 返回当前游标的值
                return next;
            } catch (IndexOutOfBoundsException e) {
                // 判断并发修改次数和预期修改次数是否相同，不相同抛出ConcurrentModificationException并发修改异常
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
}

Tags: JAVA Java基础 linkedlist

LinkedList源码分析

LinkedList 底层数据结构

LinkedList继承关系

LinkedList源码分析

构造方法

add源码分析

get源码解析

set源码分析

indexOf源码解析

remove源码解析

iterator源码分析

VirMach 便宜 VPS

QNews

LinkedList源码分析

LinkedList 底层数据结构

LinkedList继承关系

LinkedList源码分析

构造方法

add源码分析

get源码解析

set源码分析

indexOf源码解析

remove源码解析

iterator源码分析

分享此文：

Related Posts

沈向洋、高文、桂卫华、杨强四位院士齐聚，共话人工智能核心技术 & 关键应用落地

“大脑”生长系列（九）

在 macOS 中使用 Podman

Spring MVC——项目的开发流程

VirMach 便宜 VPS

QNews

熱門搜尋