LinkedList源码分析

目录

一、LinkedList源码

1、概述

(1)LinkedList底层维护了一个双向链表

(2)LinkedList中维护了两个属性first和last分别指向首节点和尾节点

(3)每个节点(Node对象)里又维护了prev(指向前一节点),next(指向后一节点),item(用于保存数据)三个属性,从而实现双链表

(4)因此元素的添加和删除效率较高

2、数据结构

LinedList底层是一个双链表:相较于数组更耗费空间,但删除和插入节点很快

LinkedList源码分析

二、源码分析

1、继承结构

LinkedList源码分析

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

(1)继承

(2)接口

  • List接口:LinkedList类再次实现List接口并没有实际用处
  • Serializable接口:实现该序列化接口,表明该类可以被序列化
  • Cloneable接口:可以使用Object.Clone方法,该方法可以克隆
  • 与ArrayList类相比,LinkedList还实现了Deque接口:该接口主要声明了队头队尾的一系列方法

2、属性

transient int size = 0;//记录节点个数

transient Node<E> first;//first引用指向头节点

transient Node<E> last;//last引用指向尾节点

底层存储节点数据的Node内部类——节点为Node类实例化对象

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

3、构造器

(1)无参构造器——空链表

public LinkedList() {
}

(2)LinkedList(Collection<? extends E>)——有参构造器

public LinkedList(Collection<? extends E> c) {
    this();//调用无参构造器
    addAll(c);//批量插入方法
}
addAll(Collection):boolean——在尾部批量插入
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//调用插入方法——addAll(int, Collection)
}
addAll(int, Collection):boolean——批量插入
public boolean addAll(int index, Collection<? extends E> c) {//传入节点个数和初始化参数
    checkPositionIndex(index);//检查下标合理性

    Object[] a = c.toArray();//将c集合转换为Object数组a
    int numNew = a.length;//记录数组长度
    if (numNew == 0)//数组长度为0
        return false;//返回false,初始化失败

    Node<E> pred, succ;//声明该节点的前驱节点和后继节点
    if (index == size) {//如果下标等于节点个数,即从尾部加入
        succ = null;//后继节点置空
        pred = last;//前驱节点指向老链表的last节点
    } else {//从指定位置添加节点
        succ = node(index);//后继节点指向原index处节点
        pred = succ.prev;//前驱节点指向原index处节点的前驱节点
    }

    for (Object o : a) {//遍历存放c集合的数组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;//newNode指向后继节点
        succ.prev = pred;//后继节点指向newNode
    }

    size += numNew;//元素长度更新
    modCount++;//操作次数++
    return true;//插入成功
}
checkPositionIndex(int):void——判断下标合理性
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))//若下标不合理,则抛出异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {//下标大于等于0且小于等于size返回true
    return index >= 0 && index <= size;
}
node(int):Node方法——返回原链表中index的节点
Node<E> node(int index) {//二分法查找法
    // assert isElementIndex(index);

    if (index < (size >> 1)) {//index小于size的二分之一,从头节点开始查找
        Node<E> x = first;//新建x指向first节点
        for (int i = 0; i < index; i++)//找到原链表中下标为index的节点
            x = x.next;
        return x;//返回原链表中下标为index的节点
    } else {//下标在后半部分,从尾节点开始查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

4、List接口

4.1 add(E):boolean方法

将元素添加到链表尾部

public boolean add(E e) {
    linkLast(e);//尾部插入节点
    return true;
}
linkLast(E):void——在尾部插入节点
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);//新节点的前驱节点为原链表尾节点,新节点的后继节点指向空,新节点的元素为e
    last = newNode;//尾节点更新
    if (l == null)//前驱节点为空
        first = newNode;//首节点更新
    else
        l.next = newNode;//前驱节点指向新节点
    size++;//链表长度++
    modCount++;//操作次数++
}
4.2 add(int, E):void——指定位置插入节点
public void add(int index, E element) {
    checkPositionIndex(index);//下标合理性检测

    if (index == size)//下标等于节点个数,尾部插入
        linkLast(element);//调用尾部插入方法
    else//指定位置插入
        linkBefore(element, node(index));
}
linkBefore(E, Node):void——在指定节点前插入节点
void linkBefore(E e, Node<E> succ) {//传入新节点元素e和原链表该下标的节点
    // assert succ != null;
    final Node<E> pred = succ.prev;//前驱节点指向index前节点
    final Node<E> newNode = new Node<>(pred, e, succ);//新建节点
    succ.prev = newNode;//后继节点的前驱节点指向新节点
    if (pred == null)//前驱节点为空
        first = newNode;//首节点更新
    else//不为空
        pred.next = newNode;//前驱节点的后节点指向新节点
    size++;
    modCount++;
}
4.3 get(int):E——查找
public E get(int index) {
    checkElementIndex(index);//下标合理性检测
    return node(index).item;//调用node返回index节点属性item,即节点元素数据
}
4.4 remove(int):E——删除指定位置元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
    //node(index):返回节点
}
unlink(E):E——删除指定元素的节点
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;//x的前驱节点置空
    }

    if (next == null) {//后继为空
        last = prev;
    } else {
        next.prev = prev;//后节点的前驱节点指向前节点
        x.next = null;//x的后继节点置空
    }

    x.item = null;//x元素置空
    size--;//size--
    modCount++;//操作次数++
    return element;//返回删除的元素
}
4.5 clear():void——清除链表
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {//遍历链表
        Node<E> next = x.next;//next指向x后节点
        x.item = null;//节点元素置空
        x.next = null;//x的后继节点置空
        x.prev = null;//x的前驱节点置空
        x = next;//更新x
    }
    first = last = null;//首节点尾节点置空
    size = 0;//size更新
    modCount++;//操作参数++
}
4.6 indexOf(Object):int——查找元素,返回下标
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;
}

5、Duque接口

该接口主要声明了队头队尾的一系列方法

5.1 addFirst(E):void——在链表头插入指定元素
public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {//在链表头插入新元素
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
5.2 addLast(E):void——在链表尾插入指定元素
public void addLast(E e) {
    linkLast(e);
}

三、总结

1、LinkedList和ArrayList的差别

(1)LinkedList内部使用链表实现,相比于ArrayList更加耗费空间

(2)LinkedList插入,删除节点不用大量copy原来的元素,效率更高

(3)LinkedList查找元素使用遍历,效率一般

(4)LinkedList同时是双向队列的实现

上一篇:LinkedList实现分析(一)——LinkedList初探与对象创建


下一篇:LinkedList源码解析