集合实现类研究底层（部分）：手撕ArrayList底层源码、手撕LinkedList底层源码、手写单向链表和双向链表

day26上

集合框架图

���绿已经学习底层，深入底层主要是研究实现类底层

继承关系图

手撕ArrayList底层源码

ps:研究添加元素的过程

思路：

1.研究继承关系

2.研究属性

3.理解创建集合的过程 – 构造方法的底层原理

4.研究添加元素的过程

提升：

1.研究删除集合的过程

2.研究遍历集合的过程

场景//ArrayList list = new ArrayList();ArrayList list = new ArrayList(10000);list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");

底层

public abstract class AbstractList extends AbstractCollection implements List {    //回顾：其中抽象类的构造方法由子类调用        //外部操作数（记录添加和删除的次数）    protected transient int modCount = 0;//最终4}

额外补充：    //空数据，没有对象，输出长度为空指针异常    private static final Object[] EMPTY_ELEMENTDATA = null;        //空内容的数组，有对象，输出长度为0    private static final Object[] EMPTY_ELEMENTDATA = {};    //默认容量的空内容的数组，有对象，（后面两个对象不同）private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    

public class ArrayList extends AbstractList implements List{    //默认初始化容量    private static final int DEFAULT_CAPACITY = 10;    //空内容的数组    private static final Object[] EMPTY_ELEMENTDATA = {};    //默认容量的空内容的数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    //数据容器最大容量    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;        //数据容器 - [“aaa”,"bbb","ccc","ddd",null,null,null,null,null,null]    transient Object[] elementData;//new Object[10];    //元素个数    private int size;//最终4        //无参构造，默认容量的空内容的数组    public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }    //有参构造，初始化容量    //initialCapacity - 10000    public ArrayList(int initialCapacity) {        if (initialCapacity > 0) {            this.elementData = new Object[initialCapacity];        } else if (initialCapacity == 0) {            this.elementData = EMPTY_ELEMENTDATA;        } else {            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);        }    }        //e - 最终"ddd"    public boolean add(E e) {        ensureCapacityInternal(size + 1);        elementData[size++] = e;//添加一个元素size+1        return true;    }        //minCapacity - 10--11（超）    private void ensureCapacityInternal(int minCapacity) {        //使用无参构造创建ArrayList，第一次添加元素时进入的判断        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {            //minCapacity =  Math.max(10, 1);            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);        }        ensureExplicitCapacity(minCapacity);    }        //minCapacity - 10--11（超）    private void ensureExplicitCapacity(int minCapacity) {        modCount++;        // 有溢出意识的代码（准备扩容的长度必须大于数据容器的长度）        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }        //minCapacity - 10--11（超）    private void grow(int minCapacity) {        // oldCapacity - 10        int oldCapacity = elementData.length;        // newCapacity - 15，超过默认容量，开始扩容        int newCapacity = oldCapacity + (oldCapacity >> 1);//ArrayList的扩容机制（1.5倍）        if (newCapacity - minCapacity  0)            newCapacity = hugeCapacity(minCapacity);                elementData = Arrays.copyOf(elementData, newCapacity);    }    //内存中一般不会存很多数据，一般几万都很多了，后面会讲解大量数据的处理情况    //其他地方调用，minCapacity可能为负    private static int hugeCapacity(int minCapacity) {        if (minCapacity  0        return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;    }    }

面试题

ArrayList的数据结构是什么？

Object类型的一维数组

ArrayList默认初始化容量是多少？

10

ArrayList最大容量是多少？

Integer.MAX_VALUE-8

ArrayList最大容量为什么是Integer.MAX_VALUE-8？

减8是为了腾出空间存放数组的头部信息

ArrayList扩容机制是什么？

扩容后的长度是原来长度的1.5倍

如何减少集合的伸缩性及其目的是什么？

根据需求判断元素大概的长度，在创建集合时指定长度，减少扩容次数，提高效率

手撕LinkedList底层源码

ps:研究添加元素的过程

思路：

1.研究继承关系

2.研究属性

3.理解创建集合的过程 – 构造方法的底层原理

4.研究添加元素的过程

提升：

1.研究删除集合的过程

2.研究遍历集合的过程

场景：    LinkedList list = new LinkedList();list.add("小小");list.add("奇男子");list.add("大大");

底层

public abstract class AbstractList extends AbstractCollection implements List {    //外部操作数（记录添加和删除的次数）    protected transient int modCount = 0;//0}

public abstract class AbstractSequentialList extends AbstractList {}

public class LinkedList extends AbstractSequentialList implements List{    //元素个数    transient int size = 0;//0    //首节点    transient Node first;//null//尾节点    transient Node last;//null        public LinkedList() {    }//new对象，系统赋默认值        //添加在inkLast()，所以研究linkLast()    public boolean add(E e) {        linkLast(e);        return true;    }        void linkLast(E e) {        final Node l = last;        final Node newNode = new Node(l, e, null);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;        size++;        modCount++;    }        //回顾：静态内部类应用场景（此处不需要调用外部类的成员属性）    //节点类    private static class Node {        E item; ------------ 元素        Node next; ------ 下一个节点的地址        Node prev; ------ 上一个节点的地址        Node(Node prev, E element, Node next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }    }

节点对象理解图

补充：双向链表【站在数据结构的角度：结点】【站在java底层的角度：节点】

LinkedList理解图

添加过程解析

第一次添加：

LinkLast（）

1.首先e-小小，l = last为null

2.newNode对象（l，e，null）找到第一个节；所以第一个节点为【0x001】

3.然后last =newNode【0x001】

4.然后判断条件，first = newNode【0x001】

5.然后size++，变成1；modCount++变成1

第二次添加：

重新LinkLast（）

e；l；newNode重新赋值

1.首先e-奇男子，l = last为0x001（上一个节点地址即赋值给下一个首节点，第二个节点的首节点可以找到上一个节点）

2.newNode对象（l，e，null）找到第二个节；所以第二个节点为【0x002】；

3.然后last =newNode【0x002】

4.然后判断条件，l.next = newNode【0x002】（下一个节点地址即赋值给上一个尾节点，上一个节点可以找到下一个节点）

5.然后size++，变成2；modCount++变成2

第三次添加：

重新LinkLast（）

e；l；newNode重新赋值

1.首先e-奇男子，l = last为0x002（上一个节点地址即赋值给下一个首节点，第二个节点的首节点可以找到上一个节点）

2.newNode对象（l，e，null）找到第二个节；所以第二个节点为【0x003】；

3.然后last =newNode【0x003】

4.然后判断条件，l.next = newNode【0x003】（下一个节点地址即赋值给上一个尾节点，上一个节点可以找到下一个节点）

5.然后size++，变成3；modCount++变成3

面试题

LinkedList底层数据结构是什么？

双向链表

ArrayList 和 LinkedList的效率区别：

​ ArrayList底层：一维数组

​ LinkedList底层：双向链表

​ 添加数据 – ArrayList扩容的情况：LinkedList快

​ 添加数据 – ArrayList不扩容的情况：ArrayList快（size指针指哪里添加到哪里）

​ 查询数据：ArrayList快（ArrayList下标查找，LinkedList需要遍历数据 ）

​ 删除数据：LinkedList快（ArrayList删除要往前移动元素，LinkedList删除只要断链接添链接）

​ 修改数据：ArrayList快（修改需要先查询）

补充：平时我们一般使用ArrayList，是因为众多业务中查询功能使用最为频繁，而ArrayList查询功能比LinkedList更快，所以我们选择使用ArrayList会更多

LinkedList如何实现删除？

​ 1.通过下标找到要删除的节点

​ 2.把要删除的节点的下一个节点地址赋值给上一个节点的next

​ 3.把要删除的节点的上一个节点地址赋值给下一个节点的prev

手写单向链表和双向链表

手写单向链表

简单实现

粗略思路：

节点（元素，下一个节点，有参构造）

首节点，尾节点，size

添加（new节点，判断赋值给节点相应位置）

遍历 迭代器 方法实现（仿写底层）判断有没有元素，获取下一个元素

public class UnidirectionalLinkedList {private Node first;private Node last;private int size;public void add(E e){Node node = new Node(e, null);if(first == null){first = node;}else{last.next = node;}last = node;size++;}public Iterator iterator(){return new Itr();}public class Itr implements Iterator{private int cursor;private Node node = first;@Overridepublic boolean hasNext() {return cursor != size;}@Overridepublic E next() {E item = node.item;node = node.next;cursor++;return item;}}public static class Node{E item;Node next;public Node(E item, Node next) {this.item = item;this.next = next;}}}public class Test01 {public static void main(String[] args) {UnidirectionalLinkedList list = new UnidirectionalLinkedList();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("eee");Iterator it = list.iterator();while(it.hasNext()){String element = it.next();System.out.println(element);}}}

手写双向链表

简单实现

粗略思路：

节点（上一个节点，元素，下一个节点，有参构造）

首节点，尾节点，size

添加（获取上一个节点，new节点，判断赋值给节点相应位置）

遍历 迭代器 方法实现（仿写底层）判断有没有元素，获取下一个元素

package com.qf.bidirectional_linked_list;import java.util.Iterator;public class BidirectionalLinkedList {private Node first;private Node last;private int size;public void add(E e){Node l = last;Node node = new Node(l,e, null);if(first == null){first = node;}else{last.next = node;}last = node;size++;}public Node getLast() {return last;}public Iterator iterator(){return new Itr();}public class Itr implements Iterator{private int cursor;private Node node = first;@Overridepublic boolean hasNext() {return cursor != size;}@Overridepublic E next() {E item = node.item;node = node.next;cursor++;return item;}}public static class Node{Node prev;E item;Node next;public Node(Node prev,E item, Node next) {this.prev = prev;this.item = item;this.next = next;}}}public class Test01 {public static void main(String[] args) {BidirectionalLinkedList list = new BidirectionalLinkedList();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("eee");//正序遍历Iterator it = list.iterator();while(it.hasNext()){String element = it.next();System.out.println(element);}System.out.println("-----------------------");//倒序遍历Node node = list.getLast();while(node != null){System.out.println(node.item);node = node.prev;}}}

总结

手撕实现类

1.手撕ArrayList底层源码

2.手撕LinkedList底层源码

ArrayList 和 LinkedList的效率区别

手写单向链表

手写双向链表