Java使用數組實現ArrayList的動態擴容的方法
提到數組大家肯定不會陌生,但我們也知道數組有個缺點就是在創建時就確定了長度,之后就不能更改長度。所以Java官方向我們提供了ArrayList這個可變長的容器。其實ArrayList底層也是用數組進行實現的,今天我們就自己使用數組實現ArrayList的功能。
一、整體框架
廢話不多說,我們以存放int類型元素為例,看一下ArrayList需要的成員變量和需要實現的方法。
public class ArrayList private int size;//用來記錄實際存儲元素個數 private int[] elements;//用來存儲元素的數組 //構造方法:在創建ArrayList對象時,初始化elements數組 public ArrayList(int capacity){ elements = new int[capacity]; } /** * 元素的數量 * @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) {} /** * 設置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() {} }
二、方法實現
框架我們已經有了,接下來我們一步步實現方法就行。
size()方法:
這個方法很簡單,因為我們有size屬性,直接將其返回就行了。
public int size() { return size;}
isEmpty()方法:
這個方法也很簡單,判斷是否為空只需要判斷size是否為0即可。
public boolean isEmpty() { return size == 0;}
indexOf(int element)方法:
這個方法是用來查詢元素的所在索引位置,并返回。我們通過遍歷列表查找即可,找到就將元素返回,沒有找到返回-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)方法:
這個方法是用來查看所傳元素是否在數組中,我們可以直接通過indexOf()方法查看返回值是否不等于-1,不等于-1返回true,等于-1返回false。
public boolean contains(int element) { return indexOf(element) != -1;}
get(int index)方法:
這個方法用來獲取指定索引位置的元素,我們直接返回數組的指定索引位置元素即可。
public int get(int index) {; return elements[index];}
set(int index, int element)方法:
這個方法用來將指定索引位置元素改為指定元素,并將原來元素返回,我們通過數組索引獲取到該位置元素,并將指定元素賦值給該位置索引并將原來元素返回。
public int set(int index, int element) { int old = elements[index]; elements[index] = element; return old;}
add(int index, int element)方法:
個方法是在指定索引位置插入指定元素,我們首先將指定索引位置的元素以及之后所有的元素向后移動一位,然后再將指定元素賦值給數組的指定索引位置,最后并將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)方法:
這個方法是在數組尾部添加元素,我們直接調用add(int index, int element)方法,將size作為index的參數傳入即可。
public void add(int element) { add(size, element);}
remove(int index)方法:
這個方法用來刪除指定索引位置的元素,并將要刪除元素返回,我們首先通過指定索引獲取原來元素,當刪除該元素后需要將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()方法:
這個方法,用于清空數組中所有元素,我們只需要將size賦值為0即可。
public void clear() { size = 0;}
toString()方法:
這個方法用于將所有元素打印出來,通過StringBuilder對象進行拼接,最后轉成字符串返回即可。
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();}
以上代碼基本實現了對數組的進行數據的增刪改查,但最后想達到我們的目的還要進一步優化。
三、優化
1.實現動態擴容
當我們向數組中添加元素時,如果數組已經滿了我們就需要就數組進行動態擴容。擴容的原理并不是真的對原數組進行增加內存操作,而是重新創建一個更大的數組,并將原數組的元素賦給新的數組。我們聲明一個私有方法確保添加元素前數組的容量足夠。
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()方法中首先調用ensureCapacity(int capacity)方法進行判斷數組容量是否足夠,不夠進行擴容。
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. 確保索引不越界
當我們在調用傳入索引的方法時,首先要保證傳入索引在可用范圍內,不然會出現角標越界的異常。定義outOfBound()方法,用于拋出角標越界異常信息。
private void outOfBounds(int index) { throw new IndexOutOfBoundsException('Index:' + index + ', Size:' + size);}
定義rangeCheck()方法用于檢查索引是否越界,如果越界,調用outOfBound()拋出異常。
private void rangeCheck(int index) { if (index < 0 || index >= size) { outOfBounds(index); }}
而對于調用add()方法時所傳入的索引范圍可以取到size位置,我們在定義一個rangeCheckForAdd()方法,用于檢查調用add()方法時索引是否越界。
private void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outOfBounds(index); }}
在get()方法,set()方法和remove()方法中,先調用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. 設置常量以及重寫構造方法
對于類中的常數我們更希望封裝成常量,并且聲明一個默認容量,希望在創建對象時未傳入容量參數或傳入容量參數過小直接創建一個相對大小合適的數組。
private static final int DEFAULT_CAPACITY = 10;//我們將默認容量設為10private static final int ELEMENT_NOT_FOUND = -1;//我們將獲取指定元素的索引時,未找到的返回值-1封裝為常量//聲明無參構造方法,在調用無參構造方法是直接創建默認容量的數組public ArrayList(){ elements = new int[DEFAULT_CAPACITY];}//聲明有參構造方法,在傳入參數小于默認容量時,我們仍然創建默認容量數組public ArrayList(int capaticy) { capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy; elements = new int[capaticy];}
四、使用泛型
以上步驟已經使用數組完全實現了ArrayList的全部功能,但只能存放int類型的數據,如果我們希望儲存其他類型的數據我們只需要使用Java中的泛型就能夠完成。
思路與上述完全一樣,整體代碼如下:
public class ArrayList<E> { /** * 元素的數量 */ 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) ? DEFAULT_CAPACITY : capaticy; elements = (E[]) new Object[capaticy]; } /** * 清除所有元素 */ public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; } /** * 元素的數量 * @return */ public int size() { return size; } /** * 是否為空 * @return */ public boolean isEmpty() { return size == 0; } /** * 是否包含某個元素 * @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]; } /** * 設置index位置的元素 * @param index * @param element * @return 原來的元素ֵ */ public E set(int index, E element) { rangeCheck(index); E old = elements[index]; elements[index] = element; return old; } /** * 在index位置插入一個元素 * @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(); }}
到此這篇關于Java使用數組實現ArrayList的動態擴容的方法的文章就介紹到這了,更多相關Java ArrayList動態擴容內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網!
相關文章:
1. React+umi+typeScript創建項目的過程2. ASP調用WebService轉化成JSON數據,附json.min.asp3. php測試程序運行速度和頁面執行速度的代碼4. php網絡安全中命令執行漏洞的產生及本質探究5. ASP.NET Core 5.0中的Host.CreateDefaultBuilder執行過程解析6. 無線標記語言(WML)基礎之WMLScript 基礎第1/2頁7. Warning: require(): open_basedir restriction in effect,目錄配置open_basedir報錯問題分析8. ASP中常用的22個FSO文件操作函數整理9. SharePoint Server 2019新特性介紹10. 三個不常見的 HTML5 實用新特性簡介
