Java線性表的順序表示及實(shí)現(xiàn)
前言
在之前對(duì)順序表使用C語(yǔ)言進(jìn)行了簡(jiǎn)單的實(shí)現(xiàn)：C語(yǔ)言線性表順序表示及實(shí)現(xiàn)
當(dāng)時(shí)使用C語(yǔ)言進(jìn)行實(shí)現(xiàn)是因?yàn)閷W(xué)校的教材使用的是C語(yǔ)言來(lái)進(jìn)行實(shí)現(xiàn)，在后來(lái)的學(xué)習(xí)中，Java成為了我的主語(yǔ)言，使用不同的語(yǔ)言對(duì)順序表來(lái)進(jìn)行實(shí)現(xiàn)也可以加深我對(duì)語(yǔ)言的理解和應(yīng)用。
一、什么是順序表？
順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素、使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過(guò)數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來(lái)反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系，采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組地址連續(xù)的存儲(chǔ)單元中。
二、順序表的實(shí)現(xiàn)
在順序表的定義中可以看到，順序表是一組地址連續(xù)的存儲(chǔ)單元，本質(zhì)上是一種增加了一些基本操作功能的數(shù)組
在本文中要實(shí)現(xiàn)的功能有：
- 獲取順序表中的元素個(gè)數(shù)
- 獲取順序表當(dāng)前的容量
- 順序表是否為空
- 在指定索引位置添加元素
- 在順序表末尾添加元素
- 在順序表頭部添加元素
- 獲取指定索引位置的元素
- 獲取順序表第一個(gè)元素
- 獲取順序表最后一個(gè)元素
- 修改指定索引位置的元素
- 判斷順序表中是否包含指定元素
- 獲取順序表中指定元素的索引
- 刪除指定索引位置的元素
- 刪除并返回順序表第一個(gè)元素
- 刪除并返回順序表最后一個(gè)元素
- 刪除順序表中的指定元素
- 對(duì)順序表進(jìn)行動(dòng)態(tài)的擴(kuò)容和縮容
1. 準(zhǔn)備工作
| 實(shí)現(xiàn)工具 | 版本 |
|---|---|
| IntelliJ IDEA | 2021.3 |
| JDK | 1.8 |
在 IntelliJ IDEA 中新建普通的Java項(xiàng)目即可
在新建好Java工程后，我們創(chuàng)建自己的順序表類，在這里我對(duì)當(dāng)前類命名為Array，在這里實(shí)現(xiàn)泛型，同時(shí)Array類中需要有兩個(gè)成員屬性：
- 存放數(shù)據(jù)的數(shù)組：
data，類型為泛型數(shù)組 - 當(dāng)前順序表中元素的數(shù)量：
size，類型為int
兩個(gè)成員屬性的訪問(wèn)權(quán)限都應(yīng)該為private，用戶不能夠直接進(jìn)行修改，只能通過(guò)對(duì)應(yīng)的getter方法進(jìn)行獲取。 在成員屬性中我們將存放數(shù)據(jù)的數(shù)組和順序表中的元素?cái)?shù)量只是進(jìn)行了聲明，但是并未進(jìn)行初始化，因此==初始化的過(guò)程就需要在構(gòu)造方法中進(jìn)行==
- 有參構(gòu)造：在進(jìn)行有參構(gòu)造時(shí)，我們只需要指定傳入的參數(shù)為一個(gè)
int類型的數(shù)據(jù)capacity，代表順序表的初始容量，因此對(duì)data進(jìn)行初始化泛型數(shù)組即可。同時(shí)當(dāng)前順序表中是沒有元素的，代表順序表中的元素個(gè)數(shù)size的初始值為0。 - 無(wú)參構(gòu)造：在用戶沒有指定了順序表的初始容量時(shí)我們可以自定義初始容量為10，僅需要通過(guò)
this(10)進(jìn)行有參構(gòu)造的調(diào)用即可。
注意： 在Java中不能直接初始化泛型數(shù)組，需要先聲明Object類型的數(shù)組后通過(guò)強(qiáng)制類型轉(zhuǎn)換的方式將Object類型的數(shù)組轉(zhuǎn)換為泛型數(shù)組
package net.csdn.array;
/**
* @author zhangrongkang
* @date 2022/6/26
*/
public class Array<E> {
/**
* 存放數(shù)據(jù)的數(shù)組
*/
private E[] data;
/**
* 數(shù)組中元素的數(shù)量
*/
private int size;
/**
* 構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造數(shù)組
*
* @param capacity 初始數(shù)組大小
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 無(wú)參構(gòu)造函數(shù)，默認(rèn)數(shù)組大小為0
*/
public Array() {
this(10);
}
}
使用泛型的原因：使用泛型后可以將當(dāng)前順序表中存儲(chǔ)對(duì)象，如果不使用泛型的話只能使用自己指定類型的數(shù)據(jù)，擴(kuò)展性不強(qiáng)。因此使用泛型后可以將當(dāng)前順序表的使用擴(kuò)展到所有類對(duì)象，只需要在創(chuàng)建時(shí)指定相應(yīng)的對(duì)象即可。
2. 獲取順序表的元素個(gè)數(shù)
/**
* 獲取數(shù)組中的元素個(gè)數(shù)
*
* @return 數(shù)組當(dāng)前的元素個(gè)數(shù)
*/
public int getSize() {
return size;
}對(duì)于獲取當(dāng)前順序表中的元素個(gè)數(shù)來(lái)說(shuō)，因?yàn)槲覀兌x的初始成員變量size代表的含義就是當(dāng)前順序表的元素個(gè)數(shù)，但是size變量的本質(zhì)為當(dāng)前順序表的指針，指向順序表最后一個(gè)元素的下一個(gè)位置 （元素的索引從0開始，最后一個(gè)元素的索引值比元素個(gè)數(shù)值小 1），不能直接進(jìn)行修改，因此要想獲取需要通過(guò)size元素的getter方法
同樣地，對(duì)于獲取順序表的元素個(gè)數(shù)只需要將size返回即可
3. 獲取順序表當(dāng)前的容量
/**
* 獲取數(shù)組當(dāng)前容量
*
* @return 數(shù)組當(dāng)前容量
*/
public int getCapacity() {
return data.length;
}在對(duì)順序表進(jìn)行聲明的時(shí)候，就已經(jīng)將用戶傳來(lái)的或者默認(rèn)的初始容量capacity作為數(shù)組的大小對(duì)data泛型數(shù)組進(jìn)行了初始化，因此當(dāng)前data的length屬性就是傳來(lái)的capacity，（或者在后面進(jìn)行動(dòng)態(tài)擴(kuò)容或縮容時(shí)，data.length是一直不會(huì)改變的，改變的只有size） 因此獲取順序表當(dāng)前的容量將data.length返回即可
4. 順序表是否為空
/**
* 判斷數(shù)組是否為空
*
* @return 數(shù)組是否為空
*/
public boolean isEmpty() {
return size == 0;
}我們知道size代表的是順序表中的元素個(gè)數(shù)，因此要判斷當(dāng)前順序表是否為空僅需要將size是否等于0進(jìn)行返回即可
5. 在指定索引位置添加元素
/**
* 向數(shù)組中索引為index位置添加元素e
*
* @param index 索引位置
* @param e 元素e
*/
public void add(int index, E e) {
// 判斷數(shù)組空間是否已滿
if (size == data.length) {
// 對(duì)數(shù)組進(jìn)行擴(kuò)容
resize(2 * data.length);
}
// 越界判斷
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}當(dāng)向順序表中指定索引位置添加元素時(shí)要考慮以下幾個(gè)問(wèn)題：
- 當(dāng)前順序表中是否還有容量？
- 添加的元素索引值是否越界？
對(duì)于第一個(gè)問(wèn)題來(lái)說(shuō)，當(dāng)順序表已滿沒有容量時(shí)，再進(jìn)行添加元素時(shí)需要進(jìn)行動(dòng)態(tài)的擴(kuò)容，resize方法的作用就是對(duì)數(shù)組進(jìn)行動(dòng)態(tài)的擴(kuò)容以及縮容，對(duì)于resize方法的實(shí)現(xiàn)我們放到后面進(jìn)行具體的講解，在這里我們知道如果當(dāng)前順序表容量已滿，將順序表容量擴(kuò)大為當(dāng)前順序表容量的二倍
第二個(gè)問(wèn)題的出現(xiàn)情況只有兩種，索引小于0或索引超過(guò)了當(dāng)前順序表中的元素個(gè)數(shù)時(shí)，拋出運(yùn)行時(shí)異常即可
在索引沒有問(wèn)題后，添加元素的過(guò)程如下圖所示：
要先將要添加的索引位置后的所有元素依次向后移動(dòng)一位，在移動(dòng)完成后將當(dāng)前索引位置的元素使用要進(jìn)行添加的元素對(duì)當(dāng)前位置的元素進(jìn)行覆蓋即可，同時(shí)添加完元素后將size++，維護(hù)指針變量
6. 在順序表末尾添加元素
/**
* 在數(shù)組末尾添加一個(gè)元素
*
* @param e 要添加的元素
*/
public void addLast(E e) {
add(size, e);
}在末尾添加元素可以對(duì)之前寫好的向指定索引位置添加元素的代碼進(jìn)行復(fù)用，同時(shí)在add方法中進(jìn)行了校驗(yàn)，因此對(duì)于擴(kuò)容以及索引都問(wèn)題都無(wú)需我們進(jìn)行考慮，將 索引位置的參數(shù)賦值為當(dāng)前最后一個(gè)元素的下一個(gè)位置size 后直接調(diào)用即可。
7. 在順序表頭部添加元素
/**
* 在數(shù)組的頭部添加元素e
*
* @param e 要添加的元素
*/
public void addFirst(E e) {
add(0, e);
}在順序表的頭部添加元素也是同樣的道理，對(duì)指定索引位置插入元素進(jìn)行復(fù)用即可，在此不進(jìn)行贅述。
8. 獲取指定索引位置的元素
/**
* 獲取索引為index位置的元素
*
* @param index 索引位置
* @return 索引為index位置的元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return data[index];
}獲取指定索引位置的元素與之前在指定索引位置插入元素的思路大體一致，但是要更簡(jiǎn)單一些，無(wú)需考慮順序表擴(kuò)容以及縮容的問(wèn)題，僅需要考慮傳入的索引值是否合法，如果傳入的索引值合法則直接將對(duì)應(yīng)位置的元素進(jìn)行返回即可。
9. 獲取順序表第一個(gè)元素
/**
* 獲取數(shù)組中第一個(gè)元素
*
* @return 數(shù)組中第一個(gè)元素
*/
public E getFirst() {
return get(0);
}在實(shí)現(xiàn)了獲取指定索引位置的元素后，獲取順序表的第一個(gè)元素同樣是對(duì)get方法的復(fù)用，將0做為索引值進(jìn)行參數(shù)傳遞即可。
10. 獲取順序表最后一個(gè)元素
/**
* 獲取數(shù)組中最后一個(gè)元素
*
* @return 數(shù)組中最后一個(gè)元素
*/
public E getLast() {
return get(size - 1);
}獲取順序表最后一個(gè)元素也是對(duì)get方法的復(fù)用，在此不進(jìn)行贅述
11. 修改指定索引位置的元素
/**
* 設(shè)置索引為index位置的元素值為e
*
* @param index 索引位置
* @param e 要進(jìn)行替換的元素值
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
data[index] = e;
}在之前獲取指定索引位置的元素時(shí)，先判斷索引是否合法，如果合法將對(duì)應(yīng)位置的元素進(jìn)行返回。同理，先判斷索引位置是否合法，如果合法就將當(dāng)前位置的元素使用我們接收到的元素e進(jìn)行替換。
12. 判斷順序表中是否包含指定元素
/**
* 判斷數(shù)組中是否存在元素e
*
* @param e 元素e
* @return 是否存在元素e
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}對(duì)于判斷順序表中是否存在指定元素來(lái)說(shuō)，對(duì)順序表進(jìn)行線性查找，如果找到了相應(yīng)的數(shù)據(jù)，就返回true，如果在對(duì)順序表遍歷結(jié)束后仍然沒有找到指定元素，說(shuō)明當(dāng)前順序表中不存在指定元素，返回false
注意：在這里因?yàn)槭?strong>對(duì)象的比較，使用equals方法進(jìn)行比較，如果是基本數(shù)據(jù)類型（如int，double等）的比較就要使用==來(lái)進(jìn)行比較
13. 獲取順序表中指定元素的索引
/**
* 查找數(shù)組中元素e的索引，如果不存在返回 -1
*
* @param e 元素e
* @return 元素e在數(shù)組中的索引
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}獲取指定元素的索引同樣使用線性查找法，使用equals進(jìn)行比較，如果找到相同的元素則返回對(duì)應(yīng)的索引值，如果遍歷完順序表后仍然沒有找到指定元素則返回-1，說(shuō)明當(dāng)前元素不存在。
14. 刪除指定索引位置的元素
/**
* 刪除索引位置為 index 的元素并返回被刪除的元素
*
* @param index 刪除元素的索引
* @return 被刪除的元素
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
// 先將返回值進(jìn)行存儲(chǔ)
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
// 如果當(dāng)前數(shù)組中的元素不足數(shù)組容量的一半
if (size < data.length / 2) {
// 重新分配空間
resize(data.length / 2);
}
return res;
}在之前進(jìn)行元素的添加時(shí)要考慮順序表是否還有容量，在刪除元素時(shí)不需要考慮是否還有容量，但是也要考慮相應(yīng)的有關(guān)于數(shù)組縮容問(wèn)題。因此要考慮以下問(wèn)題：
- 刪除當(dāng)前元素后，順序表中的元素個(gè)數(shù)是否不足數(shù)組容量的一半？
- 刪除指定索引的元素時(shí)，傳來(lái)的索引值是否合法？
對(duì)于第一個(gè)問(wèn)題的解決方法為在刪除元素后，對(duì)當(dāng)前順序表的元素個(gè)數(shù)與數(shù)組的容量的一半進(jìn)行比較，如果發(fā)現(xiàn)當(dāng)前元素個(gè)數(shù)小于數(shù)組容量的一半時(shí)，我們可以繼續(xù)調(diào)用resize方法重新分配數(shù)組的容量（resize方法在之后會(huì)詳細(xì)解釋），當(dāng)前的實(shí)現(xiàn)結(jié)果就是將數(shù)組的容量縮容至原數(shù)組都一半，對(duì)于內(nèi)存的節(jié)省來(lái)說(shuō)更有好處。
第二個(gè)問(wèn)題解決方式與之前處理一樣，查看索引值是否小于0以及是否大于等于當(dāng)前順序表都元素個(gè)數(shù)
刪除元素的本質(zhì)也是將當(dāng)前索引值的后一個(gè)元素開始，依次向前移動(dòng)，覆蓋掉前一個(gè)元素，最后再將size--，維護(hù)指針，刪除結(jié)束后將臨時(shí)存儲(chǔ)的被刪除的元素返回即可。
刪除元素過(guò)程如下圖所示：
注意：順序表的刪除本質(zhì)上是用后一個(gè)元素將前一個(gè)元素依次覆蓋，移動(dòng)了size指針后此時(shí)指針指向的元素仍然為原本順序表中的最后一個(gè)元素，因?yàn)樵谟脩舻膶?shí)際操作中，size指向的元素?zé)o法被訪問(wèn)到，所以并沒有什么影響。但是我們?cè)谶@里使用了泛型，在Java的GC（垃圾回收機(jī)制）中因?yàn)榇藭r(shí)順序表的最后一個(gè)元素仍然被size指向引用，無(wú)法被回收，因此在這里手動(dòng)執(zhí)行data[size] = null;將當(dāng)前的引用回收。
15. 刪除并返回順序表第一個(gè)元素
/**
* 刪除并返回?cái)?shù)組的第一個(gè)元素
*
* @return 數(shù)組的第一個(gè)元素
*/
public E removeFirst() {
return remove(0);
}與之前的思路一致，在有了刪除指定索引位置的元素方法后，刪除并返回順序表第一個(gè)元素也是對(duì)剛才實(shí)現(xiàn)的remove方法進(jìn)行復(fù)用，在此不做贅述。
16. 刪除并返回順序表最后一個(gè)元素
/**
* 刪除并返回?cái)?shù)組中的最后一個(gè)元素
*
* @return 數(shù)組中的最后一個(gè)元素
*/
public E removeLast() {
return remove(size - 1);
}刪除順序表中最后一個(gè)元素同樣是對(duì)remove方法的復(fù)用，在此也不多做贅述。
17. 刪除順序表中的指定元素
/**
* 從數(shù)組中刪除元素e
*
* @param e 數(shù)組中被刪除的元素
* @return 是否刪除成功
*/
public boolean removeElement(E e) {
int index = find(e);
if (index == -1) {
return false;
}
remove(index);
return true;
}刪除順序表中指定的元素本質(zhì)上是對(duì)之前實(shí)現(xiàn)的獲取順序表中指定元素的索引方法和刪除指定索引位置元素方法的復(fù)用，首先通過(guò)find方法獲取到要?jiǎng)h除元素的索引，接著對(duì)索引進(jìn)行判斷，查看當(dāng)前元素是否存在，如果當(dāng)前元素存在則將獲取到的索引值作為remove方法的參數(shù)傳遞，將當(dāng)前索引位置的元素刪除即可。
18. 對(duì)順序表進(jìn)行動(dòng)態(tài)的擴(kuò)容和縮容
/**
* 對(duì)數(shù)組進(jìn)行擴(kuò)容
*
* @param newCapacity 擴(kuò)容后數(shù)組的容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}在之前向順序表中添加元素以及刪除順序表中的元素都涉及到了擴(kuò)容以及縮容的過(guò)程，其實(shí)對(duì)于擴(kuò)容以及縮容來(lái)說(shuō)區(qū)別只體現(xiàn)在了傳遞來(lái)的參數(shù)與原數(shù)組容量大小的差別，擴(kuò)容與縮容的思路都是聲明一個(gè)新的數(shù)組，初始容量的大小為傳遞來(lái)的參數(shù)，接著遍歷原來(lái)的數(shù)組，將每一個(gè)元素依次填充到新的數(shù)組中，之后再將data對(duì)象的引用指向新的數(shù)組newData即可。
三、運(yùn)行結(jié)果
在進(jìn)行結(jié)果測(cè)試前，為了方便于觀察，在這里我重寫了Array類的toString方法
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
四、總結(jié)
以上便是Java語(yǔ)言對(duì)線性表的順序表示和實(shí)現(xiàn)，和以前使用C語(yǔ)言來(lái)寫順序表最大的感受就是曾經(jīng)覺得很難寫、很費(fèi)腦的代碼再次實(shí)現(xiàn)時(shí)感覺變得很容易了，同時(shí)對(duì)于很多的方法也有了復(fù)用的思想，對(duì)線性表的理解更加深刻。高興于自己成長(zhǎng)的同時(shí)也更加深刻意識(shí)到以后的路會(huì)更加的艱難，希望自己可以在未來(lái)的道路上戒驕戒躁、穩(wěn)扎穩(wěn)打，哪怕再困難，也不會(huì)放棄！
源碼
以下是源代碼
1. Array類源代碼
package net.csdn.array;
/**
* @author zhangrongkang
* @date 2022/6/26
*/
public class Array<E> {
private E[] data;
/**
* 數(shù)組中元素的數(shù)量
*/
private int size;
/**
* 構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造數(shù)組
*
* @param capacity 初始數(shù)組大小
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 無(wú)參構(gòu)造函數(shù)，默認(rèn)數(shù)組大小為0
*/
public Array() {
this(10);
}
/**
* 獲取數(shù)組中的元素個(gè)數(shù)
*
* @return 數(shù)組當(dāng)前的元素個(gè)數(shù)
*/
public int getSize() {
return size;
}
/**
* 獲取數(shù)組當(dāng)前容量
*
* @return 數(shù)組當(dāng)前容量
*/
public int getCapacity() {
return data.length;
}
/**
* 判斷數(shù)組是否為空
*
* @return 數(shù)組是否為空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在數(shù)組末尾添加一個(gè)元素
*
* @param e 要添加的元素
*/
public void addLast(E e) {
add(size, e);
}
/**
* 在數(shù)組的頭部添加元素e
*
* @param e 要添加的元素
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 向數(shù)組中索引為index位置添加元素e
*
* @param index 索引位置
* @param e 元素e
*/
public void add(int index, E e) {
// 判斷數(shù)組空間是否已滿
if (size == data.length) {
// 對(duì)數(shù)組進(jìn)行擴(kuò)容
resize(2 * data.length);
}
// 越界判斷
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
/**
* 獲取索引為index位置的元素
*
* @param index 索引位置
* @return 索引為index位置的元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return data[index];
}
/**
* 獲取數(shù)組中第一個(gè)元素
*
* @return 數(shù)組中第一個(gè)元素
*/
public E getFirst() {
return get(0);
}
/**
* 獲取數(shù)組中最后一個(gè)元素
*
* @return 數(shù)組中最后一個(gè)元素
*/
public E getLast() {
return get(size - 1);
}
/**
* 設(shè)置索引為index位置的元素值為e
*
* @param index 索引位置
* @param e 要進(jìn)行替換的元素值
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
data[index] = e;
}
/**
* 判斷數(shù)組中是否存在元素e
*
* @param e 元素e
* @return 是否存在元素e
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
/**
* 查找數(shù)組中元素e的索引，如果不存在返回 -1
*
* @param e 元素e
* @return 元素e在數(shù)組中的索引
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
/**
* 刪除索引位置為 index 的元素并返回被刪除的元素
*
* @param index 刪除元素的索引
* @return 被刪除的元素
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
// 先將返回值進(jìn)行存儲(chǔ)
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
// 如果當(dāng)前數(shù)組中的元素不足數(shù)組容量的一半
if (size < data.length / 2) {
// 重新分配空間
resize(data.length / 2);
}
return res;
}
/**
* 刪除并返回?cái)?shù)組的第一個(gè)元素
*
* @return 數(shù)組的第一個(gè)元素
*/
public E removeFirst() {
return remove(0);
}
/**
* 刪除并返回?cái)?shù)組中的最后一個(gè)元素
*
* @return 數(shù)組中的最后一個(gè)元素
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 從數(shù)組中刪除元素e
*
* @param e 數(shù)組中被刪除的元素
* @return 是否刪除成功
*/
public boolean removeElement(E e) {
int index = find(e);
if (index == -1) {
return false;
}
remove(index);
return true;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
/**
* 對(duì)數(shù)組進(jìn)行擴(kuò)容
*
* @param newCapacity 擴(kuò)容后數(shù)組的容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}2. 測(cè)試類源代碼
package net.csdn.array;
/**
* @author zhangrongkang
* @date 2022/6/26
*/
public class ArrayMain {
public static void main(String[] args) {
System.out.println("聲明新的順序表，初始容量為10：");
Array<Integer> array = new Array<>(10);
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array + "\n");
System.out.println("向索引為 1 的位置添加元素 100：");
array.add(1, 100);
System.out.println(array + "\n");
System.out.println("在順序表的頭部添加 -1：");
array.addFirst(-1);
System.out.println(array + "\n");
System.out.println("在順序表的尾部添加 101：");
array.addLast(101);
System.out.println(array + "\n");
System.out.println("移除索引位置為 2 的元素：");
array.remove(2);
System.out.println(array + "\n");
System.out.println("移除順序表中的元素 4：");
array.removeElement(4);
System.out.println(array + "\n");
System.out.println("移除順序表中的第一個(gè)元素：");
array.removeFirst();
System.out.println(array + "\n");
System.out.println("移除順序表中的最后一個(gè)元素：");
array.removeLast();
System.out.println(array + "\n");
System.out.println("元素7的索引位置為：" + array.find(7));
System.out.println("數(shù)組中是否包含元素4：" + array.contains(4));
}
}
到此這篇關(guān)于Java線性表的順序表示及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java線性表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- java線性表的存儲(chǔ)結(jié)構(gòu)及其代碼實(shí)現(xiàn)
- java 線性表接口的實(shí)例詳解
- java實(shí)現(xiàn)線性表及其算法
- Java實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)
- Java中ArrayList與順序表的概念與使用實(shí)例
- Java數(shù)據(jù)結(jié)構(gòu)之順序表篇
- Java實(shí)現(xiàn)順序表的操作
- Java實(shí)現(xiàn)順序表和鏈表結(jié)構(gòu)
- Java?精煉解讀數(shù)據(jù)結(jié)構(gòu)的順序表如何操作
- Java數(shù)據(jù)結(jié)構(gòu)順序表從零基礎(chǔ)到精通進(jìn)階
相關(guān)文章
Java使用類創(chuàng)造新的類型(type)，并使用繼承來(lái)便利我們創(chuàng)建類。再深一層講類型，并是多態(tài)(polymorphism)的概念。本文將給大家介紹Java 的類型轉(zhuǎn)換與多態(tài)，需要的小伙伴可以參考下面文章的具體內(nèi)容2021-09-09
這篇文章主要介紹了Java責(zé)任鏈模式定義與用法,結(jié)合具體實(shí)例分析了java責(zé)任鏈模式的功能、定義、使用方法、適用情況等,需要的朋友可以參考下2017-06-06
Java8新特性之lambda的作用_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
我們期待了很久lambda為java帶來(lái)閉包的概念，但是如果我們不在集合中使用它的話，就損失了很大價(jià)值。現(xiàn)有接口遷移成為lambda風(fēng)格的問(wèn)題已經(jīng)通過(guò)default methods解決了，在這篇文章將深入解析Java集合里面的批量數(shù)據(jù)操作解開lambda最強(qiáng)作用的神秘面紗。2017-06-06
有關(guān)tomcat內(nèi)存溢出的完美解決方法
下面小編就為大家?guī)?lái)一篇有關(guān)tomcat內(nèi)存溢出的完美解決方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-05-05
HttpServletRequest對(duì)象方法的用法小結(jié)
HttpServletRequest對(duì)象代表客戶端的請(qǐng)求，當(dāng)客戶端通過(guò)HTTP協(xié)議訪問(wèn)服務(wù)器時(shí)，HTTP請(qǐng)求頭中的所有信息都封裝在這個(gè)對(duì)象中，開發(fā)人員通過(guò)這個(gè)對(duì)象的相關(guān)方法，即可以獲得客戶的這些信息2017-03-03
java:程序包c(diǎn)om.xxx.xxx不存在報(bào)錯(cuò)萬(wàn)能解決辦法
這篇文章主要給大家介紹了關(guān)于java:程序包c(diǎn)om.xxx.xxx不存在報(bào)錯(cuò)萬(wàn)能解決辦法,這個(gè)問(wèn)題曾逼瘋初學(xué)者的我,不過(guò)弄清楚原理后就很簡(jiǎn)單了,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12
SpringBoot實(shí)現(xiàn)redis延遲隊(duì)列的示例代碼
延時(shí)隊(duì)列場(chǎng)景在我們?nèi)粘I(yè)務(wù)開發(fā)中經(jīng)常遇到,它是一種特殊類型的消息隊(duì)列,本文就來(lái)介紹一下SpringBoot實(shí)現(xiàn)redis延遲隊(duì)列的示例代碼,具有一定的參考價(jià)值,感興趣的可以了解一下2024-02-02
關(guān)于SpringBoot集成Lettuce連接Redis的方法和案例
這篇文章主要介紹了關(guān)于SpringBoot集成Lettuce連接Redis的方法和案例,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
這篇文章主要為大家詳細(xì)介紹了Java模擬實(shí)現(xiàn)ATM機(jī)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-03-03
Springboot升級(jí)至2.4.0中出現(xiàn)的跨域問(wèn)題分析及修改方案
這篇文章主要介紹了Springboot升級(jí)至2.4.0中出現(xiàn)的跨域問(wèn)題分析及修改方案,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12