Java中數(shù)組容器(ArrayList)設的計與實現(xiàn)
更新時間：2022年07月07日 09:02:48 作者：一無是處的研究僧
本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList、Vector的原理，并且自己使用Java實現(xiàn)自己的數(shù)組容器MyArrayList，讓自己寫的容器能像ArrayList那樣工作,感興趣的可以了解一下
本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList、Vector的原理，并且自己使用Java實現(xiàn)自己的數(shù)組容器MyArrayList，讓自己寫的容器能像ArrayList那樣工作。在本篇文章當中首先介紹ArrayList的一些基本功能，然后去分析我們自己的容器MyArrayList應該如何進行設計，同時分析我們自己的具體實現(xiàn)方法，最后進行代碼介紹?。?！
ArrayList為我們提供了哪些功能
我們來看一個簡單的代碼，隨機生成100個隨機數(shù)，查看生成隨機數(shù)當中是否存在50這個數(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);// 設置下標為5的數(shù)據(jù)為100
list.remove(5);// 刪除下標為5的數(shù)據(jù)
list.remove(new Integer(888));// 刪除容器當中的第一個值為5的數(shù)據(jù)
}
}上述代碼包含了ArrayList最基本的一個功能，一個是add方法，向數(shù)組容器當中加入數(shù)據(jù)，另外一個方法是get從容器當中拿出數(shù)據(jù)，set方法改變容器里的數(shù)據(jù)，remove方法刪除容器當中的數(shù)據(jù)。ArrayList的很多其他的方法都是圍繞這四個最基本的方法展開的，因此我們在這里不仔細介紹其他的方法了，后面我們自己實現(xiàn)的時候遇到問題的時候自然會需要設計相應的方法，然后我們進行解決即可。
現(xiàn)在我們就需要去設計一個數(shù)組容器實現(xiàn)“增刪改查”這四個基本功能。
設計原理分析
首先明白一點我們需要使用什么工具去實現(xiàn)這樣一個容器。我們手里有的工具就是Java提供給我們的最基本的功能——數(shù)組（這個好像是廢話，我們的標題就是數(shù)組容器??）。
當我們在Java當中使用數(shù)組去存儲數(shù)據(jù)時，數(shù)據(jù)在Java當中的內存布局大致如下圖所示。
我們在設計數(shù)組容器這樣一個數(shù)據(jù)結構的時候主要會遇到兩個問題：
- 我們申請數(shù)組的長度是多少。
- 當數(shù)組滿了之后怎么辦，也就是我們的擴容機制。
對于這兩個問題，首先我們數(shù)組的初始大小可以有默認值，在我們自己實現(xiàn)的MyArrayList當中設置為10，我們在使用類時也可以傳遞一個參數(shù)指定初始大小。第二個問題當我們的數(shù)組滿的時候我們需要對數(shù)組進行擴容，在我們實現(xiàn)的MyArrayList當中我們采取的方式是，新數(shù)組的長度是原數(shù)組的兩倍（這個跟JDK的ArrayList方式不一樣，ArrayList擴容為原來的1.5倍）。
代碼實現(xiàn)
為了讓我們的類實現(xiàn)的更加簡單我們在代碼當中就不做很多非必要的邏輯判斷并且拋出異常，我們的代碼只要能表現(xiàn)出我們的思想即可。
首先定義一個接口MyCollection，表示我們要實現(xiàn)哪些方法！
public interface MyCollection<E> {
/**
* 往鏈表尾部加入一個數(shù)據(jù)
* @param o 加入到鏈表當中的數(shù)據(jù)
* @return
*/
boolean add(E o);
/**
* 表示在第 index 位置插入數(shù)據(jù) o
* @param index
* @param o
* @return
*/
boolean add(int index, E o);
/**
* 從鏈表當中刪除數(shù)據(jù) o
* @param o
* @return
*/
boolean remove(E o);
/**
* 從鏈表當中刪除第 index 個數(shù)據(jù)
* @param index
* @return
*/
boolean remove(int index);
/**
* 往鏈表尾部加入一個數(shù)據(jù)，功能和 add 一樣
* @param o
* @return
*/
boolean append(E o);
/**
* 返回鏈表當中數(shù)據(jù)的個數(shù)
* @return
*/
int size();
/**
* 表示鏈表是否為空
* @return
*/
boolean isEmpty();
/**
* 表示鏈表當中是否包含數(shù)據(jù) o
* @param o
* @return
*/
boolean contain(E o);
/**
* 設置下標為 index 的數(shù)據(jù)為 o
* @param index
* @param o
* @return
*/
boolean set(int index, E o);
}
我們的構造函數(shù)，初始化過程。
public MyArrayList(int initialCapacity) {
this();
// 增長數(shù)組的空間為 initialCapacity，即申請一個數(shù)組
// 且數(shù)組的長度為 initialCapacity
grow(initialCapacity);
}
public MyArrayList() {
this.size = 0; // 容器當中的數(shù)據(jù)個數(shù)在開始時為 0
this.elementData = EMPTY_INSTANCE; // 將數(shù)組設置為空數(shù)組
}
我們需要實現(xiàn)的最復雜的方法就是add了，這個方法是四個方法當中最復雜的，其余的方法都相對比較簡單。
- 進入
add方法之后，我們需要找到符合要求的最小數(shù)組長度，這個值通常是容器當中元素的個數(shù)size + 1，也就是圖中的minCapacity首先先比較這個值和現(xiàn)在數(shù)組的長度，如果長度不夠的話則需要進行擴容，將數(shù)組的長度擴大到原來的兩倍。 - 如果不需要擴容，則直接講元素放入到數(shù)組當中即可。
@Override
public boolean add(E o) {
// 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
ensureCapacity(size + 1);
// 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
elementData[++size] = o;
return true;
}
/**
* 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 capacity
* @param capacity
*/
public void ensureCapacity(int capacity) {
int candidateCapacity = findCapacity(capacity);
if (elementData.length < candidateCapacity)
grow(candidateCapacity);
}
/**
* 這個函數(shù)的主要目的就是找到最終數(shù)組長度需求的容量
* @param minCapacity
* @return
*/
private int findCapacity(int minCapacity) {
/**
* 如果 if 條件為 true 即 elementData 還是初始化時設置的空數(shù)組
* 那么返回默認大小和需要大小的最大值
* 否則直接返回 minCapacity
*/
if (elementData == EMPTY_INSTANCE){
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
我們?yōu)槭裁葱枰獙?code>ensureCapacity的訪問限制權限設置為public？因為我們想讓用戶盡量去使用這個函數(shù)，因為如果我們如果寫出下面這樣的代碼我們會一直申請內存空間，然后也需要將前面的數(shù)組釋放掉，會給垃圾回收器造成更大的壓力。
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
list.add(i);
}
下面我們對ArrayList的方法進行測試：
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));
}
}
// 輸出結果
end - start: 1345
end - start: 4730
從上面的測試結果我們可以看出提前使用ensureCapacity方法之后，程序執(zhí)行的時間更加短。
插入數(shù)據(jù)的add方法。
@Override
public boolean add(E o) {
// 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
ensureCapacity(size + 1);
// 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
elementData[size] = o;
size++;
return true;
}
add在指定下標插入數(shù)據(jù)。
- 首先將插入下標后的數(shù)據(jù)往后移動一個位置
- 然后在將數(shù)據(jù)放在指定下標的位置。
/**
* 在下標 index 位置插入數(shù)據(jù) o
* 首先先將 index 位置之后的數(shù)據(jù)往后移動一個位置
* 然后將 index 賦值為 o
* @param index
* @param o
* @return
*/
@Override
public boolean add(int index, E o) {
// 確保容器當中的數(shù)組長度至少為 size + 1
ensureCapacity(size + 1);
// 將 elementData index位置之后的數(shù)據(jù)往后移動一個位置
// 做一個原地拷貝
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 移動的數(shù)據(jù)個數(shù)為 size - index
elementData[index] = o;
size++;
return true;
}
刪除數(shù)據(jù)的方法remove。
- 首先先刪除指定下標的數(shù)據(jù)。
- 然后將指定下標后的數(shù)據(jù)往前移動一個位置
- 在實際的操作過程中我們可以不刪除，直接移動，這樣也覆蓋被插入位置的數(shù)據(jù)了。
/**
* 移除下標為 index 的數(shù)據(jù)
* @param index
* @return
*/
@Override
public boolean remove(int index) {
// 需要被移動的數(shù)據(jù)個數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return true;
}
移除容器當中具體的某個對象。
/**
* 這個方法主要是用于溢出容器當中具體的某個數(shù)據(jù)
* 首先先通過 for 循環(huán)遍歷容器當中的每個數(shù)據(jù)，
* 比較找到相同的數(shù)據(jù)對應的下標，然后通過下標移除方法
* @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方法，這個方法就很簡單了。
@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();
}
測試代碼
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); // 容器會擴容兩倍，而默認容器長度為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> {
/**
* 容器當中存儲數(shù)據(jù)的個數(shù)
*/
private int size;
/**
* 容器中數(shù)組的默認長度
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 存放具體數(shù)據(jù)的數(shù)組，也就是我們容器當中真正存儲數(shù)據(jù)的地方
*/
Object[] elementData;
/**
* 當容器當中沒有數(shù)據(jù)將 elementData 設置為這個值，這個值是所有實例一起共享的
*/
private static final Object[] EMPTY_INSTANCE = {};
public MyArrayList(int initialCapacity) {
this();
// 增長數(shù)組的空間為 initialCapacity，即申請一個數(shù)組
// 且數(shù)組的長度為 initialCapacity
grow(initialCapacity);
}
public MyArrayList() {
this.size = 0; // 容器當中的數(shù)據(jù)個數(shù)在開始時為 0
this.elementData = EMPTY_INSTANCE; // 將數(shù)組設置為空數(shù)組
}
/**
* 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 capacity
* @param capacity
*/
public void ensureCapacity(int capacity) {
int candidateCapacity = findCapacity(capacity);
if (elementData.length < candidateCapacity)
grow(candidateCapacity);
}
/**
* 這個函數(shù)的主要目的就是找到最終數(shù)組長度需求的容量
* @param minCapacity
* @return
*/
private int findCapacity(int minCapacity) {
/**
* 如果 if 條件為 true 即 elementData 還是初始化時設置的空數(shù)組
* 那么返回默認大小和需要大小的最大值
* 否則直接返回 minCapacity
*/
if (elementData == EMPTY_INSTANCE){
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 該函數(shù)主要保證 elementData 的長度至少為 minCapacity
* 如果數(shù)組的長度小于 minCapacity 則需要進行擴容，反之
* @param minCapacity 數(shù)組的最短長度
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新的數(shù)組長度為原來數(shù)組長度的兩倍
int newCapacity = oldCapacity << 1;
// 如果數(shù)組新數(shù)組的長度 newCapacity 小于所需要的長度 minCapacity
// 新申請的長度應該為 minCapacity
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
// 申請一個長度為 newCapacity 的數(shù)組，在將原來數(shù)組
// elementData 的數(shù)據(jù)拷貝到新數(shù)組當中
elementData = Arrays.copyOf(elementData, newCapacity);
}
@Override
public boolean add(E o) {
// 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
ensureCapacity(size + 1);
// 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
elementData[size] = o;
size++;
return true;
}
/**
* 在下標 index 位置插入數(shù)據(jù) o
* 首先先將 index 位置之后的數(shù)據(jù)往后移動一個位置
* 然后將 index 賦值為 o
* @param index
* @param o
* @return
*/
@Override
public boolean add(int index, E o) {
// 確保容器當中的數(shù)組長度至少為 size + 1
ensureCapacity(size + 1);
// 將 elementData index位置之后的數(shù)據(jù)往后移動一個位置
// 做一個原地拷貝
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 移動的數(shù)據(jù)個數(shù)為 size - index
elementData[index] = o;
size++;
return true;
}
/**
* 這個方法主要是用于溢出容器當中具體的某個數(shù)據(jù)
* 首先先通過 for 循環(huán)遍歷容器當中的每個數(shù)據(jù)，
* 比較找到相同的數(shù)據(jù)對應的下標，然后通過下標移除方法
* @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;
}
/**
* 移除下標為 index 的數(shù)據(jù)
* @param index
* @return
*/
@Override
public boolean remove(int index) {
// 需要被移動的數(shù)據(jù)個數(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)設的計與實現(xiàn)的詳細內容，更多關于Java數(shù)組容器的資料請關注腳本之家其它相關文章！
相關文章
接口訪問頻率限制是通過在一定時間內限制用戶對接口的訪問次數(shù)來實現(xiàn)的,在Spring Boot中,我們可以通過多種方式來實現(xiàn)接口的限流,如使用過濾器、攔截器或者借助第三方庫,本文給大家講解的非常詳細,需要的朋友可以參考下2024-07-07
Map作為Java中的一種集合,以鍵值對的形式存放一批數(shù)據(jù),經常會被我們應用在項目中,下面這篇文章主要給大家介紹了關于Java遍歷Map的5種方式,需要的朋友可以參考下2023-02-02
最近工作中遇到了一個需求，需要利用java獲取字符串中的數(shù)字，嘗試幾種方法后發(fā)現(xiàn)利用正則表達式實現(xiàn)最為方法，下面這篇文章就主要介紹了Java通過正則表達式獲取字符串中數(shù)字的方法，文中給出了詳細的示例代碼，需要的朋友可以參考下。2017-03-03
Springboot如何獲取上下文ApplicationContext
這篇文章主要介紹了Springboot如何獲取上下文ApplicationContext，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
在 Java 多線程編程中，線程安全是一個非常重要的概念，本文主要介紹了Java中線程安全有哪些實現(xiàn)思路，非常具有實用價值，需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Java之Spring注解開發(fā)案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
【Redis緩存機制】詳解Java連接Redis_Jedis_事務
這篇文章主要介紹了【Redis緩存機制】詳解Java連接Redis_Jedis_事務，詳細的介紹了Jedis事務和實例，有興趣的可以了解一下。2016-12-12
這篇文章主要介紹了Java去掉指定字符串的開頭的指定字符操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了Springboot的maven間接依賴的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
Spring Boot中整合Spring Security并自定義驗證代碼實例
本篇文章主要介紹了Spring Boot中整合Spring Security并自定義驗證代碼實例，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-04-04