java基礎(chǔ)-數(shù)組擴容詳解
更新時間：2021年08月20日 16:40:03 作者：haijiao12138
這篇文章主要介紹了Java數(shù)組擴容實現(xiàn)方法解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
數(shù)組與鏈表的比較：
- 數(shù)組通過下標訪問的話是O(1)
- 數(shù)組一旦聲明 長度就是固定的
- 數(shù)組的數(shù)據(jù)是物理邏輯均連續(xù)的
- 鏈表增刪要快一些, 數(shù)組遍歷快一些
- 長度一定的話， 數(shù)組的存儲空間比鏈表要小
ArrayList：
ArrayList是List接口的實現(xiàn)類，它是支持根據(jù)需要而動態(tài)增長的數(shù)組；java中標準數(shù)組是定長的，在數(shù)組被創(chuàng)建之后，它們不能被加長或縮短。這就意味著在創(chuàng)建數(shù)組時需要知道數(shù)組的所需長度，但有時我們需要動態(tài)程序中獲取數(shù)組長度。ArrayList就是為此而生的。
擴容機制發(fā)生在add()方法調(diào)用的時候；
public boolean add(E e) {
//擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
該行代碼ensureCapacityInternal()是用來擴用的，形參是最小擴容量，進入該方法后：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
通過方法calculateCapacity(elementData, minCapacity)獲取:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果傳入的是個空數(shù)組則最小容量取默認容量與minCapacity之間的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
使用 ensureExplicitCapacity方法可以判斷是否需要擴容：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果最小需要空間比elementData的內(nèi)存空間要大，則需要擴容
if (minCapacity - elementData.length > 0)
//擴容
grow(minCapacity);
}
需要擴容，進入ArrayList擴容的關(guān)鍵方法grow():擴大為原來的1.5倍；
private void grow(int minCapacity) {
// 獲取到ArrayList中elementData數(shù)組的內(nèi)存空間長度
int oldCapacity = elementData.length;
// 擴容至原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 再判斷一下新數(shù)組的容量夠不夠，夠了就直接使用這個長度創(chuàng)建新數(shù)組，
// 不夠就將數(shù)組長度設(shè)置為需要的長度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若預(yù)設(shè)值大于默認的最大值檢查是否溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 調(diào)用Arrays.copyOf方法將elementData數(shù)組指向新的內(nèi)存空間時newCapacity的連續(xù)空間
// 并將elementData的數(shù)據(jù)復(fù)制到新的內(nèi)存空間
elementData = Arrays.copyOf(elementData, newCapacity);
}
復(fù)制代碼
至此得出ArrayList擴容的本質(zhì)是計算出新的擴容數(shù)組的size后實例化，并將原有數(shù)組內(nèi)容復(fù)制到新數(shù)組中去。
LinkedList：
鏈表實現(xiàn)擴容，直接在尾指針后面加入新的元素即可。
實現(xiàn)LinkedList:LinkedList的底層實現(xiàn)是鏈表。更深理解是一個雙向鏈表。
節(jié)點代碼：
//節(jié)點
public class Node {
Node previous;//前繼，指向前一個Node
Object data;//節(jié)點數(shù)據(jù)
Node next;//后繼，指向后一個Node
public Node() {
}
public Node(Node previous, Object data, Node next) {
super();
this.previous = previous;
this.data = data;
this.next = next;
}
}
初始化MyLinkedList:
public class MyLinkedList {
private Node first;//首節(jié)點
private Node last;//尾節(jié)點
private int size;//鏈表大小
public MyLinkedList() {
first = null;
last = null;
size = 0;
}
}
尾部添加，實現(xiàn)add(Object obj)方法：
public void add(Object obj){
Node node = new Node(null,null,null);
if(first==null){//first=null,說明LinkedList中沒有一個節(jié)點
node.data = obj;
first = node;
last = node;//第一個節(jié)點和最后一個節(jié)點都是node
size++;
}else{
node.data = obj;
last.next = node;//和最后一個連接起來
node.previous = last;
last = node;//當前節(jié)點變?yōu)槟┪补?jié)點
size++;
}
現(xiàn)get(int index)方法，獲取index處的節(jié)點并返回Node:
使用循環(huán)，遍歷鏈表：
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;
}
任意位置插入，實現(xiàn)add(int index,Object obj)方法：插入的步驟注意順序，不要產(chǎn)生斷鏈。
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():
private void RangeCheck(int index) {
if(index<0||index >= size){
throw new IndexOutOfBoundsException("IndexOutOfBounds"+index);//不合法則拋出異常
}
}
實現(xiàn)remove(Object obj)方法：
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;
}
實現(xiàn)set(int index,Object obj)方法：
public Object set(int index,Object obj) {
Node node = get(index);
Object oldObject=node.data;
node.data = obj;
return oldObject;
}
總結(jié)
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
教您如何3分鐘快速搞定EasyExcel導(dǎo)入與導(dǎo)出功能
對于EasyExcel庫,我們可以使用它來實現(xiàn)數(shù)據(jù)的導(dǎo)入和導(dǎo)出,下面這篇文章主要給大家介紹了關(guān)于如何3分鐘快速搞定EasyExcel導(dǎo)入與導(dǎo)出功能的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01
null是沒有地址,""是有地址但是里面的內(nèi)容是空的,好比做飯 null說明連鍋都沒有 而""則是有鍋沒米,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，下面我們來詳細學習一下它吧2019-06-06
Mybatis-plus和Mybatis出現(xiàn)版本不兼容的問題解決
MyBatis-Plus?與?MyBatis?之間的兼容性問題通常是由于版本不匹配引起的,本文主要介紹了Mybatis-plus和Mybatis出現(xiàn)版本不兼容的問題解決,具有一定的參考價值,感興趣的可以了解一下2024-08-08
這篇文章主要介紹了Java 自定義注解的相關(guān)資料，幫助大家更好的理解和學習使用Java，感興趣的朋友可以了解下2021-03-03
springboot集成普羅米修斯(Prometheus)的方法
這篇文章主要介紹了springboot集成普羅米修斯(Prometheus)的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
這篇文章主要介紹了Java 模擬cookie登陸簡單操作,結(jié)合實例形式分析了Java 模擬cookie登陸的相關(guān)原理與基本實現(xiàn)技巧,需要的朋友可以參考下2020-03-03
簡單幾步實現(xiàn)將Spring security4.x升級到5.x
這篇文章主要介紹了簡單幾步實現(xiàn)將Spring security4.x升級到5.x方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
Java設(shè)計模式之訪問模式（Visitor者模式）介紹
這篇文章主要介紹了Java設(shè)計模式之訪問模式（Visitor者模式）介紹,本文講解了為何使用Visitor模式、如何使用Visitor模式、使用Visitor模式的前提等內(nèi)容,需要的朋友可以參考下2015-03-03
使用maven開發(fā)springboot項目時pom.xml常用配置(推薦)
這篇文章主要介紹了使用maven開發(fā)springboot項目時的pom.xml常用配置,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
這篇文章主要介紹了Java SpringBoot攔截器的使用方法詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2021-10-10