day26上

集合框架图

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

继承关系图

手撕ArrayList底层源码

ps:研究添加元素的过程

思路：

1.研究继承关系

2.研究属性

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

4.研究添加元素的过程

提升：

1.研究删除集合的过程

2.研究遍历集合的过程

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

底层

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

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

public class ArrayList<E> extends AbstractList<E> implements List<E>{//默认初始化容量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 - 10000public 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+1return 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 - 10int oldCapacity = elementData.length;// newCapacity - 15，超过默认容量，开始扩容int newCapacity = oldCapacity + (oldCapacity >> 1);//ArrayList的扩容机制（1.5倍）if (newCapacity - minCapacity < 0)//newCapacity-10，没有超过默认容量newCapacity = minCapacity;//当超过最大容量Integer.MAX_VALUE-8if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}//内存中一般不会存很多数据，一般几万都很多了，后面会讲解大量数据的处理情况//其他地方调用，minCapacity可能为负private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();//minCapacity > 0return (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<String> list = new LinkedList<>();list.add("小小");list.add("奇男子");list.add("大大");

底层

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

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
}

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

节点对象理解图

补充：双向链表【站在数据结构的角度：结点】【站在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<E> {private Node<E> first;private Node<E> last;private int size;public void add(E e){Node<E> node = new Node<>(e, null);if(first == null){first = node;}else{last.next = node;}last = node;size++;}public Iterator<E> iterator(){return new Itr();}public class Itr implements Iterator<E>{private int cursor;private Node<E> 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>{E item;Node<E> next;public Node(E item, Node<E> next) {this.item = item;this.next = next;}}}public class Test01 {public static void main(String[] args) {UnidirectionalLinkedList<String> list = new UnidirectionalLinkedList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("eee");Iterator<String> 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<E> {private Node<E> first;private Node<E> last;private int size;public void add(E e){Node<E> l = last;Node<E> node = new Node<>(l,e, null);if(first == null){first = node;}else{last.next = node;}last = node;size++;}public Node<E> getLast() {return last;}public Iterator<E> iterator(){return new Itr();}public class Itr implements Iterator<E>{private int cursor;private Node<E> 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>{Node<E> prev;E item;Node<E> next;public Node(Node<E> prev,E item, Node<E> next) {this.prev = prev;this.item = item;this.next = next;}}}public class Test01 {public static void main(String[] args) {BidirectionalLinkedList<String> list = new BidirectionalLinkedList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");list.add("eee");//正序遍历Iterator<String> it = list.iterator();while(it.hasNext()){String element = it.next();System.out.println(element);}System.out.println("-----------------------");//倒序遍历Node<String> node = list.getLast();while(node != null){System.out.println(node.item);node = node.prev;}}
}

总结

手撕实现类

1.手撕ArrayList底层源码
2.手撕LinkedList底层源码
ArrayList 和 LinkedList的效率区别
手写单向链表
手写双向链表