Java总结 - List实现类ArrayList&LinkedList

2022-04-25 01:24:54

本文是根据源码进行学习的,如果我有什么理解不对的地方请多指正,谢谢您

上面基本就是List集合类的类图关系了,图中省略掉了比如Cloneable等标记接口,那么List分别具体的主要实现类有:ArrayList,Vector,LinkedList,Stack,那么这篇文章会对这四个实现类进行介绍(由于篇幅原因,本文只说到了ArrayList和LinkedList)

ArrayList

这是最常用的List的实现类,那么这个类的存储是由数组实现的,如果超过数组规定阀值,那么就会进行自动扩容,自动扩容其实就是将数组数据复制到一个新的更大的数组中以达到扩容的目的,我们来看一下ArrayList的部分属性源码

//默认容量,将在添加第一个元素时扩展为 DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY = 10;
//共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//这是保存数据的数组,非私有以简化嵌套类访问
//arraylist 的容量是此array数组的长度
//当第一个元素被添加时,当任何一个空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都会被扩展为DEFAULT_CAPACITY
transient Object[] elementData;
//共享空数组实例，用于默认大小的空实例
//将其与 EMPTY_ELEMENTDATA 区分开来,以了解添加第一个元素时要增加多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private int size;
...

初始化

ArrayList提供了三种构造方法,如下

public ArrayList() {...}
public ArrayList(int initialCapacity) {...}
public ArrayList(Collection<? extends E> c) {...}

空参 : 我们从第一个ArrayList的空参的构造方法介绍,下面是源码的实现
```
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```
怎么理解之前的代码注释当第一个元素被添加时,任何一个空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都会被扩展为DEFAULT_CAPACITY呢?ArrayList为空并且两个属性值相等的时候,说明是调用了无参构造,在构造执行完的时候,并没有被构造为默认大小,而是当第一个元素添加时候,判断的条件成立即两属性值相等,才会进行扩展为默认大小

所以说当我们构建空参对象的时候,初始值数组长度是为0的,并没有直接扩充为长度为10的数组,代码验证

public static void main(String[] args) throws Exception {
    ArrayList<String> arrayList = new ArrayList<>();
    getSize(arrayList);
    arrayList.add("x");
    getSize(arrayList);
}
private static void getSize(ArrayList<String> arrayList) throws Exception {
    Field elementData = arrayList.getClass().getDeclaredField("elementData");
    elementData.setAccessible(true);
    Object[] o = (Object[]) elementData.get(arrayList);
    System.out.println(o.length);
}
//0 10
//而当我们以0为初始化长度参数创建ArrayList的时候,其实就是告诉他我一个都不存,所以他就创建了一个0长度的数组,而当我们添加数据的时候,就会自动扩容一个
//验证 : 可以将初始化改成这样        ArrayList<String> arrayList = new ArrayList<>(0);
//然后输出为 0 1
//所以这也就是为什么要区分DEFAULTCAPACITY_EMPTY_ELEMENTDATA  与 EMPTY_ELEMENTDATA

从中我们可以看到,只是初始化空参的ArrayList的话,那么只是将一个空数组赋值给elementData属性,那么EMPTY_ELEMENTDATA也是空数组对象,他是用来干啥的呢?他只是用作是构造有参空ArrayLIst的时候=0.而DEFAULTCAPACITY_EMPTY_ELEMENTDATA才是我们构造空参ArrayList时候使用的对象,即这样的,从下面一个分析另一个构造的时候就能看出来
```
//使用EMPTY_ELEMENTDATA
List<String> arrayList = new ArrayList<>(0);
//使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA
List<String> arrayList = new ArrayList<>();
```

我们还注意到DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA都是以private static final修饰,所以这两个空数组是属于类的,仅存在一份,说这个的意思就是,当你创建两个容量为0的ArrayList的时候,都会指向一个堆内存中的对象,我们可以尝试一下

public static void main(String[] args) throws Exception {
    ArrayList<String> list1 = new ArrayList<>();
    Field elementData1 = list1.getClass().getDeclaredField("elementData");
    elementData1.setAccessible(true);
    Object o1 = elementData1.get(list1);
    ArrayList<String> list2 = new ArrayList<>();
    Field elementData2 = list2.getClass().getDeclaredField("elementData");
    elementData2.setAccessible(true);
    Object o2 = elementData1.get(list2);
    System.out.println(o1 == o2);
} //true

