编程技术网

关注微信公众号,定时推送前沿、专业、深度的编程技术资料。

 找回密码
 立即注册

QQ登录

只需一步,快速开始

极客时间

java集合list,arrayList,linkedList源码分析

李轼 集合 2021-11-29 22:49 234人围观

腾讯云服务器

1 List

1.1 ArrayList

1.1.1 整体架构

ArrayList 底层数据结构为数组

  • 查询和修改速度很快(仅需根据数组下标直接获取当前元素进行修改)
  • 增加删除速度较慢(添加触发扩容时会拷贝整个数组,删除时会拷贝删除元素后的部分数组)

1. 重点属性

  • elementData 表示数组本身
  • DEFAULT_CAPACITY 表示数组初始大小,默认值为10
  • 扩容为原数组大小的1.5倍
  • size 表示当前数组大小
  • modCount 表示当前数组被修改的版本次数,若数组结构变动则 +1

2. 类注释

  • 允许添加 null 值,会自动扩容
  • size()、isEmpty()、get()、set()、add() 等方法的时间复杂度都是O(1)
  • 非线程安全的(多线程下推荐使用线程安全类:Collection#synchronizedList)
  • 使用增强 for 循环,或迭代器迭代过程中,如果数组大小被改变,会快速失败,抛异常

1.1.2 初始化

  • 无参初始化:数组大小默认为空

    第一次调用 add 进行扩容时,才会使数组长度为 10

  • 指定大小初始化

  • 指定初始数据初始化

指定初始数据初始化源码:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//无参数直接初始化,数组大小为空
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//指定初始数据初始化
public ArrayList(Collection<? extends E> c) {
    //elementData 是保存数组的容器,默认为 null
    elementData = c.toArray();
    //如果给定的集合(c)数据有值
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //如果集合元素类型不是 Object 类型,我们会转成 Object
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // 给定集合(c)无值,则默认空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

1.1.3 新增和扩容

1. 新增流程

①判断是否需要扩容,需要则扩容

②赋值

2. 新增源码

public boolean add(E e) {
  //确保数组大小是否足够,不够执行扩容,size 为当前数组的大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接赋值,线程不安全的
  elementData[size++] = e;
  return true;
}

3. 扩容特性

  • 扩容大小是原来容量的1.5倍
  • 数组长度最大值为 Integer.MAX_VALUE 即2^32
  • 新增时允许 null 值

4. 扩容源码

private void ensureCapacityInternal(int minCapacity) {
  //如果初始化数组大小时,有给定初始值,以给定的大小为准,不走 if 逻辑
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //确保容积足够
  ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
  //记录数组被修改
  modCount++;
  // 如果我们期望的最小容量大于目前数组的长度,那么就扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

//扩容,并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的值 < 我们的期望值,扩容后的值就等于我们的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的值 > jvm 所能分配的数组的最大值,那么就用 Integer 的最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通过复制进行扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

1.1.4 扩容底层实现

通过 System.arrayCopy 方法,新建一个预期容量的数组,将旧数组的数据与新增数据一并拷贝到新数组中。

/**
 * @param src     被拷贝的数组
 * @param srcPos  从数组那里开始
 * @param dest    目标数组
 * @param destPos 从目标数组那个索引位置开始拷贝
 * @param length  拷贝的长度 
 * 此方法是没有返回值的,通过 dest 的引用进行传值
 */
public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length);

1.1.5 删除

1. 删除特性

  • 新增允许 null 值
  • 通过 equals 获取元素的索引位置,非基本类型必须重写 equals 方法
  • 删除某个元素后,只会把数组后面的元素向前移动

2. 删除源码

public boolean remove(Object o) {
  // 如果要删除的值是 null,找到第一个值是 null 的删除
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    // 如果要删除的值不为 null,找到第一个和要删除的值相等的删除
    for (int index = 0; index < size; index++)
      // 这里是根据  equals 来判断值相等的,相等后再根据索引位置进行删除
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

private void fastRemove(int index) {
  // 记录数组的结构要发生变动了
  modCount++;
  // numMoved 表示删除 index 位置的元素后,需要从 index 后移动多少个元素到前面去
  // 减 1 的原因,是因为 size 从 1 开始算起,index 从 0开始算起
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 从 index +1 位置开始被拷贝,拷贝的起始位置是 index,长度是 numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //数组最后一个位置赋值 null,帮助 GC
  elementData[--size] = null;
}

1.1.6 迭代器

1. 迭代器重要参数

int cursor;// 迭代过程中,下一个元素的位置,默认从 0 开始。
int lastRet = -1; // 新增场景:表示上一次迭代过程中,索引的位置;删除场景:为 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代过程中,期望的版本号;modCount 表示数组实际的版本号。

2. 迭代器的三个方法

  • hasNext() 还有没有值可以迭代
  • next() 如果有值可以迭代,迭代的值是多少
  • remove() 删除当前迭代的值

3. 迭代器的方法源码

1)hasNext()

public boolean hasNext() {
  return cursor != size;//cursor 表示下一个元素的位置,size 表示实际大小,如果两者相等,说明已经没有元素可以迭代了,如果不等,说明还可以迭代
}

2)next()

public E next() {
  //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
  checkForComodification();
  //本次迭代过程中,元素的索引位置
  int i = cursor;
  if (i >= size)
    throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
    throw new ConcurrentModificationException();
  // 下一次迭代时,元素的位置,为下一次迭代做准备
  cursor = i + 1;
  // 返回元素值
  return (E) elementData[lastRet = i];
}
// 版本号比较
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

3)remove()

