Java使用數(shù)組實(shí)現(xiàn)ArrayList的動(dòng)態(tài)擴(kuò)容的方法
提到數(shù)組大家肯定不會(huì)陌生，但我們也知道數(shù)組有個(gè)缺點(diǎn)就是在創(chuàng)建時(shí)就確定了長(zhǎng)度，之后就不能更改長(zhǎng)度。所以Java官方向我們提供了ArrayList這個(gè)可變長(zhǎng)的容器。其實(shí)ArrayList底層也是用數(shù)組進(jìn)行實(shí)現(xiàn)的，今天我們就自己使用數(shù)組實(shí)現(xiàn)ArrayList的功能。
一、整體框架
廢話不多說(shuō)，我們以存放int類型元素為例，看一下ArrayList需要的成員變量和需要實(shí)現(xiàn)的方法。
public class ArrayList
private int size;//用來(lái)記錄實(shí)際存儲(chǔ)元素個(gè)數(shù)
private int[] elements;//用來(lái)存儲(chǔ)元素的數(shù)組
//構(gòu)造方法：在創(chuàng)建ArrayList對(duì)象時(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 原來(lái)的元素
*/
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() {}
/**
* 用來(lái)打印列表
*/
public String toString() {}
}
二、方法實(shí)現(xiàn)
框架我們已經(jīng)有了，接下來(lái)我們一步步實(shí)現(xiàn)方法就行。
size()方法：
這個(gè)方法很簡(jiǎn)單，因?yàn)槲覀冇衧ize屬性，直接將其返回就行了。
public int size() {
return size;
}
isEmpty()方法：
這個(gè)方法也很簡(jiǎn)單，判斷是否為空只需要判斷size是否為0即可。
public boolean isEmpty() {
return size == 0;
}
indexOf(int element)方法：
這個(gè)方法是用來(lái)查詢?cè)氐乃谒饕恢?，并返回。我們通過(guò)遍歷列表查找即可，找到就將元素返回，沒(méi)有找到返回-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è)方法是用來(lái)查看所傳元素是否在數(shù)組中，我們可以直接通過(guò)indexOf()方法查看返回值是否不等于-1，不等于-1返回true，等于-1返回false。
public boolean contains(int element) {
return indexOf(element) != -1;
}
get(int index)方法：
這個(gè)方法用來(lái)獲取指定索引位置的元素，我們直接返回?cái)?shù)組的指定索引位置元素即可。
public int get(int index) {;
return elements[index];
}
set(int index, int element)方法:
這個(gè)方法用來(lái)將指定索引位置元素改為指定元素，并將原來(lái)元素返回，我們通過(guò)數(shù)組索引獲取到該位置元素，并將指定元素賦值給該位置索引并將原來(lái)元素返回。
public int set(int index, int element) {
int old = elements[index];
elements[index] = element;
return old;
}
add(int index, int element)方法：
個(gè)方法是在指定索引位置插入指定元素，我們首先將指定索引位置的元素以及之后所有的元素向后移動(dòng)一位，然后再將指定元素賦值給數(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è)方法用來(lái)刪除指定索引位置的元素，并將要?jiǎng)h除元素返回，我們首先通過(guò)指定索引獲取原來(lái)元素，當(dāng)刪除該元素后需要將index索引后面的所有元素向前移動(dòng)一位，最后將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è)方法用于將所有元素打印出來(lái)，通過(guò)StringBuilder對(duì)象進(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)了對(duì)數(shù)組的進(jìn)行數(shù)據(jù)的增刪改查，但最后想達(dá)到我們的目的還要進(jìn)一步優(yōu)化。
三、優(yōu)化
1.實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容
當(dāng)我們向數(shù)組中添加元素時(shí)，如果數(shù)組已經(jīng)滿了我們就需要就數(shù)組進(jìn)行動(dòng)態(tài)擴(kuò)容。擴(kuò)容的原理并不是真的對(duì)原數(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;
}
我們?cè)赼dd()方法中首先調(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)我們?cè)谡{(diào)用傳入索引的方法時(shí)，首先要保證傳入索引在可用范圍內(nèi)，不然會(huì)出現(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);
}
}
而對(duì)于調(diào)用add()方法時(shí)所傳入的索引范圍可以取到size位置，我們?cè)诙x一個(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)造方法
對(duì)于類中的常數(shù)我們更希望封裝成常量，并且聲明一個(gè)默認(rèn)容量，希望在創(chuàng)建對(duì)象時(shí)未傳入容量參數(shù)或傳入容量參數(shù)過(guò)小直接創(chuàng)建一個(gè)相對(duì)大小合適的數(shù)組。
private static final int DEFAULT_CAPACITY = 10;//我們將默認(rèn)容量設(shè)為10
private static final int ELEMENT_NOT_FOUND = -1;//我們將獲取指定元素的索引時(shí)，未找到的返回值-1封裝為常量
//聲明無(wú)參構(gòu)造方法，在調(diào)用無(wú)參構(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) ? DEFAULT_CAPACITY : capaticy;
elements = new int[capaticy];
}
四、使用泛型
以上步驟已經(jīng)使用數(shù)組完全實(shí)現(xiàn)了ArrayList的全部功能，但只能存放int類型的數(shù)據(jù)，如果我們希望儲(chǔ)存其他類型的數(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) ? 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 原來(lái)的元素ֵ
*/
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)于Java使用數(shù)組實(shí)現(xiàn)ArrayList的動(dòng)態(tài)擴(kuò)容的方法的文章就介紹到這了,更多相關(guān)Java ArrayList動(dòng)態(tài)擴(kuò)容內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- 關(guān)于Java的ArrayList數(shù)組自動(dòng)擴(kuò)容機(jī)制
- Java ArrayList擴(kuò)容機(jī)制原理深入分析
- Java中的ArrayList容量及擴(kuò)容方式
- Java基礎(chǔ)之ArrayList的擴(kuò)容機(jī)制
- 在java中ArrayList集合底層的擴(kuò)容原理
- 對(duì)Java ArrayList的自動(dòng)擴(kuò)容機(jī)制示例講解
- Java ArrayList擴(kuò)容問(wèn)題實(shí)例詳解
- Java中Arraylist動(dòng)態(tài)擴(kuò)容方法詳解
- 淺談Java中ArrayList的擴(kuò)容機(jī)制
相關(guān)文章
spring用戶通過(guò)交互界面登錄成功的實(shí)現(xiàn)
本文主要介紹了spring用戶通過(guò)交互界面登錄成功的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
Struts2開(kāi)發(fā)環(huán)境搭建 附簡(jiǎn)單登錄功能實(shí)例
這篇文章主要介紹了Struts2開(kāi)發(fā)環(huán)境搭建，為大家分享一個(gè)簡(jiǎn)單登錄功能實(shí)例,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-11-11
Java實(shí)戰(zhàn)之超市收銀管理系統(tǒng)的實(shí)現(xiàn)
這篇文章主要介紹了如何利用Java實(shí)現(xiàn)超市收銀管理系統(tǒng)，文中采用的技術(shù)有：Spring、SpringMVC、MyBatis、ThymeLeaf等，需要的可以參考一下2022-03-03
這篇文章主要介紹了枚舉java語(yǔ)言中的修飾符組合，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-07-07
Java實(shí)現(xiàn)簡(jiǎn)單的飛機(jī)大戰(zhàn)游戲(控制主飛機(jī)篇)
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)簡(jiǎn)單的飛機(jī)大戰(zhàn)游戲，控制主飛機(jī)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
java使用DOM4J對(duì)XML文件進(jìn)行增刪改查操作
這篇文章主要為大家詳細(xì)介紹了java使用DOM4J對(duì)XML文件進(jìn)行增刪改查操作，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
springboot+thymeleaf+mybatis實(shí)現(xiàn)甘特圖的詳細(xì)過(guò)程
這篇文章主要介紹了springboot+thymeleaf+mybatis實(shí)現(xiàn)甘特圖的詳細(xì)過(guò)程,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-07-07
這篇文章主要介紹了詳解Java面向?qū)ο笾械睦^承，繼承提高代碼的復(fù)用性：通過(guò)繼承，子類可以直接使用父類的屬性和方法，不需要重復(fù)定義,需要的朋友可以參考下2023-05-05
現(xiàn)在面試Java開(kāi)發(fā)時(shí)，基本都會(huì)問(wèn)到Java虛擬機(jī)的知識(shí)，根據(jù)職位不同問(wèn)的內(nèi)容深淺又有所區(qū)別。本文整理了10道面試中常問(wèn)的Java虛擬機(jī)面試題，希望對(duì)正在面試的同學(xué)有所幫助2021-06-06
java求最大公約數(shù)與最小公倍數(shù)的方法示例
這篇文章主要介紹了java求最大公約數(shù)與最小公倍數(shù)的方法,涉及java數(shù)值運(yùn)算的相關(guān)操作技巧,并附帶分析了eclipse環(huán)境下設(shè)置運(yùn)行輸入?yún)?shù)的相關(guān)操作技巧,需要的朋友可以參考下2017-11-11