java基礎(chǔ)-數(shù)組擴容詳解
更新時間：2021年08月20日 16:40:03 作者：haijiao12138
這篇文章主要介紹了Java數(shù)組擴容實現(xiàn)方法解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
數(shù)組與鏈表的比較：
- 數(shù)組通過下標(biāo)訪問的話是O(1)
- 數(shù)組一旦聲明 長度就是固定的
- 數(shù)組的數(shù)據(jù)是物理邏輯均連續(xù)的
- 鏈表增刪要快一些, 數(shù)組遍歷快一些
- 長度一定的話， 數(shù)組的存儲空間比鏈表要小
ArrayList：
ArrayList是List接口的實現(xiàn)類，它是支持根據(jù)需要而動態(tài)增長的數(shù)組；java中標(biāo)準(zhǔn)數(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()是用來擴用的，形參是最小擴容量，進(jìn)入該方法后：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
通過方法calculateCapacity(elementData, minCapacity)獲取:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果傳入的是個空數(shù)組則最小容量取默認(rèn)容量與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);
}
需要擴容，進(jìn)入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è)值大于默認(rèn)的最大值檢查是否溢出
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;//當(dāng)前節(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)){//改進(jìn)的遍歷方法，右移運算符的巧用
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);//對傳入的索引必須進(jìn)行檢查，判斷是否越界
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)文章
本文主要介紹了MyBatis實現(xiàn)注冊及獲取Mapper，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-03-03
關(guān)于Java8新特性O(shè)ptional類的詳細(xì)解讀
Optional類是一個容器類，它可以保存類型T的值，代表這個值存在?；蛘邇H僅保存null，表示這個值不存在,原來用 null 表示一個值不存在，現(xiàn)在Optional 可以更好的表達(dá)這個概念。并且可以避免空指針異常,需要的朋友可以參考下2023-05-05
都說經(jīng)典的就是好的，這句話放在Java的ThreadPoolExecutor上那是一點都沒錯，像現(xiàn)在數(shù)據(jù)庫連接的池化實現(xiàn)，或者像Tomcat這種WEB服務(wù)器的線程管理，處處都有著ThreadPoolExecutor的影子，本篇文章將結(jié)合源碼實現(xiàn)，對ThreadPoolExecutor的原理進(jìn)行一個深入學(xué)習(xí)2023-06-06
詳解Java中String,StringBuffer和StringBuilder的使用
這篇文章主要為大家詳細(xì)介紹了Java中String,StringBuffer和StringBuilder三者的區(qū)別以及使用，文中的少了講解詳細(xì)，感興趣的可以了解一下2022-07-07
這篇文章主要介紹了Java漏桶算法的簡單代碼實例,漏桶算法的意義在于能夠平滑請求,不給下游服務(wù)造成過大壓力,特別適用于突發(fā)流量或者定時任務(wù)拉取大量數(shù)據(jù)時,需要處理大量數(shù)據(jù)或者請求的場景,需要的朋友可以參考下2024-01-01
這篇文章主要討論了在Java中如何訪問或修改類的私有字段,包括使用公共的getter和setter方法、反射、繼承和序列化機制,文章強調(diào)了尊重類的封裝性,感興趣的小伙伴跟著小編一起來看看吧2025-02-02
這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)簡單連連看游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了SpringBoot中Mybatis注解多對多查詢的實現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
Java利用Socket和IO流實現(xiàn)文件的上傳與下載
本文主要介紹了Java利用Socket和IO流實現(xiàn)文件的上傳與下載，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-04-04
本文主要介紹了如何在不升級電腦配置的情況下通過修改IntelliJIDEA的設(shè)置來優(yōu)化其性能,從而提升開發(fā)效率2024-12-12