public void remove() {
  // 如果上一次操作时,数组的位置已经小于 0 了,说明数组已经被删除完了
  if (lastRet < 0)
    throw new IllegalStateException();
  //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    // -1 表示元素已经被删除,这里也防止重复删除
    lastRet = -1;
    // 删除元素时 modCount 的值已经发生变化,在此赋值给 expectedModCount
    // 这样下次迭代时,两者的值是一致的了
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}
  • lastRet = -1 的操作目的,是防止重复删除操作
  • 删除元素成功时,数组当前 modCount 就会发生变化,这里会把 expectedModCount 重新赋值,下次迭代时两者的值就会一致了

1.2 LinkedList

1.2.1 整体架构

LinkedList 底层数据结构为双向链表,实现了 Queue 接口。

  • 新增和删除速度很快(仅需修改前后节点的指向)
  • 查询和修改速度较慢(查询采用二分法,但仍然需要从头部或尾部遍历到指定节点,修改同理)

1. 双向链表特性

  • 链表的节点叫 Node,Node 有 prev 和 next 属性,分别表示前节点和后节点
  • 链表头节点(first)的前节点是 null
  • 链表尾节点(last)的后节点是 null
  • 链表无数据时,first 和 last 为同一个节点,前后指向均为 null
  • 系统内存足够大时,链表大小不限制

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

1.2.2 追加节点

  • 追加到链表尾部,add() 方法
  • 追加到链表头部,addFirst() 方法

1. add() 源码

// 从尾部开始追加节点
void linkLast(E e) {
    // 把尾节点数据暂存
    final Node<E> l = last;
    // 新建新的节点,初始化入参含义:
    // l 是新节点的前一个节点,当前值是尾节点值
    // e 表示当前新增节点,当前新增节点后一个节点是 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 新建节点追加到尾部
    last = newNode;
    //如果链表为空(l 是尾节点,尾节点为空,链表即空),头部和尾部是同一个节点,都是新建的节点
    if (l == null)
        first = newNode;
    //否则把前尾节点的下一个节点,指向当前尾节点。
    else
        l.next = newNode;
    //大小和版本更改
    size++;
    modCount++;
}

2. addFirst() 源码

// 从头部追加
private void linkFirst(E e) {
    // 头节点赋值给临时变量
    final Node<E> f = first;
    // 新建节点,前一个节点指向null,e 是新建节点,f 是新建节点的下一个节点,目前值是头节点的值
    final Node<E> newNode = new Node<>(null, e, f);
    // 新建节点成为头节点
    first = newNode;
    // 头节点为空,就是链表为空,头尾节点是一个节点
    if (f == null)
        last = newNode;
    //上一个头节点的前一个节点指向当前节点
    else
        f.prev = newNode;
    size++;
    modCount++;
}

1.2.3 删除节点

  • 从头部删除元素,unlinkFirst() 方法
  • 从尾部删除元素,unlinkLast() 方法

删除操作会把节点的值,前后指向节点都置为 null,帮助 GC 进行回收。

1. unlinkFirst() 方法

// 从头删除节点 f 是链表头节点
private E unlinkFirst(Node<E> f) {
    // 拿出头节点的值,作为方法的返回值
    final E element = f.item;
    // 拿出头节点的下一个节点
    final Node<E> next = f.next;
    //帮助 GC 回收头节点
    f.item = null;
    f.next = null;
    // 头节点的下一个节点成为头节点
    first = next;
    //如果 next 为空,表明链表为空
    if (next == null)
        last = null;
    //链表不为空,头节点的前一个节点指向 null
    else
        next.prev = null;
    //修改链表大小和版本
    size--;
    modCount++;
    return element;
}

