java數(shù)組如何實(shí)現(xiàn)ArrayList的動態(tài)擴(kuò)容

發(fā)布時(shí)間：2020-06-22 16:58:25 來源：億速云閱讀：201 作者：清晨欄目：開發(fā)技術(shù)

這篇文章將為大家詳細(xì)講解有關(guān)java數(shù)組如何實(shí)現(xiàn)ArrayList的動態(tài)擴(kuò)容，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

提到數(shù)組大家肯定不會陌生，但我們也知道數(shù)組有個(gè)缺點(diǎn)就是在創(chuàng)建時(shí)就確定了長度，之后就不能更改長度。所以Java官方向我們提供了ArrayList這個(gè)可變長的容器。其實(shí)ArrayList底層也是用數(shù)組進(jìn)行實(shí)現(xiàn)的，具體內(nèi)容如下：

一、整體框架

廢話不多說，我們以存放int類型元素為例，看一下ArrayList需要的成員變量和需要實(shí)現(xiàn)的方法。

public class ArrayList
 private int size;//用來記錄實(shí)際存儲元素個(gè)數(shù)
  private int[] elements;//用來存儲元素的數(shù)組
  
  //構(gòu)造方法：在創(chuàng)建ArrayList對象時(shí)，初始化elements數(shù)組
  public ArrayList(int capacity){
    elements = new int[capacity];
  }
 
 
 /**
 * 元素的數(shù)量
 * @return
 */
 public int size() {}
 /**
 * 是否為空
 * @return
 */
 public boolean isEmpty() {}
 /**
 * 查看元素的索引
 * @param element
 * @return
 */
 public int indexOf(int element) {}
 /**
 * 是否包含元素
 * @param element
 * @return
 */
 public boolean contains(int element) {}
 /**
 * 獲取index位置的元素
 * @param index
 * @return
 */
 public int get(int index) {}
 /**
 * 設(shè)置index位置的元素
 * @param index
 * @param element
 * @return 原來的元素
 */
 public int set(int index, int element) {}
 /**
 * 在index索引位置插入元素
 * @param index
 * @param element
 */
 public void add(int index, int element) {}
 /**
 * 添加元素到尾部
 * @param element
 */
 public void add(int element) {}
 /**
 * 刪除index位置的元素
 * @param index
 * @return
 */
 public int remove(int index) {}
 /**
 * 清除所有元素
 */
 public void clear() {}
 /**
 * 用來打印列表
 */
 public String toString() {}
  
}

二、方法實(shí)現(xiàn)

框架我們已經(jīng)有了，接下來我們一步步實(shí)現(xiàn)方法就行。

size()方法：

這個(gè)方法很簡單，因?yàn)槲覀冇衧ize屬性，直接將其返回就行了。

public int size() {
 return size;
}

isEmpty()方法：

這個(gè)方法也很簡單，判斷是否為空只需要判斷size是否為0即可。

public boolean isEmpty() {
 return size == 0;
}

indexOf(int element)方法：

這個(gè)方法是用來查詢元素的所在索引位置，并返回。我們通過遍歷列表查找即可，找到就將元素返回，沒有找到返回-1。

public int indexOf(int element) {
  
 for (int i = 0; i < size; i++) {
 if (element.equals(elements[i])) {
  return i;
 } 
 return -1; 
  
}

contains(int element)方法：

這個(gè)方法是用來查看所傳元素是否在數(shù)組中，我們可以直接通過indexOf()方法查看返回值是否不等于-1，不等于-1返回true，等于-1返回false。

public boolean contains(int element) {
 return indexOf(element) != -1;
}

get(int index)方法：

這個(gè)方法用來獲取指定索引位置的元素，我們直接返回?cái)?shù)組的指定索引位置元素即可。

public int get(int index) {;
 return elements[index];
}

set(int index, int element)方法:

這個(gè)方法用來將指定索引位置元素改為指定元素，并將原來元素返回，我們通過數(shù)組索引獲取到該位置元素，并將指定元素賦值給該位置索引并將原來元素返回。

public int set(int index, int element) {
 int old = elements[index];
 elements[index] = element;
 return old;
}

add(int index, int element)方法：

個(gè)方法是在指定索引位置插入指定元素，我們首先將指定索引位置的元素以及之后所有的元素向后移動一位，然后再將指定元素賦值給數(shù)組的指定索引位置，最后并將size加1。

public void add(int index, int element) {

 for (int i = size; i > index; i--) {
 elements[i] = elements[i - 1];
 }
 elements[index] = element;
 size++;
 
}

add(int element)方法：

這個(gè)方法是在數(shù)組尾部添加元素，我們直接調(diào)用add(int index, int element)方法，將size作為index的參數(shù)傳入即可。

public void add(int element) {
 add(size, element);
}

remove(int index)方法：

