首页 > 编程语言 >一文掌握ArrayList和LinkedList源码解读

一文掌握ArrayList和LinkedList源码解读

时间:2023-04-11 21:55:40浏览次数:47  
标签:Node index LinkedList ArrayList elementData 源码 null 节点 size

大家好,我是Leo!
今天来看一下ArrayList和LinkedList的源码,主要是看一下常用的方法,包括像add、get、remove方法,大部分都是从源码直接解读的,相信大家读完都会有一定收获。

ArrayList

List<String> list = new ArrayList<>();
list.add("zly");
list.add("coding");
list.add("菜鸟阶段!");

底层是数组:transient Object[] elementData;

构造方法: 一个是支持自定义大小的,一个是直接赋值成{}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      // 如果用户指定了初始容量
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果用户指定了初始容量为0,就赋值成一个{}
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    // DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个默认大小为0的数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

add方法:

public boolean add(E e) {
    // 确保容量足够,判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 插入数据
    elementData[size++] = e;
    return true;
}

对于扩容的解释:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 1.5倍进行扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

带索引的add方法:

public void add(int index, E element) {
    // 检查索引是否合法!
    rangeCheckForAdd(index);
    // 判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将index和之后的数据都后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 插入元素                 
    elementData[index] = element;
    size++;
}

get方法

public E get(int index) {
    // 检查索引是否合法
    rangeCheck(index);
    // 根据索引从object[] 获取数据
    return elementData(index);
}

set方法

将某个index的数据修改成指定的元素。

public E set(int index, E element) {
    rangeCheck(index);
    // 旧数据
    E oldValue = elementData(index);
    // 更新成新数据
    elementData[index] = element;
    // 返回旧数据
    return oldValue;
}

remove方法

public E remove(int index) {
    rangeCheck(index);
    // 修改次数+1
    modCount++;
    // 获取原先的值
    E oldValue = elementData(index);
    // 计算往前移动的下标
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 移动数据
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后一个树设置为null
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

remove某个元素

// 删除第一个匹配的值
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                // 快速移除值
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}    

private void fastRemove(int index) {
    // 修改次数
    modCount++;
    // 需要移动的长度
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

迭代器iterator

在ArrayList中自己实现了一个Itr迭代器,由于ArrayList是线程不安全的,所以在并发删除的时候,通过会报错Exception in thread "main" java.util.ConcurrentModificationException,并发修改错误。

因为在javac后面,增强for会被编译成iterator的形式,删除调用的是ArrayList的remove方法,而next方法是iterator内的,所以我们可以看iterator内的next方法,然后就大致知道为什么会报这个错了。

public E next() {
    // check是否有并发修改
    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];
}
// modCount在ArrayList的fastRemove已经修改了
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

那为什么使用iterator器为什么就可以安全删除呢?

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        // 虽然这里也修改了
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // 假修改了
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

elementData被transient修饰

ArrayList本身是支持序列化的,为什么存储的元素用transient修饰呢,其实在ArrayList也提供了序列化的方式,提供了readObject和writeObject两种方法。

// 序列化
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
// 反序列化
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    // Read in size, and any hidden stuff
    s.defaultReadObject();
    // Read in capacity
    s.readInt(); // ignored
    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

LinkedList

双向链表结构

LinkedList实现了List、Deque

// 链表的元素个数
transient int size = 0;

// 链表的头节点
transient Node<E> first;

// 链表的尾节点
transient Node<E> last;

我们都说LinkedList是通过双向链表实现的,那它的链表节点的结构长什么样呢?其实相信大家数据结构有了解的话,肯定也知道会有一个前缀节点和指向的下一个节点和指向的数据

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

构造函数

public LinkedList() {
}

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

那常用的方法会有哪些呢?

public E getFirst();
public E getLast();
public E removeFirst();
public E removeLast();
public void addFirst(E e) ;
public void addLast(E e);
public E get(int index);
public E set(int index, E element);

上面的方法都可以看到提供了添加和删除的方法以及获取链表头尾节点的方法,当然这里面也有迭代器的实现,下面我们再一个个开它们源码的实现。

add(E e)

首先我们先来看不指定插入头尾的方法,可以看到默认采用的是尾插法。

public boolean add(E e) {
    // 插入到尾部
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l =  ;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // 尾插法
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 元素个数+1
    size++;
    // 修改次数+1,来自AbstractList中
    modCount++;
}

当然看完上面这个方法后,再看addLast应该就是同理了,

addLast(E e)

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

addFirst(E e)

这个很明显采用的就是头插法了,每次将新插入的节点更新为新的头节点。

public void addFirst(E e) {
    linkFirst(e);
}
// null<-e->f
private void linkFirst(E e) {
    // 先copy一份当前的头节点
    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++;
}

add(int index, E element)

在指定位置插入元素,在LinkedList里面有一个default node()方法,用于查询指定索引的节点,根据位置位于大小中间左边还是右边确定用头节点还是尾节点进行遍历查询。

