Java中數(shù)組容器(ArrayList)設(shè)的計(jì)與實(shí)現(xiàn)
本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList
、Vector
的原理,并且自己使用Java
實(shí)現(xiàn)自己的數(shù)組容器MyArrayList
,讓自己寫的容器能像ArrayList
那樣工作。在本篇文章當(dāng)中首先介紹ArrayList
的一些基本功能,然后去分析我們自己的容器MyArrayList
應(yīng)該如何進(jìn)行設(shè)計(jì),同時(shí)分析我們自己的具體實(shí)現(xiàn)方法,最后進(jìn)行代碼介紹?。?!
ArrayList為我們提供了哪些功能
我們來看一個(gè)簡(jiǎn)單的代碼,隨機(jī)生成100個(gè)隨機(jī)數(shù),查看生成隨機(jī)數(shù)當(dāng)中是否存在50這個(gè)數(shù)。
public class MyArrayList { public static void main(String[] args) { Random random = new Random(); ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 100; i++) { list.add(random.nextInt(5000)); } for (int i = 0; i < 100; i++) { if (list.get(i) == 50) { System.out.println("包含數(shù)據(jù) 50"); } } list.set(5, 1000);// 設(shè)置下標(biāo)為5的數(shù)據(jù)為100 list.remove(5);// 刪除下標(biāo)為5的數(shù)據(jù) list.remove(new Integer(888));// 刪除容器當(dāng)中的第一個(gè)值為5的數(shù)據(jù) } }
上述代碼包含了ArrayList
最基本的一個(gè)功能,一個(gè)是add
方法,向數(shù)組容器當(dāng)中加入數(shù)據(jù),另外一個(gè)方法是get
從容器當(dāng)中拿出數(shù)據(jù),set
方法改變?nèi)萜骼锏臄?shù)據(jù),remove
方法刪除容器當(dāng)中的數(shù)據(jù)。ArrayList
的很多其他的方法都是圍繞這四個(gè)最基本的方法展開的,因此我們?cè)谶@里不仔細(xì)介紹其他的方法了,后面我們自己實(shí)現(xiàn)的時(shí)候遇到問題的時(shí)候自然會(huì)需要設(shè)計(jì)相應(yīng)的方法,然后我們進(jìn)行解決即可。
現(xiàn)在我們就需要去設(shè)計(jì)一個(gè)數(shù)組容器實(shí)現(xiàn)“增刪改查”這四個(gè)基本功能。
設(shè)計(jì)原理分析
首先明白一點(diǎn)我們需要使用什么工具去實(shí)現(xiàn)這樣一個(gè)容器。我們手里有的工具就是Java
提供給我們的最基本的功能——數(shù)組(這個(gè)好像是廢話,我們的標(biāo)題就是數(shù)組容器??)。
當(dāng)我們?cè)?code>Java當(dāng)中使用數(shù)組去存儲(chǔ)數(shù)據(jù)時(shí),數(shù)據(jù)在Java
當(dāng)中的內(nèi)存布局大致如下圖所示。
我們?cè)谠O(shè)計(jì)數(shù)組容器這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)的時(shí)候主要會(huì)遇到兩個(gè)問題:
- 我們申請(qǐng)數(shù)組的長(zhǎng)度是多少。
- 當(dāng)數(shù)組滿了之后怎么辦,也就是我們的擴(kuò)容機(jī)制。
對(duì)于這兩個(gè)問題,首先我們數(shù)組的初始大小可以有默認(rèn)值,在我們自己實(shí)現(xiàn)的MyArrayList
當(dāng)中設(shè)置為10,我們?cè)谑褂妙悤r(shí)也可以傳遞一個(gè)參數(shù)指定初始大小。第二個(gè)問題當(dāng)我們的數(shù)組滿的時(shí)候我們需要對(duì)數(shù)組進(jìn)行擴(kuò)容,在我們實(shí)現(xiàn)的MyArrayList
當(dāng)中我們采取的方式是,新數(shù)組的長(zhǎng)度是原數(shù)組的兩倍(這個(gè)跟JDK
的ArrayList
方式不一樣,ArrayList
擴(kuò)容為原來的1.5倍)。
代碼實(shí)現(xiàn)
為了讓我們的類實(shí)現(xiàn)的更加簡(jiǎn)單我們?cè)诖a當(dāng)中就不做很多非必要的邏輯判斷并且拋出異常,我們的代碼只要能表現(xiàn)出我們的思想即可。
首先定義一個(gè)接口MyCollection
,表示我們要實(shí)現(xiàn)哪些方法!
public interface MyCollection<E> { /** * 往鏈表尾部加入一個(gè)數(shù)據(jù) * @param o 加入到鏈表當(dāng)中的數(shù)據(jù) * @return */ boolean add(E o); /** * 表示在第 index 位置插入數(shù)據(jù) o * @param index * @param o * @return */ boolean add(int index, E o); /** * 從鏈表當(dāng)中刪除數(shù)據(jù) o * @param o * @return */ boolean remove(E o); /** * 從鏈表當(dāng)中刪除第 index 個(gè)數(shù)據(jù) * @param index * @return */ boolean remove(int index); /** * 往鏈表尾部加入一個(gè)數(shù)據(jù),功能和 add 一樣 * @param o * @return */ boolean append(E o); /** * 返回鏈表當(dāng)中數(shù)據(jù)的個(gè)數(shù) * @return */ int size(); /** * 表示鏈表是否為空 * @return */ boolean isEmpty(); /** * 表示鏈表當(dāng)中是否包含數(shù)據(jù) o * @param o * @return */ boolean contain(E o); /** * 設(shè)置下標(biāo)為 index 的數(shù)據(jù)為 o * @param index * @param o * @return */ boolean set(int index, E o); }
我們的構(gòu)造函數(shù),初始化過程。
public MyArrayList(int initialCapacity) { this(); // 增長(zhǎng)數(shù)組的空間為 initialCapacity,即申請(qǐng)一個(gè)數(shù)組 // 且數(shù)組的長(zhǎng)度為 initialCapacity grow(initialCapacity); } public MyArrayList() { this.size = 0; // 容器當(dāng)中的數(shù)據(jù)個(gè)數(shù)在開始時(shí)為 0 this.elementData = EMPTY_INSTANCE; // 將數(shù)組設(shè)置為空數(shù)組 }
我們需要實(shí)現(xiàn)的最復(fù)雜的方法就是add
了,這個(gè)方法是四個(gè)方法當(dāng)中最復(fù)雜的,其余的方法都相對(duì)比較簡(jiǎn)單。
- 進(jìn)入
add
方法之后,我們需要找到符合要求的最小數(shù)組長(zhǎng)度,這個(gè)值通常是容器當(dāng)中元素的個(gè)數(shù)size + 1
,也就是圖中的minCapacity
首先先比較這個(gè)值和現(xiàn)在數(shù)組的長(zhǎng)度,如果長(zhǎng)度不夠的話則需要進(jìn)行擴(kuò)容,將數(shù)組的長(zhǎng)度擴(kuò)大到原來的兩倍。 - 如果不需要擴(kuò)容,則直接講元素放入到數(shù)組當(dāng)中即可。
@Override public boolean add(E o) { // 這個(gè)函數(shù)的主要作用就是確保數(shù)組的長(zhǎng)度至少為 size + 1 ensureCapacity(size + 1); // 新增加了一個(gè)數(shù)據(jù),容器的大小需要 + 1 elementData[++size] = o; return true; } /** * 這個(gè)函數(shù)的主要作用就是確保數(shù)組的長(zhǎng)度至少為 capacity * @param capacity */ public void ensureCapacity(int capacity) { int candidateCapacity = findCapacity(capacity); if (elementData.length < candidateCapacity) grow(candidateCapacity); } /** * 這個(gè)函數(shù)的主要目的就是找到最終數(shù)組長(zhǎng)度需求的容量 * @param minCapacity * @return */ private int findCapacity(int minCapacity) { /** * 如果 if 條件為 true 即 elementData 還是初始化時(shí)設(shè)置的空數(shù)組 * 那么返回默認(rèn)大小和需要大小的最大值 * 否則直接返回 minCapacity */ if (elementData == EMPTY_INSTANCE){ return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
我們?yōu)槭裁葱枰獙?code>ensureCapacity的訪問限制權(quán)限設(shè)置為public
?因?yàn)槲覀兿胱層脩舯M量去使用這個(gè)函數(shù),因?yàn)槿绻覀內(nèi)绻麑懗鱿旅孢@樣的代碼我們會(huì)一直申請(qǐng)內(nèi)存空間,然后也需要將前面的數(shù)組釋放掉,會(huì)給垃圾回收器造成更大的壓力。
ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 1000000; i++) { list.add(i); }
下面我們對(duì)ArrayList
的方法進(jìn)行測(cè)試:
import java.util.ArrayList; class Person { String name; public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + '}'; } } public class ArrayListTest { public static void main(String[] args) { ArrayList<Person> o1 = new ArrayList<>(); o1.ensureCapacity(10000000); long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { o1.add(new Person()); } long end = System.currentTimeMillis(); System.out.println("end - start: " + (end - start)); ArrayList<Person> o2 = new ArrayList<>(); start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { o2.add(new Person()); } end = System.currentTimeMillis(); System.out.println("end - start: " + (end - start)); } } // 輸出結(jié)果 end - start: 1345 end - start: 4730
從上面的測(cè)試結(jié)果我們可以看出提前使用ensureCapacity
方法之后,程序執(zhí)行的時(shí)間更加短。
插入數(shù)據(jù)的add
方法。
@Override public boolean add(E o) { // 這個(gè)函數(shù)的主要作用就是確保數(shù)組的長(zhǎng)度至少為 size + 1 ensureCapacity(size + 1); // 新增加了一個(gè)數(shù)據(jù),容器的大小需要 + 1 elementData[size] = o; size++; return true; }
add
在指定下標(biāo)插入數(shù)據(jù)。
- 首先將插入下標(biāo)后的數(shù)據(jù)往后移動(dòng)一個(gè)位置
- 然后在將數(shù)據(jù)放在指定下標(biāo)的位置。
/** * 在下標(biāo) index 位置插入數(shù)據(jù) o * 首先先將 index 位置之后的數(shù)據(jù)往后移動(dòng)一個(gè)位置 * 然后將 index 賦值為 o * @param index * @param o * @return */ @Override public boolean add(int index, E o) { // 確保容器當(dāng)中的數(shù)組長(zhǎng)度至少為 size + 1 ensureCapacity(size + 1); // 將 elementData index位置之后的數(shù)據(jù)往后移動(dòng)一個(gè)位置 // 做一個(gè)原地拷貝 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 移動(dòng)的數(shù)據(jù)個(gè)數(shù)為 size - index elementData[index] = o; size++; return true; }
刪除數(shù)據(jù)的方法remove
。
- 首先先刪除指定下標(biāo)的數(shù)據(jù)。
- 然后將指定下標(biāo)后的數(shù)據(jù)往前移動(dòng)一個(gè)位置
- 在實(shí)際的操作過程中我們可以不刪除,直接移動(dòng),這樣也覆蓋被插入位置的數(shù)據(jù)了。
/** * 移除下標(biāo)為 index 的數(shù)據(jù) * @param index * @return */ @Override public boolean remove(int index) { // 需要被移動(dòng)的數(shù)據(jù)個(gè)數(shù) int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; return true; }
移除容器當(dāng)中具體的某個(gè)對(duì)象。
/** * 這個(gè)方法主要是用于溢出容器當(dāng)中具體的某個(gè)數(shù)據(jù) * 首先先通過 for 循環(huán)遍歷容器當(dāng)中的每個(gè)數(shù)據(jù), * 比較找到相同的數(shù)據(jù)對(duì)應(yīng)的下標(biāo),然后通過下標(biāo)移除方法 * @param o * @return */ @Override public boolean remove(E o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { remove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { remove(index); return true; } } return false; }
set
方法,這個(gè)方法就很簡(jiǎn)單了。
@Override public boolean set(int index, E o) { elementData[index] = o; return true; }
重寫toString
方法。
@Override public String toString() { if (size <= 0) return "[]"; StringBuilder builder = new StringBuilder(); builder.append("["); for (int index = 0; index < size; index++) { builder.append(elementData[index].toString() + ", "); } builder.delete(builder.length() - 2, builder.length()); builder.append("]"); return builder.toString(); }
測(cè)試代碼
public static void main(String[] args) { MyArrayList<Integer> list = new MyArrayList<>(); for (int i = 0; i < 15; i++) { list.add(-i); } System.out.println(list.contain(5)); System.out.println(list); list.remove(new Integer(-6)); System.out.println(list); System.out.println(list.elementData.length); // 容器會(huì)擴(kuò)容兩倍,而默認(rèn)容器長(zhǎng)度為10,因此這里是 20 list.add(5, 99999); System.out.println(list); System.out.println(list.contain(99999)); } // 代碼輸出 false [0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14] [0, -1, -2, -3, -4, -5, -7, -8, -9, -10, -11, -12, -13, -14] 20 [0, -1, -2, -3, -4, 99999, -5, -7, -8, -9, -10, -11, -12, -13, -14] true
完整代碼
import java.util.ArrayList; import java.util.Arrays; public class MyArrayList<E> implements MyCollection<E> { /** * 容器當(dāng)中存儲(chǔ)數(shù)據(jù)的個(gè)數(shù) */ private int size; /** * 容器中數(shù)組的默認(rèn)長(zhǎng)度 */ private static final int DEFAULT_CAPACITY = 10; /** * 存放具體數(shù)據(jù)的數(shù)組,也就是我們?nèi)萜鳟?dāng)中真正存儲(chǔ)數(shù)據(jù)的地方 */ Object[] elementData; /** * 當(dāng)容器當(dāng)中沒有數(shù)據(jù)將 elementData 設(shè)置為這個(gè)值,這個(gè)值是所有實(shí)例一起共享的 */ private static final Object[] EMPTY_INSTANCE = {}; public MyArrayList(int initialCapacity) { this(); // 增長(zhǎng)數(shù)組的空間為 initialCapacity,即申請(qǐng)一個(gè)數(shù)組 // 且數(shù)組的長(zhǎng)度為 initialCapacity grow(initialCapacity); } public MyArrayList() { this.size = 0; // 容器當(dāng)中的數(shù)據(jù)個(gè)數(shù)在開始時(shí)為 0 this.elementData = EMPTY_INSTANCE; // 將數(shù)組設(shè)置為空數(shù)組 } /** * 這個(gè)函數(shù)的主要作用就是確保數(shù)組的長(zhǎng)度至少為 capacity * @param capacity */ public void ensureCapacity(int capacity) { int candidateCapacity = findCapacity(capacity); if (elementData.length < candidateCapacity) grow(candidateCapacity); } /** * 這個(gè)函數(shù)的主要目的就是找到最終數(shù)組長(zhǎng)度需求的容量 * @param minCapacity * @return */ private int findCapacity(int minCapacity) { /** * 如果 if 條件為 true 即 elementData 還是初始化時(shí)設(shè)置的空數(shù)組 * 那么返回默認(rèn)大小和需要大小的最大值 * 否則直接返回 minCapacity */ if (elementData == EMPTY_INSTANCE){ return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } /** * 該函數(shù)主要保證 elementData 的長(zhǎng)度至少為 minCapacity * 如果數(shù)組的長(zhǎng)度小于 minCapacity 則需要進(jìn)行擴(kuò)容,反之 * @param minCapacity 數(shù)組的最短長(zhǎng)度 */ private void grow(int minCapacity) { int oldCapacity = elementData.length; // 新的數(shù)組長(zhǎng)度為原來數(shù)組長(zhǎng)度的兩倍 int newCapacity = oldCapacity << 1; // 如果數(shù)組新數(shù)組的長(zhǎng)度 newCapacity 小于所需要的長(zhǎng)度 minCapacity // 新申請(qǐng)的長(zhǎng)度應(yīng)該為 minCapacity if (newCapacity < minCapacity) { newCapacity = minCapacity; } // 申請(qǐng)一個(gè)長(zhǎng)度為 newCapacity 的數(shù)組,在將原來數(shù)組 // elementData 的數(shù)據(jù)拷貝到新數(shù)組當(dāng)中 elementData = Arrays.copyOf(elementData, newCapacity); } @Override public boolean add(E o) { // 這個(gè)函數(shù)的主要作用就是確保數(shù)組的長(zhǎng)度至少為 size + 1 ensureCapacity(size + 1); // 新增加了一個(gè)數(shù)據(jù),容器的大小需要 + 1 elementData[size] = o; size++; return true; } /** * 在下標(biāo) index 位置插入數(shù)據(jù) o * 首先先將 index 位置之后的數(shù)據(jù)往后移動(dòng)一個(gè)位置 * 然后將 index 賦值為 o * @param index * @param o * @return */ @Override public boolean add(int index, E o) { // 確保容器當(dāng)中的數(shù)組長(zhǎng)度至少為 size + 1 ensureCapacity(size + 1); // 將 elementData index位置之后的數(shù)據(jù)往后移動(dòng)一個(gè)位置 // 做一個(gè)原地拷貝 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 移動(dòng)的數(shù)據(jù)個(gè)數(shù)為 size - index elementData[index] = o; size++; return true; } /** * 這個(gè)方法主要是用于溢出容器當(dāng)中具體的某個(gè)數(shù)據(jù) * 首先先通過 for 循環(huán)遍歷容器當(dāng)中的每個(gè)數(shù)據(jù), * 比較找到相同的數(shù)據(jù)對(duì)應(yīng)的下標(biāo),然后通過下標(biāo)移除方法 * @param o * @return */ @Override public boolean remove(E o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { remove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { remove(index); return true; } } return false; } /** * 移除下標(biāo)為 index 的數(shù)據(jù) * @param index * @return */ @Override public boolean remove(int index) { // 需要被移動(dòng)的數(shù)據(jù)個(gè)數(shù) int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; return true; } @Override public boolean append(E o) { return add(o); } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contain(E o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { return true; } } return false; } @Override public String toString() { if (size <= 0) return "[]"; StringBuilder builder = new StringBuilder(); builder.append("["); for (int index = 0; index < size; index++) { builder.append(elementData[index].toString() + ", "); } builder.delete(builder.length() - 2, builder.length()); builder.append("]"); return builder.toString(); } @Override public boolean set(int index, E o) { elementData[index] = o; return true; } public static void main(String[] args) { MyArrayList<Integer> list = new MyArrayList<>(); for (int i = 0; i < 15; i++) { list.add(-i); } System.out.println(list.contain(5)); System.out.println(list); list.remove(new Integer(-6)); System.out.println(list); System.out.println(list.elementData.length); list.add(5, 99999); System.out.println(list); System.out.println(list.contain(99999)); } }
以上就是Java中數(shù)組容器(ArrayList)設(shè)的計(jì)與實(shí)現(xiàn)的詳細(xì)內(nèi)容,更多關(guān)于Java數(shù)組容器的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Spring Boot中使用Spring-data-jpa的配置方法詳解
今天小編就為大家分享一篇關(guān)于Spring Boot中使用Spring-data-jpa的配置方法詳解,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2019-03-03淺談Java HttpURLConnection請(qǐng)求方式
這篇文章主要介紹了淺談Java HttpURLConnection請(qǐng)求方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-08-08Springboot+MybatisPlus+Oracle實(shí)現(xiàn)主鍵自增的示例代碼
這篇文章主要介紹了Springboot+MybatisPlus+Oracle實(shí)現(xiàn)主鍵自增的示例代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11深入解析Java的Struts框架中的控制器DispatchAction
這篇文章主要介紹了深入解析Java的Struts框架中的控制器DispatchAction,Struts是Java的SSH三大web開發(fā)框架之一,需要的朋友可以參考下2015-12-12SpringBoot中的@PostConstruct注解詳細(xì)解析
這篇文章主要介紹了SpringBoot中的@PostConstruct注解詳細(xì)解析,@PostConstruct注解,主要用于在Spring容器啟動(dòng)時(shí)執(zhí)行某些操作或者任務(wù),@PostConstruct注解一般放在BEAN的方法上,一旦BEAN初始化完成之后,將會(huì)調(diào)用這個(gè)方法,需要的朋友可以參考下2024-01-01Java MultipartFile實(shí)現(xiàn)上傳文件/上傳圖片
這篇文章主要介紹了Java MultipartFile實(shí)現(xiàn)上傳文件/上傳圖片,幫助大家更好的理解和使用Java,感興趣的朋友可以了解下2020-12-12Java深入分析Iterator迭代器與foreach循環(huán)的使用
這篇文章主要介紹了Java-Iterator迭代器與foreach循環(huán),主要包括Iterator迭代器接口的操作方法和foreach?循環(huán)語(yǔ)法解析,需要的朋友可以參考下2022-05-05