Java容器源码分析之LinkedList


	Java容器源码分析之LinkedList
[编程语言教程]

LinkedList简介

LinkedList是一个使用双向链表结构实现的容器,与ArrayList一样,它能动态扩充其长度,LinkedList相较于ArrayList,其任意位置插入速度比ArrayList要快,但是其查询速度要比ArrayList要慢;LinkedList继承自AbstractSequentialList,实现了List、Deque、Cloneable、Serializable接口。

LinkedList UML图如下:

LinkedList UML图

和ArrayList一样,LinkedList也不是一个线程安全的容器。

LinkedList源码分析

构造方法

LinkedList有两个构造方法:

public LinkedList() {
}

//从已有的一个容器创建一个LinkedList对象
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

addAll()方法:

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    //检查index是否溢出
    checkPositionIndex(index);
    
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //获取第index位置的node元素和node的前一个元素
    //succ:第index位置的node元素
    //pred:index位置前一个node元素
    Node<E> 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 = newNode;
    }

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

    size += numNew;
    modCount++;
    return true;
}

add方法

LinkedList也有两个add方法,如下:

public boolean add(E e) {
    //添加元素到队尾
    linkLast(e);
    return true;
}

public void add(int index, E element) {
    //检查index是否溢出
    checkPositionIndex(index);

    if (index == size)
        //index == size,直接添加到队尾
        linkLast(element);
    else
        //index != size,添加元素到index位置
        linkBefore(element, node(index));
}

linkLast方法:

void linkLast(E e) {
    final Node<E> l = last;
    //新建一个node,将其前一个元素指针指向原链表的最后一个元素
    final Node<E> newNode = new Node<>(l, e, null);
    //更新尾指针
    last = newNode;
    if (l == null)
        //若原last==null说明此时链表就一个元素
        first = newNode;
    else
        //更新原链表尾元素指针
        l.next = newNode;
    size++;
    modCount++;
}

linkBefore方法:

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //获取指定位node元素的前一个元素pred
    final Node<E> pred = succ.prev;
    //新建一个node,将其前指针指向pred元素
    final Node<E> newNode = new Node<>(pred, e, succ);
    //将指定位置的node元素的前指针指向新元素,完成插入
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

获取指定位置node指针方法node:

Node<E> node(int index) {
    // assert isElementIndex(index);
    //index > size/2时,说明在链表前半段,从前往后搜索
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    //index < size/2时,从后往前搜索
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

get方法

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

get方法也比较简单,首先检测index是否溢出,然后直接找到index位置的元素,并返回其item。

Java容器源码分析之LinkedList

原文地址:https://www.cnblogs.com/Sirius-/p/13934542.html

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » Java容器源码分析之LinkedList