所以ArrayList其实已经想好了为我们的空集合做一个缓存,而当我们向空集合中添加数据的时候,elementData就会指向其他的对象,这个是add方法的源码范围,所以一会再说,到这第一个空参的构造方法已经介绍的差不多了,下面是有int类型参数的构造方法的源码实现

public ArrayList(int initialCapacity) {
  //不为0,按照指定长度创建数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
      //为0就直接指向创建好的数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
      //参数不合法
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

不用细说,这个是很容易的,也可以看出来为什么ArrayList要设计两个空数组以备使用,这个构造没什么可说的,那么下面就是以集合为参数的创建方式的源码

//将参数转换为ArrayList
public ArrayList(Collection<? extends E> c) {
  //因为Collection中就定义了toArray方法,所以他的实现类就都会实现自己的toArray,所以可以直接调用返回数组而不会出错
    elementData = c.toArray();
    //如果返回的数组的长度不是空的数组的话
    if ((size = elementData.length) != 0) {
      //防范c.ToArray错误不返回Object[]
        if (elementData.getClass() != Object[].class)
        //那么就将elementData中的元素都转换为Object类型
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //到这就是空数组,所以直接引用创建好的空数组即可,还能节省空间
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

到这ArrayList的创建方式大概的就过了一边,那么下面的ArrayList的实现方法,我就只挑几个核心方法来看一下源码

add

首当其冲的就是add,我们使用一下ArrayList来add元素,然后我们进行代码走读,那么我们看一下源码

//使用
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
//源码开始
public boolean add(E e) {
    modCount++;  //代表操作ArrayList的次数,有关于fast-fail机制,之后再说
    //参数值:并不是A参数是一个URL, 数组对象 , 2
    add(e, elementData, size); //调用类中方法
    return true; //返回结果
} // 结束代码

上面可以说是很简单了,但是在debug的时候我发现存储元素的elementData数组中其实已经有东西了,如下图

然后当我debug step over到结束代码的时候,程序跳到这这样一个代码

public synchronized void addURL(URL url) {
    if (closed || url == null)
        return;
    synchronized (unopenedUrls) {
        if (! path.contains(url)) {
            unopenedUrls.addLast(url);
            path.add(url);
        }
    }
}
//再跳
public InternalError(String message) {
    super(message);
}
//还跳
static {
    System.loadLibrary("instrument");
}
//还有很多...

上面的一些代码其实不用知道其意思,但是可以告诉我们的是,ArrayList中的elementData不单纯是存储我们需要存储的元素的,而是在首次add的时候会借助elementData这个数组去加载一些文件或者其他东西,而在第二次add的时候就不需要这个步骤了,并且在首次加载完一些路径后或者库后,elementData就会将他们清除,以为已经加载上了,然后这时候才会来存储我们的元素,录了一段小视频,可以下载来看一下
经过后面再次实验, 除了首次使用ArrayList的add方法会加载一些东西,当我们再次new出ArrayList的时候,首次使用add方法就不会再家在任何东西了,如下的测试代码
```
List<String> list = new ArrayList<>();
list.add("X");
List<String> list2 = new ArrayList<>();
list2.add("X");
```
其中在我debug时候会看到很多getLoader`loders一些方法或者属性,那么在这感觉是首次使用ArrayList的类加载机制在起作用,我在社区提问题了,所以大家可以看一下,联想到类加载机制非常感谢回复我的1382148494135822`大哥, 问答页 : 关于ArrayList的问题,请大佬进来看看

回到add方法上来,我们发现它会调用类中的另一个add方法.源码如下

private void add(E e, Object[] elementData, int s) {
  //如果满了就扩容
    if (s == elementData.length)
        elementData = grow();
    //然后将要存的元素存入到数组指定位置
    elementData[s] = e;
    //加一
    size = s + 1;
}

这个方法中用到的grow方法源码如下

private Object[] grow() {
    return grow(size + 1);
}
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}
//返回至少与给定最小容量相同的容量
private int newCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    //10+(10>>1)=15 ,即扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //扩容后如果还比最小的容量小或者相等的话
    if (newCapacity - minCapacity <= 0) {
      //判断是否是初始化的情况
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        //是的话就直接返回默认容量10,从这就可以看出来才刚开始初始化大小
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow错误,最小值不可能是负数
            throw new OutOfMemoryError();
        //如果不是初始化也不是参数错误,那么就返回最小的容量
        return minCapacity;
    }
    //到这表示扩容后的容量比最小容量要大
    //是否达到了最大长度,如果没到达就返回扩容后的长度,否则就调用hugeCapacity
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow错误
        throw new OutOfMemoryError();
    //如果达到了规定的最大数组长度,那么就扩容到整数的最大长度,否则就是当前默认的数组最大长度
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

还有一个指定位置的add方法,下面是源码实现

public void add(int index, E element) {
    //检查是否数组越界
    rangeCheckForAdd(index);
    modCount++;
    final int s; //临时保存size
    Object[] elementData; //临时保存elementData
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow(); //如果长度等于size代表要扩容了
    //核心方法System.arraycopy,他会将你要操作的index地方的位置空出了
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    //然后index空出来的位置赋值               
    elementData[index] = element;
    //加一
    size = s + 1;
}

好了ArrayList的add方法已经介绍完了,如果有不对的地方请指正

addAll

源码实现

public boolean addAll(Collection<? extends E> c) {
  //转换数组
    Object[] a = c.toArray();
    modCount++;
    //获取传入集合的长度
    int numNew = a.length;
    //是空集合的话直接返回
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    //如果传入集合的长度大于elementData中空余的位置个数就增长
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    //增长完了就将传入的数据copy进去
    System.arraycopy(a, 0, elementData, s, numNew);
    //元素个数修改
    size = s + numNew;
    //返回成功
    return true;
}

Get

源码实现

public E get(int index) {
    //检查index
    Objects.checkIndex(index, size);
    //然后调用方法
    return elementData(index);
}
E elementData(int index) {
  //直接下标取元素
    return (E) elementData[index];
}

很简单就不说了

remove

源码实现按照索引删除

public E remove(int index) {
    //检查index
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    //用于返回值
    E oldValue = (E) es[index];

    fastRemove(es, index);
    return oldValue;
}
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    //去掉一个元素后的长度如果大于指定删除的索引的位置
    if ((newSize = size - 1) > i)
    //把删除元素后面的元素往前挪一位
        System.arraycopy(es, i + 1, es, i, newSize - i);
    //避免内存泄露
    es[size = newSize] = null;
}

源码实现按照对象删除

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;  //元素首次出现位置记录
    //寻找元素的逻辑
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        //到这代表没找到.返回false
        return false;
    }
    //找到了就按照下标删除
    fastRemove(e  s, i);
    return true;
}

