零、前言：
一講到裝東西的容器，你可能習慣于使用ArrayList和數組,你有想過ArrayList和數組的差別嗎?
Java的類起名字都不是随便亂起的，一般前面是輔助，後面是實質：
ArrayList = Array + List
就是數組，Array
便是表結構，List
,問題來了，什麼是ArrayList即數組實作的表結構
注：不要問我效果圖用什麼軟體畫的...因為本來就沒用什麼軟體畫。下一節帶你一起表結構
自己畫
!!!
希望你可以和我在Github一同見證：DS4Android的誕生與成長，歡迎star
0.不管别的，先留圖鎮樓：
表結構的正常操作
表結構的正常操作.gif
數組的擴容與縮容
數組的擴容與縮容
1.在我們生活中都有什麼表?
課程表，成績表，作息時間表、列車行程表、手表(這個算了吧...) 複制
2.表有什麼用?
成績表.jpg
可以把同類的對象統一管理，比如成績表:
高三12班的54為同學的成績是對象，對象又包括數學、國文、英語...等屬性
把混亂的54個對象放在一起，這麼一排，哪個是學霸，哪個是學渣一目了然，非常友善
如果其中某個對象的成績改錯了，可以get到對象重新set一下，也非常友善
如果中間一個人作弊了，分數取消，直接remove掉，後面的人名詞往前排,也非常友善
如果高三12班和高三11班要比較成績，兩張表contact一下，就成一張表，合并也很友善 複制
3.表和數組有什麼不同?
打個最恰當的比方就是：而數組相當于列印出來的紙質版
表結構像是Excel中可操作版
1.數組定長：添加新元素，定位添加都很困難
2.拿删除來說：數組remove掉了，後面的人名次都不變----(我還沒個空白名次高，你說氣人不氣人...)
3.表是一種抽象資料類型(Abstract Data Type)，既然是抽象就是規範或功能，表會有不同的實作形式
[番外]：小和尚問老和尚："什麼是聖人?" 老和尚說："好好學習，天天向上，樂于助人，誠信友善"
這裡"聖人"便是一種抽象，"好好學習，天天向上，樂于助人，誠信友善"便是"聖人"的"條件（功能）"，
小和尚按照這麼做了，他就是老和尚眼中的"聖人"，即小和尚實作了聖人。
4.同樣，表是一種抽象，也可以定義你眼中的表，并為它附上add(),get(),set(),remove()等功能
5.其實Java的ArrayList實作了List這個抽象接口 複制
4.數組表結構：本文要務
數組表結構.png
一、定義自己的表結構
由于Java用List,為了不混淆，取了個新名字叫Chart
1.定義表的接口
也就是說說你的表能幹嘛用(接口方法最好注釋非常清晰)
/**
* 作者：張風捷特烈
* 時間：2018/9/25 0025:8:25
* 郵箱：[email protected]
* 說明：線性表結構接口
*/
public interface IChart<T> {
//region -------------添加操作------------
/**
* 定點添加
*
* @param index 索引
* @param el 資料元素
*/
void add(int index, T el);
/**
* 添加尾
*
* @param el 資料元素
*/
void add(T el);
//endregion
//region -------------删除操作------------
/**
* 定位删除
*
* @param index 索引
* @return 删除的元素
*/
T remove(int index);
/**
* 删除尾位
*
* @return 删除的元素
*/
T remove();
/**
* 删除指定元素的第一次出現時
*
* @param el 資料元素
* @return 元素位置
*/
int removeEl(T el);
/**
* 删除所有指定元素
*
* @param el 資料元素
*/
boolean removeEls(T el);
/**
* 清空集合
*/
void clear();
//endregion
//region -------------改查操作------------
/**
* 設定某位置的元素新值
*
* @param index 索引
* @param el 新值
* @return 舊值
*/
T set(int index, T el);
/**
* 根據指定位置擷取元素
*
* @param index 索引
* @return 資料元素
*/
T get(int index);
/**
* 根據指定元素擷取比對索引
*
* @param el 資料元素
* @return 索引集
*/
int[] getIndex(T el);
//endregion
//region ------------其他操作-------------
/**
* 集合是否包含某元素
*
* @param el 資料元素
* @return 是否包含
*/
public boolean contains(T el);
/**
* 連接配接兩個集合
*
* @param iChart 插入集合
* @return 合并後的集合
*/
public IChart<T> contact(IChart<T> iChart);
/**
* 定點連接配接兩個集合
*
* @param index 索引
* @param iChart 插入集合
* @return 合并後的集合
*/
IChart<T> contact(int index, IChart<T> iChart);
/**
* 是否為空
*
* @return 是否為空
*/
boolean isEmpty();
/**
* 傳回集合大小
*
* @return 大小
*/
int size();
/**
* 擷取數組容量
* @return 數組容量
*/
int capacity();
//endregion
} 複制
2.使用數組實作表結構：ArrayChart
實作接口，并實作接口裡的所有方法
/**
* 作者：張風捷特烈<br/>
* 時間：2018/11/21 0021:8:18<br/>
* 郵箱：[email protected]<br/>
* 說明：數組實作線性表結構
*/
public class ArrayChart<T> implements IChart<T> {
//空實作---略
} 複制
3.成員變量和構造初始化
private int size;//表中資料的個數
private T[] data;//資料核心承載體
private static final int DEFAULT_CAPACITY = 10;//預設數組容量
private static final float GROW_RATE = 1.5f;//擴容增長率
public ArrayChart() {
this(DEFAULT_CAPACITY);//無參構造預設建立10個容量的數組
}
public ArrayChart(int capacity) {
data = (T[]) new Object[capacity];//新建立[數組表]時初始化數組
} 複制
4.簡單接口的實作：
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public int capacity() {
return data.length;
} 複制
二、主要方法的實作(CRUD)
1.定點添加元素：
看一下操作圖(将在下一篇:視圖篇完成
)：預設添加到尾部
思路：定點後的所有元素後移一位，空出頂點位，讓待添加元素入駐
紫色框代表空的數組位，中間填充的是表中的實際元素
可見定點添加是在選中索引的前一位添加，是以添加到尾部是add(size,data)來添加
尾添加和定點添加.gif
@Override
public void add(T el) {
add(size , el);//這裡size---是因為在size之前一位添加
}
@Override
public void add(int index, T el) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size");
}
//從最後一個元素開始,到定點位置元素,元素都後移一位
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = el;
size++;
} 複制
addByIndex.png
2.查找與設定值：get(),set()：
set和定索引查詢.gif
@Override
public T set(int index, T el) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed! Make sure index < 0 || index > size");
}
T oldEl = get(index);
data[index] = el;//設定一下，很簡單
return oldEl;
}
@Override
public T get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed! Make sure index < 0 || index > size");
}
return data[index];//查詢數組的對應索引處
} 複制
定值查詢擷取索引
定值查詢擷取索引.gif
@Override
public int[] getIndex(T el) {
int[] tempArray = new int[size];//臨時數組
int count = 0;//重複個數
for (int i = 0; i < size; i++) {//周遊集合,擷取該元素重複個數，及位置數組
if (data[i].equals(el)) {
tempArray[count] = i;
count++;
}
}
//将臨時數組壓縮---排除空位
int[] indexArray = new int[count];
for (int i = 0; i < count; i++) {
indexArray[i] = tempArray[i];
}
return indexArray;//傳回查找元素的索引數組(相當于成績表看數學80分的都有哪些人)
} 複制
3.删除元素：
删除和定點删除.gif
@Override
public T remove() {
return remove(size - 1);
}
@Override
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed! Make sure index < 0 || index > size");
}
T temp = get(index);
//從删除元素索引的下一位開始到結尾，依次左移
// 可簡寫: System.arraycopy(data, index + 1, data, index + 1 - 1, size - index + 1);
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
//置空--遊蕩的對象
data[size] = null;
return temp;
} 複制
其他删除：
定元素删除單個和定元素删除所有相當于前面的組合操作,就不做操作示範了
@Override
public int removeEl(T el) {
int[] indexes = getIndex(el);//查找元素的索引集合，删除首個
int index = -1;
if (indexes.length > 0) {
index = indexes[0];
remove(indexes[0]);
}
return index;
}
@Override
public boolean removeEls(T el) { //查找元素的索引集合,删除所有
int[] indexArray = getIndex(el);
if (indexArray.length != 0) {
for (int i = 0; i < indexArray.length; i++) {
remove(indexArray[i] - i); // 注意-i
}
return true;
}
return false;
} 複制
三、動态擴容與縮容的實作
也沒有什麼高大上的，就是一個籃子裝不下了，裝個更大的籃子裝而已
數組的擴容與縮容
1.擴容與縮容方法的實作
/**
* 擴容/縮容
*
* @param newCapacity 新容量
*/
private void grow(int newCapacity) {
T[] newData = (T[]) new Object[newCapacity];//建立個大籃子
for (int i = 0; i < size; i++) {//把原來的元素放到大籃子裡
newData[i] = data[i];
}
data = newData;
} 複制
2.擴容和縮容的調用契機
什麼時候擴容----籃子不夠裝了呗---add
什麼時候需要縮容----1000個容量的籃子裝1個雞蛋想想也浪費---remove
1) add檢測擴容時機：滿了
@Override
public void add(int index, T el) {
if (size == data.length) {//籃子裝不下了---
grow((int) (GROW_RATE * data.length));//換個1.5倍的籃子
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size");
}
//從最後一個元素開始,到定點位置元素,元素都後移一位
//可簡寫：System.arraycopy(data, index, data, index + 1, size - index);
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = el;
size++;
} 複制
2)remove檢測縮容時機
這裡的判斷标志是留多點備用，不然有可能插入移除頻繁而導緻重複擴容或縮容，
籃子可能會說:"你到底縮還是放，你是不是在玩老子....,老子給你多留點空行了吧!"
@Override
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed! Make sure index < 0 || index > size");
}
T temp = get(index);
//從删除元素索引的下一位開始到結尾，依次左移
// 可簡寫: System.arraycopy(data, index + 1, data, index + 1 - 1, size - index + 1);
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
//置空--遊蕩的對象
data[size] = null;
//縮容----此處限定是為了避免反複出現擴容縮容---可自定義
if (size == data.length / 4 && data.length / 2 != 0 && data.length > 5) {
grow(data.length / 2);
}
return temp;
} 複制
3.清空時，數組縮放到初始值
@Override
public void clear() {
size = 0;
grow(DEFAULT_CAPACITY);
} 複制
四、其他操作
1.是否包含某元素
@Override
public boolean contains(T el) {
return getIndex(el).length != 0;//按值查詢有資料
} 複制
2.contact連接配接數組
表的聯合.png
@Override
public IChart<T> contact(IChart<T> iChart) {
return contact(size - 1, iChart);
}
@Override
public IChart<T> contact(int index, IChart<T> iChart) {
if (!(iChart instanceof ArrayChart)) {//必須是數組才能聯合
return null;
}
//從index處周遊本數組，将待插入資料一個一個插入
for (int i = index; i < index + iChart.size(); i++) {
add(i + 1, iChart.get(i - index));
}
return this;
} 複制
作為一個表結構，基本上就示範這麼多，還有其他操作可以自定義接口，自己實作，
不過不管多麼複雜的操作都是以上操作的組合而已。
五、小結：
關于複雜度的分析，等到所有表結構講完再整體比較一下，這裡先粗略感覺一下
耗時測試
| 方法\操作次數 | 1000 | 10000 | 10W | 100W | 1000W |
|---|---|---|---|---|---|
| add首 | 0.0063秒 | 0.2706秒 | 19.5379秒 | ---- | ---- |
| add尾 | 0.0004秒 | 0.0025秒 | 0.0141秒 | 0.0687秒 | 1.26014秒 |
| remove首 | 0.0063秒 | 0.2771秒 | 19.7902秒 | ---- | ---- |
| remove尾 | 0.0005秒 | 0.0036秒 | 0.0091秒 | 0.02301秒 | :0.1607秒 |
可以看出往開始添加/删除會很困難，從代碼中可以感覺到，畢竟要讓後面所有人挪一挪
想一下如果30000人排一起，第一個人走了，後面所有人往前挪一下，是不是工程量挺大的
要是你決定插到第一個，讓後面的人都往後移一下.....(大哥，活着難道不好嗎....)
是以
頻繁對第一個元素進行操作的，還是不要作死，數組表結構(ArrayList)不适合你