数据结构和算法二（ArrayList和LinkedList源码解

2017-11-11 本文已影响0人小窦子

ArrayList源码解析

ArrayList 是基于数组的方式来实现数据的增加、删除、修改、查找
1、内部维护了两个变量

private transient Object[] elementData ;该数组缓存的集合中的元素，集合的容量就是该数组的长度，
    elementData 是 transient修饰，说明在序列化时 数组 elementData不在序列化范围内。
private int size;  集合的大小，集合中元素的数量

2、在看看 ArrayList的构造器

  构造一个指定容量的 initialCapacity 的空的集合 super调用的 AbstractList的默认构造方法，
  该方法是一个空的方法 然后判断传入的参数不能小于 0否则就跑出非法参数异常， 然后直接创建了一个 长度为 initialCapacity的数组对象，并将该对象赋值给当前实例的 elementData属性，用以存放集合中元素 
  public ArrayList(int initialCapacity){
    super();
      if(initialCapacity<0){
            throw new IllegalArgumentException("Illegal Capacity initialCapacity")
      }
     this.elementData=new Object[initialCapacity];
    }

  public ArrayList(){ this{10}}
  构造一个默认为 10的空的集合

  再来看一个包含指定集合  中的所有元素的集合，该集合中元素的顺序是以  的迭代器返回元素的顺序
  public ArrayList(Collection<? extend E> c)
  { 
      elementData=c.toArray(); 
      size=elementData.length; 
      if(elementData.getClass!=Object[].class) {                  
         elementData=Arrays.copyof(elementData,size,Object[].class);
      }
   }

3、从上面的源码中看到是先将 c.toArray()方法返回赋值给 elementData，将大小赋值给 size，然后进行判断如果为 true，调用 Arras.copy方法创建一个新的 Object[]新数组，将 elementData 中元素 copy 到新 Object
数组中然后赋值给 elementData()

4、add()方法

插入对象 首先将 size+1，缠上一个 minCapacity的变量，调用 
  ensureCapacity（ minCapacity）
方法保证数组插入一个元素时有可用的容量，然后将元素 放到 elementData的 size位置，size+1
public boolean add(E e){ 
    ensureCapacity(size+1); 
    elementData[size++]=e;
    return true;
}

public void ensureCapacity(int minCapacity){ 
    modCount++;
    int oldCapacity=elementData.length; 
    if(minCapacity>oldCapacity){
        Object[] oldData=elementData;
        int newCapacity=(oldCapacity*3)/2+1; 
    if(newCapacity<minCapacity)
         newCapacity=minCapacity;
     elementData=Arrays.copy(elementData,newCapacity);
    }
}


必要时数组的扩容，首先将 
modCoun+1 modeCount
表示修改数组结构次数，如果传入的 minCapacity大于目前 elementData的容量则将容量扩展到     （oldCapacity*3）/2+1若此时容量仍然小于 minCapacity，直接将 minCapacity设置为最新的容量，
最后使用 Arrays的 copy方法到新的数组中 并将新数组赋值给 elementData.

在指定下表 index处插入 element首先判断下标 index 的参数是否有效，否则跑出异常，然后调用
ensureCapacity(size+1)要确保有足够容量来插入数据，然后调用 System.arraycopy 从 index 开始，将 
elementData 数组元素 copy到从 index+1 开始的地方，copy 的长度为 size-index,这样 index下标出的位置就空出来了，然后将元素 element 放到下标为 index处的位置，最后将 size++ 
public void add(int index,E element){
    if(index>size || index<0){
      throw new IndexOutOfBoundsException("Index"+index+",Size:"+size);
    }
    ensureCapacity(size+1);
    这一步是扩容 
  Systim.arraycopy(elementData,index,elementData,index+1,size-index);
  elementData[index]=element;
  size++;
}

5、删除方法

删除指定元素，分为两种情况， 若指定的元素为 null，则遍历当前的 elementData 数组，如果某一个下标 index的值为 null，则调用方法 fastRemove 删除元素， 如果指定的不为 null，则遍历 若某一个 index
下标处的元素和 o 进行 equals则快速删除元素 但是只能删除第一个出现的元素 快速删除是 将 index后面的元素往前复制一位 ，这样就达到删除的目的

image.png

6、查找方法

   查找非常简单，(这里不粘代码了 在下面和LinkedList对比起来看)