這個(gè)方法用來刪除指定索引位置的元素，并將要?jiǎng)h除元素返回，我們首先通過指定索引獲取原來元素，當(dāng)刪除該元素后需要將index索引后面的所有元素向前移動一位，最后將size減1。

public int remove(int index) {
 int old = elements[index];
 for (int i = index + 1; i < size; i++) {
 elements[i - 1] = elements[i]; 
 }
 size--; 
 
 return old;
}

clear()方法：

這個(gè)方法，用于清空數(shù)組中所有元素，我們只需要將size賦值為0即可。

public void clear() {

 size = 0;
}

toString()方法：

這個(gè)方法用于將所有元素打印出來，通過StringBuilder對象進(jìn)行拼接，最后轉(zhuǎn)成字符串返回即可。

public String toString() {
 
 StringBuilder string = new StringBuilder();
 string.append("size=").append(size).append(", [");
 
 for (int i = 0; i < size; i++) {
  
 if (i != 0) {
  string.append(", ");
 }
 string.append(elements[i]);
 }
 
 
 string.append("]");
 return string.toString();
}

以上代碼基本實(shí)現(xiàn)了對數(shù)組的進(jìn)行數(shù)據(jù)的增刪改查，但最后想達(dá)到我們的目的還要進(jìn)一步優(yōu)化。

三、優(yōu)化

1.實(shí)現(xiàn)動態(tài)擴(kuò)容

當(dāng)我們向數(shù)組中添加元素時(shí)，如果數(shù)組已經(jīng)滿了我們就需要就數(shù)組進(jìn)行動態(tài)擴(kuò)容。擴(kuò)容的原理并不是真的對原數(shù)組進(jìn)行增加內(nèi)存操作，而是重新創(chuàng)建一個(gè)更大的數(shù)組，并將原數(shù)組的元素賦給新的數(shù)組。我們聲明一個(gè)私有方法確保添加元素前數(shù)組的容量足夠。

private void ensureCapacity(int capacity) {
 int oldCapacity = elements.length;
 if (oldCapacity >= capacity) return;
 
 // 新容量為舊容量的1.5倍
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 int[] newElements = new int[newCapacity];
 for (int i = 0; i < size; i++) {
 newElements[i] = elements[i];
 }
 elements = newElements;

}

我們在add()方法中首先調(diào)用ensureCapacity(int capacity)方法進(jìn)行判斷數(shù)組容量是否足夠，不夠進(jìn)行擴(kuò)容。

public void add(int index, E element) {
 
 ensureCapacity(size + 1);
 
 for (int i = size; i > index; i--) {
 elements[i] = elements[i - 1];
 }
 elements[index] = element;
 size++;
}

2. 確保索引不越界

當(dāng)我們在調(diào)用傳入索引的方法時(shí)，首先要保證傳入索引在可用范圍內(nèi)，不然會出現(xiàn)角標(biāo)越界的異常。
定義outOfBound()方法，用于拋出角標(biāo)越界異常信息。