indexOf

源码实现

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
              //寻找到首个想等元素的时候返回索引
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
              //寻找到首个想等元素的时候返回索引
                return i;
            }
        }
    }
    //未找到返回-1
    return -1;
}

这个实现比较简单,并且ArrayList的一些*indexOf*类似的方法的大致思路都是如此的

writeObject

这是序列化的方法

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    //将操作次数记录
    int expectedModCount = modCount;
    //将类中的no-static和no-transient属性写到流中
    s.defaultWriteObject();
    s.writeInt(size);
    //依次写出元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    //如果再次过程中数组中内容遭到改变,序列化停止并且抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

readObject

这是反序列化的方法

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // 读取大小和其他的内容
    s.defaultReadObject();
    //读取容量
    s.readInt();
    //如果读取到size>0
    if (size > 0) {
        // 与clone()一样,根据大小而非容量分配数组
        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
        //创建存储数组
        Object[] elements = new Object[size];
        //依次将数据读出来并赋值
        for (int i = 0; i < size; i++) {
            elements[i] = s.readObject();
        }
        //然后赋值给本类的全局变量
        elementData = elements;
    } else if (size == 0) {
      //size为0代表空集合,那么就直接使用常量替换
        elementData = EMPTY_ELEMENTDATA;
    } else {
      //非法的,出异常
        throw new java.io.InvalidObjectException("Invalid size: " + size);
    }
}