注意

 ArrayList是基于数组的方式实现的， 所以查找效率高，但是每次插入或者删除元素，都要大
量的移动元素，所以效率很低， 这里面主要涉及几个重要的方法 一个是减小数组的容量 就是讲当前数组的容量缩小为实际存储的容量trimToSize,还有一个就是扩容，如果容量不够，就设置新的容量为旧的容量的
1.5倍加1，因此建议能够事先确定元素数量的情况下用ArrayList（数组都是这样的特征）

LinkedList源码解析

LinkedList** 继承结构开始分析

public class LinkedList<E> extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList是一个继承于 AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列
列进行操作。
LinkedList实现 List接口，能对它进行队列操作。
LinkedList实现 Deque接口，双向队列它支持从两个端点方向检索和插入元素。
LinkedList实现了了Cloneable接口，即覆盖了了函数 clone()，能克隆
LinkedList实现 java.io.Serializable 接口，这意味着 LinkedList支持序列化，能通过序列化去传输。

LinkedList属性
关键字 transient 标识的字段的生命周期仅存于调用者的内存中而不不会写到磁盘里里持久化

 transient int size = 0;
  /**
    *Pointer to first node.
    *Invariant: (first == null && last == null) ||
    *           (first.prev == null && first.item != null)
  */
  transient Node<E> first;
  transient Node<E> last;

  LinkedList每个存储元素是 一个 Node对象

private static class Node<E> {

  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存储开销比 Arraylist大因为 LinkedList每个元素在内存里里多分配了了Node next; , Node prev;两个变量值得出ArrayList 和 
LinkedList 存储相同 大 小的数据LinkedList占内存 比较 大

LinkedList 构造方法

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

return addAll(size, c);开始分析.参数 1.添加位置 , 参数 2,需要添加的数据;

 public boolean addAll(int index, Collection<? extends E> c) { 
     checkPositionIndex(index);
     Object[] a = c.toArray();
     int numNew = a.length;
     if (numNew == 0)
       return false;
   上部分校验数据是否为0但是少了了空指针校验

   Node<E> pred, succ;
   if (index == size) {
     保存index处的节点。插 入位置如果是size，则在头结点前 面插 入，否则在获取
     index处的节点插 入succ = null;
     pred = last;
   } else {
     获取前 一个节点，插 入时需要修改这个节点的next引 用
     succ = node(index);
     pred = succ.prev;
   }
   可以理理解node摆放的位置
   for (Object o : a) {
   在强制类型转换的时候编译器 会给出警告@SuppressWarnings("unchecked")此注解去除警告
   @SuppressWarnings("unchecked") E e = (E) o;
   创建node参数1.node头参数2.数据参数3.node尾
   Node<E> newNode = new Node<>(pred, e, null);
   if (pred == null)
     first = newNode;
   else
    修改前 一节点的next指针
   pred.next = newNode;
   pred = newNode;
 }
   收尾的处理理
   if (succ == null) {
     last = pred;
   } else {
     pred.next = succ;
     succ.prev = pred;
   }
 size += numNew;
 modCount++;
 return true;
 }

LinkedList初始化操作会处理理一大坨的头尾地址转换ArrayList初始化操作会不不断的 copy数组为了了
Arrays.copyOf(elementData, size, Object[].class);

（说明这些东西原来在world上写的复制过来格式全部变了所以我就截图了）

LinkedList 添加元素

image.png
linkLast方法
image.png
linkBefore方法(按指定位置插)
image.png
LinkedList 添加又是处理理头--尾.地址转换
ArrayList 添加又会 copy 数组.为了了自增

image.png
LinkedList 删除元素

image.png
unlink方法
删除节点把节点的.所有属性指 null

image.png
LinkedList 删除元素.先把自己的东西给别人.然后自己指空.
ArrayList 删除元素.还是操作 Copy 数组
image.png
LinkedList 获取元素
image.png
node方法
image.png
LinkedList 获取元素.需要用循环找
ArrayList 获取元素直接 index 下标查找
image.png
上面的源码分析是对上一篇的线性表的一个扩展，因为ArrayList和LinkedList就是用的顺序存储结构和链式存储结构的，好了先到这里大家有什么疑问或者哪里写的不对可以指正。

数据结构和算法二（ArrayList和LinkedList源码解

ArrayList源码解析

LinkedList源码解析

猜你喜欢

热点阅读