private void outOfBounds(int index) {
 throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

定義rangeCheck()方法用于檢查索引是否越界，如果越界，調(diào)用outOfBound()拋出異常。

private void rangeCheck(int index) {
 if (index < 0 || index >= size) {
 outOfBounds(index);
 }
}

而對于調(diào)用add()方法時(shí)所傳入的索引范圍可以取到size位置，我們在定義一個(gè)rangeCheckForAdd()方法，用于檢查調(diào)用add()方法時(shí)索引是否越界。

private void rangeCheckForAdd(int index) {
 if (index < 0 || index > size) {
 outOfBounds(index);
 }
}

在get()方法，set()方法和remove()方法中，先調(diào)用rangeCheck()方法，檢查傳入索引是否越界。

public int get(int index) {
 rangeCheck(index);
 return elements[index];
}

public int set(int index, E element) {
 rangeCheck(index);
 
 int old = elements[index];
 elements[index] = element;
 return old;
}

public int remove(int index) {
 rangeCheck(index);
 
 int old = elements[index];
 for (int i = index + 1; i < size; i++) {
 elements[i - 1] = elements[i];
 }
 size--;
 return old;
}

3. 設(shè)置常量以及重寫構(gòu)造方法

對于類中的常數(shù)我們更希望封裝成常量，并且聲明一個(gè)默認(rèn)容量，希望在創(chuàng)建對象時(shí)未傳入容量參數(shù)或傳入容量參數(shù)過小直接創(chuàng)建一個(gè)相對大小合適的數(shù)組。

private static final int DEFAULT_CAPACITY = 10;//我們將默認(rèn)容量設(shè)為10
private static final int ELEMENT_NOT_FOUND = -1;//我們將獲取指定元素的索引時(shí)，未找到的返回值-1封裝為常量

//聲明無參構(gòu)造方法，在調(diào)用無參構(gòu)造方法是直接創(chuàng)建默認(rèn)容量的數(shù)組
public ArrayList(){
  elements = new int[DEFAULT_CAPACITY];
}

//聲明有參構(gòu)造方法，在傳入?yún)?shù)小于默認(rèn)容量時(shí)，我們?nèi)匀粍?chuàng)建默認(rèn)容量數(shù)組
public ArrayList(int capaticy) {
 capaticy = (capaticy < DEFAULT_CAPACITY) &#63; DEFAULT_CAPACITY : capaticy;
 elements = new int[capaticy];
}

四、使用泛型

以上步驟已經(jīng)使用數(shù)組完全實(shí)現(xiàn)了ArrayList的全部功能，但只能存放int類型的數(shù)據(jù)，如果我們希望儲存其他類型的數(shù)據(jù)我們只需要使用Java中的泛型就能夠完成。

思路與上述完全一樣，整體代碼如下：

public class ArrayList<E> {
 /**
 * 元素的數(shù)量
 */
 private int size;
 /**
 * 所有的元素
 */
 private E[] elements;
 
 private static final int DEFAULT_CAPACITY = 10;
 private static final int ELEMENT_NOT_FOUND = -1;
 
 public ArrayList() {
 elements = (E[]) new Object[DEFAULT_CAPACITY];
 }
 
 public ArrayList(int capaticy) {
 capaticy = (capaticy < DEFAULT_CAPACITY) &#63; DEFAULT_CAPACITY : capaticy;
 elements = (E[]) new Object[capaticy];
 }
 
 
 /**
 * 清除所有元素
 */
 public void clear() {
 for (int i = 0; i < size; i++) {
  elements[i] = null;
 }
 size = 0;
 }

 /**
 * 元素的數(shù)量
 * @return
 */
 public int size() {
 return size;
 }

 /**
 * 是否為空
 * @return
 */
 public boolean isEmpty() {
  return size == 0;
 }

 /**
 * 是否包含某個(gè)元素
 * @param element
 * @return
 */
 public boolean contains(E element) {
 return indexOf(element) != ELEMENT_NOT_FOUND;
 }

 /**
 * 添加元素到尾部
 * @param element
 */
 public void add(E element) {
 add(size, element);
 }

 /**
 * 獲取index位置的元素
 * @param index
 * @return
 */
 public E get(int index) {
 rangeCheck(index);
 return elements[index];
 }

 /**
 * 設(shè)置index位置的元素
 * @param index
 * @param element
 * @return 原來的元素&#1461;
 */
 public E set(int index, E element) {
 rangeCheck(index);
 
 E old = elements[index];
 elements[index] = element;
 return old;
 }

 /**
 * 在index位置插入一個(gè)元素
 * @param index
 * @param element
 */
 public void add(int index, E element) {
 rangeCheckForAdd(index);
 
 ensureCapacity(size + 1);
 
 for (int i = size; i > index; i--) {
  elements[i] = elements[i - 1];
 }
 elements[index] = element;
 size++;
 }

 /**
 * 刪除index位置的元素
 * @param index
 * @return
 */
 public E remove(int index) {
 rangeCheck(index);
 
 E old = elements[index];
 for (int i = index + 1; i < size; i++) {
  elements[i - 1] = elements[i];
 }
 elements[--size] = null;
 return old;
 }

 /**
 * 查看元素的索引
 * @param element
 * @return
 */
 public int indexOf(E element) {
 if (element == null) { 
  for (int i = 0; i < size; i++) {
  if (elements[i] == null) return i; 
  }
 } else {
  for (int i = 0; i < size; i++) {
  if (element.equals(elements[i])) return i; 
  }
 }
 return ELEMENT_NOT_FOUND;
 }
 
 
 /**
 * 保證要有capacity的容量
 * @param capacity
 */
 private void ensureCapacity(int capacity) {
 int oldCapacity = elements.length;
 if (oldCapacity >= capacity) return;
 
 // 新容量為舊容量的1.5倍
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 E[] newElements = (E[]) new Object[newCapacity];
 for (int i = 0; i < size; i++) {
  newElements[i] = elements[i];
 }
 elements = newElements;

 }
 
 private void outOfBounds(int index) {
 throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
 }
 
 private void rangeCheck(int index) {
 if (index < 0 || index >= size) {
  outOfBounds(index);
 }
 }
 
 private void rangeCheckForAdd(int index) {
 if (index < 0 || index > size) {
  outOfBounds(index);
 }
 }
 
 @Override
 public String toString() {
 StringBuilder string = new StringBuilder();
 string.append("size=").append(size).append(", [");
 for (int i = 0; i < size; i++) {
  if (i != 0) {
  string.append(", ");
  }
  
  string.append(elements[i]);
 } 
 string.append("]");
 return string.toString();
 }
}

關(guān)于數(shù)組如何實(shí)現(xiàn)ArrayList的動態(tài)擴(kuò)容就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問一下細(xì)節(jié)

java數(shù)組如何實(shí)現(xiàn)ArrayList的動態(tài)擴(kuò)容

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