好了到这我自己认为比较重要的方法源码就都列出来的,所以将ArrayList的介绍就告一段落了,那么到这我就只有一个疑问就是关于elementData在首次add时加载jar或者路径是做什么用的,如果您知道,请评论在下面,非常谢谢您
总结一下ArrayList,我们在分析源码的时候,除了在首次add时会添加路径之类的信息会设计到其他类的同步加载方法,但是本类的方法并没有涉及同步,所以ArrayList并不是线程安全的,并且他是懒加载的,首次默认初始化并不会就初始化为初始化容量,而是在之后才会初始化为初始化容量,这个类的核心就是System.arraycopy方法,所以以后我们在操作数组移动的时候,我们也可以使用这个native方法使得程序更加的快速准确,在add和get的时候是相当迅速而直接的,就是将制定位置元素后移并在此位置上插入元素,所以ArrayList的增加和查询是很迅速的,但是我们也需要注意,当ArrayList的元素满的时候他是创建新数组进行copy的,所以当ArrayList的元素相当大的时候,这无疑是一个恐怖的事情,所以ArrayList并不适合存储很多元素

LinkedList

可以先参考一下这篇关于链表的文章,如果你有了解一点就可以不用看了 : 链表
这是一个链表实现的List的实现类,对于ArrayList这个类要并不存在扩容copy的问题,如果你了解一点链表内容就会知道,增加元素在链表中无非就是改变引用的事情,所以它并没有这样的问题,好了让我们直接上源码吧

依旧先看一下他的成员属性

  //元素个数
  transient int size = 0;
  //头节点
  transient Node<E> first;
  //尾节点
  transient Node<E> last;

transient代表不会被序列化,那么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;
    }
}

从中可以LinkedList实现是一个双链表,我们接下来看看他的初始化方法的实现
```
public LinkedList() {
}
```

空参构造什么都没做,接下来看其他的初始化方法

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

那么这个有参的构造方法其实主要逻辑是addAll方法,我暂时先不说这个方法,那么我们先来看看其他的核心实现方法

add

源码如下

public boolean add(E e) {
    linkLast(e);  //添加到链表最后面
    return true;
}
void linkLast(E e) {
  //将最后一个元素引用保留
    final Node<E> l = last;
    //创建一个新的元素根据传入的add参数,新的对象的前一个元素的引用
    //就是之前的最后一个元素
    final Node<E> newNode = new Node<>(l, e, null);
    //将最后的元素指针指向新元素
    last = newNode;
    //如果之前的尾元素是空的代表是空链表,
    if (l == null)
    //即首尾都是此元素
        first = newNode;
    else
    //就不是空链表,那么倒数第二个的元素的下一个元素就是新元素
        l.next = newNode;
    size++;
    modCount++;
}

还有一种是根据index位置插入的

