数组与链表的比较：
数组通过下标访问的话是O(1) 数组一旦声明 长度就是固定的 数组的数据是物理逻辑均连续的 链表增删要快一些, 数组遍历快一些 长度一定的话， 数组的存储空间比链表要小
ArrayList：
ArrayList是List接口的实现类，它是支持根据需要而动态增长的数组；java中标准数组是定长的，在数组被创建之后，它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度，但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的。
扩容机制发生在add()方法调用的时候；
|
1 2 3 4 5 6 |
public boolean add(E e) { //扩容 ensureCapacityInternal(size + 1 ); // Increments modCount!! elementData[size++] = e; return true ; } |
该行代码ensureCapacityInternal()是用来扩用的，形参是最小扩容量，进入该方法后：
|
1 2 3 |
private void ensureCapacityInternal( int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } |
通过方法calculateCapacity(elementData, minCapacity)获取:
|
1 2 3 4 5 6 7 |
private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } |
使用 ensureExplicitCapacity方法可以判断是否需要扩容：
|
1 2 3 4 5 6 7 |
private void ensureExplicitCapacity( int minCapacity) { modCount++; // 如果最小需要空间比elementData的内存空间要大，则需要扩容 if (minCapacity - elementData.length > 0 ) //扩容 grow(minCapacity); } |
需要扩容，进入ArrayList扩容的关键方法grow():扩大为原来的1.5倍；
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
private void grow( int minCapacity) { // 获取到ArrayList中elementData数组的内存空间长度 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); // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间 // 并将elementData的数据复制到新的内存空间 elementData = Arrays.copyOf(elementData, newCapacity); } 复制代码 |
至此得出ArrayList扩容的本质是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。
LinkedList：
链表实现扩容，直接在尾指针后面加入新的元素即可。
实现LinkedList:LinkedList的底层实现是链表。更深理解是一个双向链表。
节点代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//节点 public class Node { Node previous; //前继，指向前一个Node Object data; //节点数据 Node next; //后继，指向后一个Node public Node() { } public Node(Node previous, Object data, Node next) { super (); this .previous = previous; this .data = data; this .next = next; } } |
初始化MyLinkedList:
|
1 2 3 4 5 6 7 8 9 10 |
public class MyLinkedList { private Node first; //首节点 private Node last; //尾节点 private int size; //链表大小 public MyLinkedList() { first = null ; last = null ; size = 0 ; } } |
尾部添加，实现add(Object obj)方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public void add(Object obj){ Node node = new Node( null , null , null ); if (first== null ){ //first=null,说明LinkedList中没有一个节点 node.data = obj; first = node; last = node; //第一个节点和最后一个节点都是node size++; } else { node.data = obj; last.next = node; //和最后一个连接起来 node.previous = last; last = node; //当前节点变为末尾节点 size++; } |
现get(int index)方法，获取index处的节点并返回Node:
使用循环，遍历链表：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public Node get( int index) { RangeCheck(index); Node temp = null ; if (index < (size>> 1 )){ //改进的遍历方法，右移运算符的巧用 temp = first; for ( int i= 0 ;i<index;i++){ temp = temp.next; } } else { temp = last; for ( int i=size- 1 ;i>index;i--){ temp = temp.previous; } } return temp; } |
任意位置插入，实现add(int index,Object obj)方法：插入的步骤注意顺序，不要产生断链。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public void add( int index,Object obj) { RangeCheck(index); //对传入的索引必须进行检查，判断是否越界 Node node = new Node( null , null , null ); node.data = obj; Node node2=first; for ( int i= 0 ;i<index- 1 ;i++){ node2 = node2.next; } node.next = node2.next; node2.next.previous=node; node2.next = node; node.previous=node2; size++; } |
RangeCheck():
|
1 2 3 4 5 |
private void RangeCheck( int index) { if (index< 0 ||index >= size){ throw new IndexOutOfBoundsException( "IndexOutOfBounds" +index); //不合法则抛出异常 } } |
实现remove(Object obj)方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public boolean remove(Object obj) { Node node = first; if (obj== null ){ while (node!= null ){ if (node.data== null ){ removefast(node); return true ; } node = node.next; } } else { while (node!= null ){ if (obj.equals(node.data)){ removefast(node); return true ; } node = node.next; } } return false ; } private void removefast(Node node){ node.previous.next=node.next; size--; node.data= null ; node.previous = node.next = null ; } |
实现set(int index,Object obj)方法：
|
1 2 3 4 5 6 |
public Object set( int index,Object obj) { Node node = get(index); Object oldObject=node.data; node.data = obj; return oldObject; } |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！
原文链接：https://blog.csdn.net/qq_40604313/article/details/118683783