2. unlinkLast() 方法

// 从尾部删除节点 f 是链表尾节点
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;
    }

1.2.4 查询节点

1. 查询流程

采取简单二分法

①判断索引在链表的前半部分,还是后半部分

②在前半部分则从头开始遍历,否则从尾部开始遍历

2. 查询源码

// 根据链表索引位置查询节点
Node<E> node(int index) {
    // 如果 index 处于队列的前半部分,从头开始找,size >> 1 是 size 除以 2 的意思。
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 直到 for 循环到 index 的前一个 node 停止
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {// 如果 index 处于队列的后半部分,从尾开始找
        Node<E> x = last;
        // 直到 for 循环到 index 的后一个 node 停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

1.2.5 方法对比

LinkedList 实现了 Deque 接口(Deque 接口继承 Queue 接口)

方法返回异常返回特殊值底层实现
新增add(e)offer(e)底层实现相同
删除remove()poll(e)链表为空时,remove 会抛异常,poll 返回 null
查找element()peek()链表为空时,element 会抛异常,peek 返回 null

Queue 接口注释建议 add 方法操作失败时抛异常,但 LinkedList 实现的 add 方法一直返回 true。

1.2.6 迭代器

通过继承 ListIterator 接口来实现双向迭代访问。

LinkedList 需要实现双向迭代访问,无法通过继承 Iterator 来实现。

迭代顺序方法
从头到尾迭代方法hasNext、next、nextIndex
从尾到头迭代方法hasPrevious、previous、previousIndex

1. 迭代器源码

// 双向迭代器
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;//上一次执行 next() 或者 previos() 方法时的节点位置
    private Node<E> next;//下一个节点
    private int nextIndex;//下一个节点的位置
    //expectedModCount:期望版本号;modCount:目前最新版本号
    private int expectedModCount = modCount;
    …………
}

2. 从头到尾迭代方法

// 判断还有没有下一个元素
public boolean hasNext() {
    return nextIndex < size;// 下一个节点的索引小于链表的大小,就有
}

// 取下一个元素
public E next() {
    //检查期望版本号有无发生变化
    checkForComodification();
    if (!hasNext())//再次检查
        throw new NoSuchElementException();
    // next 是当前节点,在上一次执行 next() 方法时被赋值的。
    // 第一次执行时,是在初始化迭代器的时候,next 被赋值的
    lastReturned = next;
    // next 是下一个节点了,为下次迭代做准备
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

从头部遍历时,直接取当前节点的下一个节点即可。

3. 从尾到头迭代方法

// 如果上次节点索引位置大于 0,就还有节点可以迭代
public boolean hasPrevious() {
    return nextIndex > 0;
}
// 取前一个节点
public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();
    // next 为空场景:1:说明是第一次迭代,取尾节点(last);2:上一次操作把尾节点删除掉了
    // next 不为空场景:说明已经发生过迭代了,直接取前一个节点即可(next.prev)
    lastReturned = next = (next == null) ? last : next.prev;
    // 索引位置变化
    nextIndex--;
    return lastReturned.item;
}

从尾部开始遍历时,需要判断 next 不为空和为空的场景(见代码注释)。

4. 迭代器删除

public void remove() {
    checkForComodification();
    // lastReturned 是本次迭代需要删除的值,分以下空和非空两种情况:
    // lastReturned 为空,说明调用者没有主动执行过 next() 或者 previos(),直接报错
    // lastReturned 不为空,是在上次执行 next() 或者 previos()方法时赋的值
    if (lastReturned == null)
        throw new IllegalStateException();
    Node<E> lastNext = lastReturned.next;
    //删除当前节点
    unlink(lastReturned);
    // next == lastReturned 的场景分析:从尾到头递归顺序,并且是第一次迭代,并且要删除最后一个元素的情况下
    // 这种情况下,previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等
    if (next == lastReturned)
        // 这时候 lastReturned 是尾节点,lastNext 是 null,所以 next 也是 null,这样在 previous() 执行时,发现 next 是 null,就会把尾节点赋值给 next
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

迭代过程中需要删除的值,需要判断空和非空两种情况(见代码注释)。

转自:网络
腾讯云服务器 阿里云服务器


关注微信
^