public void add(int index, E element) {
  //是否越界
    checkPositionIndex(index);
    //如果index等于元素个数
    if (index == size)
    //那么就添加到尾部
        linkLast(element);
    else
    //否则就按位置添加
    //node方法,传入index,返回指定元素索引处的（非空）节点
        linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    //已经确保了succ不为空,在上面node方法中确保的
    //取出指定index索引上的元素的前一个元素引用
    final Node<E> pred = succ.prev;
    //创建新的元素,新元素的前一个元素就是目前指定index上的元素的前一个元素
    //下一个元素是index上面的元素
    final Node<E> newNode = new Node<>(pred, e, succ);
    //将指定索引位置的原元素的前指针指向新元素
    succ.prev = newNode;
    //如果是在头部添加,那么当前元素的前一个元素肯定为空
    if (pred == null)
    //然后新元素就成为了头元素
        first = newNode;
    else
    //否则就将index-1位置的元素的后指针指向新元素
        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) {
    //检查位置是否越界
    checkPositionIndex(index);
    //集合转数组
    Object[] a = c.toArray();
    //确定集合元素个数
    int numNew = a.length;
    //如果是空集合返回
    if (numNew == 0)
        return false;
    //记录前指向和当前节点
    Node<E> pred, succ;
    //如果相等代表在最后追加
    if (index == size) {
      //在最后追加,就不需要当前元素了,因为last已经指向了
        succ = null;
        //添加集合的时候的,集合中首个被添加的元素的前一个节点就是当前链表中的最后一个节点
        pred = last;
    } else {
        //到这就代表不是在尾部追加,而是将元素追加到链表中间位置
        //node方法之前说过就是根据index来返回index位置上的节点
        //node返回节点后保存引用
        succ = node(index);
        //记录当前index节点的前节点的引用
        pred = succ.prev;
        //到这就记录好了当前节点和前节点的引用
    }
    //开始循环创建集合中的元素的节点了,然后修改相关指向
    for (Object o : a) {
        //将集合元素强转一下,泛型约束不会classcast
        E e = (E) o;
        //创建节点,此节点的前一个元素指向已经确定
        Node<E> newNode = new Node<>(pred, e, null);
        //代表从头开始添加
        if (pred == null)
        //新节点就是first节点
            first = newNode;
        else
        //新节点前指向是pred,perd.next指向新元素,所以到这形成了前元素和新元素的双向链接
            pred.next = newNode;
        //到这就连接好了旧节点和新节点,需要移动pred指向,指向新节点
        //然后将新节点当做旧节点,然后在于新创建的节点做双向链接
        pred = newNode;
    }
    //到这就把链表从头到集合所有元素都连接完成了,需要处理集合的尾节点和链表的原index节点的链接问题了
    //如果原来的尾index节点没有
    if (succ == null) {
      //那么last就指向集合的尾节点
        last = pred;
    } else {
      //代表之前的链表有index节点,那么就修改index节点和集合的尾节点的链接
        pred.next = succ;
        succ.prev = pred;
    }
    //做一些计数操作
    size += numNew;
    modCount++;
    return true;
}

到这其实add方法基本就解析完了,那么顺便前面的构造也就没有问题了,下面是其他方法的源代码

remove

remove()

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指针指向下一个元素
    first = next;
    //如果存在就只有一个元素的情况
    if (next == null)
    //first和last都是null
        last = null;
    else
    //否则就将原来头节点的下一个节点的前引用取消,因为不存在了,自己已经变成了头结点
        next.prev = null;
    size--;
    modCount++;
    return element;
}

remove(Object)

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;
}  
//整体逻辑就是:已经获得了一个node,那么node的前后引用关系就找到了,然后剩下的就是改引用关系
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;
    //如果前引用是null,就代表是头元素
    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节点已经完全脱离链表,置空
    x.item = null;
    size--;
    modCount++;
    return element;
}

removeFirst()

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f); //方法实现上面已经写出了
}

removeLast()

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l); // 跟之前的unlinkFirst类似就不再详细说了
}

remove(int)

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index)); //实现有说明在前面
}

removeFirstOccurrence&removeLastOccurrence
- 其源码就不去实现了,这个方法的作用是在于:如果指定的删除元素在链表中就删除,(区别:删除最开始出现的&删除最后一个出现的),如果不存在链表不变

Get

getFirst() & getLast(),实现比较简单就不注释了

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

get(int),实现比较简单就不注释了

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

set

set(int,E)

public E set(int index, E element) {
  //检查索引
    checkElementIndex(index);
    //利用node方法取出index上的节点
    Node<E> x = node(index);
    //保存作为返回
    E oldVal = x.item;
    //替换
    x.item = element;
    return oldVal;
}

队列操作

对于LinkedList还支持队列操作,其实现也是比较简单的,都是依靠于之前介绍的add方法和remove方法(unlink),所以不打算贴出源码了,所支持的操作有类似peek,poll,push,pop等等,只了列举部分

writeObject&readObject

至于LinkedList的序列化机制也是类似ArrayList的序列化方式和步骤,都是先将类中no-static和no-transient属性写到流中,然后写size,然后依次写元素,反序列化即相同步骤即可
总结:我们可以看到LinkedList是双向链表的实现,并没有首尾相连,所以也不是环形链表,并且其中不存在初始化容量概念,并且不存在ArrayList中的容量限制常量,所以说这个类可以做到理论上的无限大,并且从中没发现同步代码块,所以这个类也不是同步的,需要我们在使用的时候注意使用场景,对于其他的操作就是常规的链表操作

码农公寓

ArrayList

初始化

add

addAll

Get

remove

indexOf

writeObject

readObject

LinkedList

add

addAll

remove

Get

set

队列操作

writeObject&readObject

相关文章