public void add(int index, E element) {
    // 检查索引是否合法,是否在[0,size]之间;
    checkPositionIndex(index);
    // 如果需要在最末尾进行插入
    if (index == size)
        linkLast(element);
    else
    // node(index)先查询这个索引下对应的节点
        linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 原先位置的前缀节点
    final Node<E> pred = succ.prev;
    // 插入位置的节点,下一个节点指向原先在这个位置的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    // 如果pred为null,证明该节点是头节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果查询位置位于中间位置偏左
    if (index < (size >> 1)) {
        // 遍历,找到索引位置的节点
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 从后开始遍历,找到索引位置的节点
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

remove(E e)

移除指定元素,在删除的时候需要维护first和last节点,并且只会删除第一个匹配到的元素。

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

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;
    // 如果prev为null, 说明是头节点,需要更新头节点,直接删除即可
    if (prev == null) {
        first = next;
    } else {
    //  不是头节点,将前缀节点的next指向删除节点的下一个节点
        prev.next = next;
        // GC
        x.prev = null;
    }
    // 判断是否是尾节点,是的话,更新last节点
    if (next == null) {
        last = prev;
    } else {
    // 不是,将删除节点的next节点的前缀节点改成删除节点的前缀节点
        next.prev = prev;
        x.next = null;
    }
    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);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    // 将原先的头节点的数据和指向的下一个节点置null
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
    // 将新头节点的前缀节点置null
        next.prev = null;
    size--;
    modCount++;
    return element;
}

removeLast()

删除链表的尾节点

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 将原先链表的尾节点的值和前缀节点都置null
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    // 如果前缀节点为null,说明链表只有一个元素,删除后为null
    if (prev == null)
        first = null;
    else
    //  将原尾节点的下一个节点置null
        prev.next = null;
    size--;
    modCount++;
    return element;
}

set(index, Element e)

public E set(int index, E element) {
    // 检查节点的索引是否位于[0,size)
    checkElementIndex(index);
    // 获取index的节点
    Node<E> x = node(index);
    // 更新值
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

get(int index)

获取指定位置的节点的信息

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

通过上面大家应该对ArrayList和LinkedList的源码有一定的了解,对于ArrayList的存储是数组的,LinkedList是双向链表,这两个结构非常常见和好用的。

标签:Node,index,LinkedList,ArrayList,elementData,源码,null,节点,size
From: https://www.cnblogs.com/Leo-coding/p/17307891.html

相关文章

  • 经典版DD应用系统软件库网站源码支持多方面应用
    demo软件园每日更新资源,请看到最后就能获取你想要的:1.经典版DD应用系统软件库网站源码支持多方面应用DD应用系统软件库网站源码1.增加手机端开发者中心2.增加手机端开发者中心应用管理3.增加手机端开发者中心用户管理4.增加手机端开发者中心网站管理5.增加手机端开发者中......
  • 成品直播源码,Android实现监听Settings值变化的功能
    成品直播源码,Android实现监听Settings值变化的功能先创建一个内部类继承自ContentObserver   classSettingsContentObserverextendsContentObserver{    publicSettingsContentObserver(){      super(newHandler());    }    ......
  • SpringSecurity源码-构建ProviderManager
    简介在构建WenSecurity执行生命周期AbstractConfiguredSecurityBuilder#doBuild()方法中的init(),会执行到WebSecurityConfigurerAdapter#init(WebSecurityweb)方法,会去创建HttpSecurity。在创建HttpSecurity时调用authenticationManager()构建ProviderManager。 WebSecurityCo......
  • vue2源码-二、对象响应式原理
    //循环对象进行一次劫持classObserver{constructor(value){this.walk()}walk(data){//重新定义属性Object.keys(data).forEach((key)=>defineReactive(data,key, data[key]))}}//属性劫持//对对象target,定义属性key,值为value//使用Object.definProperty重......
  • spring boot单库动态分表实现【增删查】(含源码)
    一.背景现实场景中当个别业务数据量过大时会影响系统功能性能,当整个业务还没有达到分库的级别时,动态分表也是一个的选择,基本思想是按照一定维度将数据分表存储动态查询。本次实现的是基于springboot的单表动态增删查,首先分表的规则根据一个格式生产,包含时间在其中,每一条数据......
  • C语言中的位运算符和源码反码补码的浅解
    位运算符【与(&);或(|);非(~);异或(^);移位运算符(<<和>>)】对于有符号(正负)的而言:1)二进制的最高位是符号位:0表示正数,1表示负数2)正数的原码,反码,补码都一样3)负数的反码=它的原码符号位不变,其它位取反(0->1,1->0)4)负数的补码=它的反码+1 5) 0在计算机种分+0与-0,它们的原码,补码,反码......
  • 直播网站源码,接收方收到的信息等于缓冲区长度
    直播网站源码,接收方收到的信息等于缓冲区长度原因分析:实际上是创建字符串时设置获取数据包的长度不正确,长度不应使用data.length byte[]data=packet.getData();Strings=newString(data,0,data.length);​解决方案:改用packet.getLength()即可解决 publicvoid......
  • Collection - LinkedList源码解析
    简介:LinkedList集合底层是一个双向链表结构,具有增删快,查询慢的特点,内部包含大量操作首尾元素的方法。适用于集合元素先入先出和先入后出的场景,在队列源码中被频繁使用。链表结构的节点新增、删除都非常简单,仅仅把前后节点的指向修改下就好了,所以LinkedList新增和删除速度很......
  • SpringSecurity源码之WebSecurity构建FilterChainProxy
    主要参考了https://mp.weixin.qq.com/s/D0weIKPto4lcuwl9DQpmvQ。SpringSecurity版本是2.7.9。将SpringBoot和SpringSecurity结合使用,SpringSecurity自动配置类是SecurityAutoConfiguration.class。 @AutoConfiguration@ConditionalOnClass({DefaultAuthenticationEventPubli......
  • 爬虫最后一天,爬取到的数据存到mysql中,爬虫和下载中间件、加代理、cookie、header、se
    爬到的数据存到mysql中classFirstscrapyMySqlPipeline:defopen_spider(self,spider):print('我开了')self.conn=pymysql.connect(user='root',password="",host='127.0.0.1......