數(shù)組知識點(diǎn)回顧
聲明Java數(shù)組時侧巨，會在內(nèi)存中開辟一塊連續(xù)指定大小的空間稠歉，用來存儲固定大小的同類型元素
在java中定義個名為scores射众，長度為8澎胡，類型為int類型的數(shù)組如下：
public static void main(String[] args) {
int[] scores = new int[8];
}
為了便于理解钮追，我們看下它在內(nèi)存的中的分布示意圖：
圖中的一個個小格子是用來存放數(shù)組的元素预厌，小格子上方的0-7數(shù)字，是數(shù)組中每個元素的下標(biāo)（也可以叫索引）元媚，如果我們要查詢數(shù)組中指定位置的元素轧叽，我們可以通過數(shù)組名[索引]來獲取，比如圖中的scores[2]
在圖中我們還可以看到刊棕，數(shù)組的起始下標(biāo)是從0開始的（也就是第一個元素）炭晒，最后一個元素的下標(biāo)是7(也就是數(shù)組的長度8減1)由此類推，數(shù)組長度若是n甥角，那么數(shù)組最后一個元素的下標(biāo)是n-1（數(shù)組的起始下標(biāo)總是從0開始的）
各位不要閑嘮叨哈网严，為了照顧所有人（其實(shí)我的內(nèi)心是很糾結(jié)的。嗤无。屿笼。??）
自定義數(shù)組類
思路分析
使用data屬性表示存放數(shù)組的元素，
使用capacity屬性表示數(shù)組的容量（等價于數(shù)組的長度）翁巍，但是真正自定義數(shù)組類的時候我們不需要顯示聲明驴一，因?yàn)殡[示等價于（Array.length）
使用size屬性表示數(shù)組中真正存放元素的個數(shù)（注意和capacity概念的區(qū)分）。
我們畫出示意圖：
下面我們來完成初始代碼
public class ArrayExample {
/**
* 存放數(shù)組的元素
*/
private int data[];
/**
* 數(shù)組中元素的個數(shù)
*/
private int size;
/**
* 根據(jù)指定capacity容量初始化數(shù)組
*
* @param capacity 容量
*/
public ArrayExample(int capacity) {
data = new int[capacity];
size = 0;
}
/**
* 無參構(gòu)造函數(shù)灶壶，指定默認(rèn)數(shù)組容量capacity=10
*/
public ArrayExample() {
this(10);
}
/**
* 獲取數(shù)組中元素的個數(shù)
*
* @return
*/
public int getSize() {
return size;
}
/**
* 獲取數(shù)組容量
*
* @return
*/
public int getCapacity() {
return data.length;
}
}
向數(shù)組中添加元素
向指定位置添加元素
假設(shè)現(xiàn)在數(shù)組的形態(tài)是這樣肝断，我們需要將77元素插入到索引為1的位置
思路分析：把當(dāng)前索引為1的位置元素以及后面的元素都向后挪一個位置，然后將77這個元素放到索引為1的位置（注意：挪位置的時候驰凛，我們應(yīng)該從最后一個元素100向后挪一個位置胸懈，換句話說從后往前挪），完成之后恰响，維護(hù)一下size的索引趣钱，進(jìn)行size++操作（size是始終指向數(shù)組中下一個沒有元素的位置）
下面我們基于前面寫的代碼，來完成數(shù)組元素的添加操作
/**
* 在index位置插入元素
*
* @param index 指定索引
* @param element 插入的元素
*/
public void add(int index, int element) {
// 簡單的邊界判斷
if (size == data.length) {
throw new IllegalArgumentException("數(shù)組添加失敗胚宦，數(shù)組已滿");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("index索引不合法");
}
// 從最后一個元素一直到size位置的元素首有，往后挪動一位
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
// 位置賦值
data[index] = element;
// 維護(hù)size大小
size++;
}
由于方面大家查看燕垃，只貼出添加數(shù)組元素的代碼，本文文末井联，會貼出完成的代碼示例地址
現(xiàn)在如果我們想把一個元素添加到數(shù)組頭部的位置或者尾部的位置卜壕，我們可以這么做
/**
* 向數(shù)組頭的位置添加元素
*
* @param element 元素
*/
public void addFirst(int element) {
add(0, element);
}
/**
* 向數(shù)組尾的位置添加元素
*
* @param element 元素
*/
public void addLast(int element) {
add(size, element);
}
大家一定要注重代碼的復(fù)用性哈
查詢數(shù)組元素和修改數(shù)組元素
查詢數(shù)組元素
/**
* 獲取index索引位置的元素
*
* @param index 索引
* @return
*/
public int get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("獲取失敗，索引不合法");
}
return data[index];
}
修改數(shù)組元素
/**
* 修改index索引位置的元素為element
*
* @param index 索引
* @param element 元素
*/
public void set(int index, int element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("獲取失敗烙常，索引不合法");
}
data[index] = element;
}
包含數(shù)組元素和搜索數(shù)組元素
包含數(shù)組元素
/**
* 查找數(shù)組中是否有元素element
*
* @param element
* @return
*/
public boolean contains(int element) {
return Arrays.stream(data).filter(x -> x == element).findAny().isPresent();
}
這里使用了Java8的lambda表達(dá)式轴捎，不知曉的盆友，可以自行去了解一下
搜索數(shù)組元素
/**
* 查找數(shù)組中元素element所在的索引蚕脏，如果不存在元素element侦副，則返回-1
*
* @param element
* @return
*/
public int find(int element) {
for (int i = 0; i < data.length; i++) {
if (data[i] == element) {
return i;
}
}
return -1;
}
刪除數(shù)組中的元素
現(xiàn)在我們要刪除索引為1的元素77
思路分析：我們知曉了數(shù)組的插入思路，那么數(shù)組的刪除思路驼鞭，剛好和數(shù)組的插入思路相反秦驯，如果要刪除索引為1位置的元素77，我們只需要终议，從索引2開始汇竭，將索引2位置的元素向左移動到索引為1的位置，也就是將索引2位置的元素的值賦值給索引為1位置的元素（等價于data[1]=data[2]）穴张，依次類推细燎，將索引為3位置的元素，移動到索引為2位置的元素皂甘，一直到最后一個元素玻驻，比如圖中的元素100，完成之后偿枕，這時候璧瞬，我們需要再次維護(hù)一下size的大小，我們要進(jìn)行size--操作
重要
size既表示數(shù)組中元素的大小渐夸，又表示始終指向數(shù)組中第一個沒有元素的位置
代碼完成數(shù)組的刪除操作
/**
* 刪除索引index位置的元素嗤锉，并將刪除的元素返回
*
* @param index
* @return
*/
public int remove(int index) {
// 簡單判斷數(shù)組索引的合法性
if (index < 0 || index >= size) {
throw new IllegalArgumentException("刪除數(shù)組元素失敗，索引不合法");
}
// 存放刪除指定索引的位置元素
int result = data[index];
// 從刪除指定索引的后一個位置墓塌，一直往前挪一位瘟忱，直到最后一個元素
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// 維護(hù)size的位置
size--;
return result;
}
完成了數(shù)組元素的刪除操作，我們還可以便捷地為數(shù)組添加刪除數(shù)組中第一個元素的方法和刪除數(shù)組中最后一個元的方法苫幢。
刪除數(shù)組中第一個元素的方法
/**
* 刪除數(shù)組中第一個元素访诱，并將刪除的元素進(jìn)行返回
*
* @return
*/
public int removeFirst() {
return remove(0);
}
刪除數(shù)組中最后一個元素的方法
/**
* 刪除數(shù)組中最后一個元素，并將刪除的元素進(jìn)行返回
*
* @return
*/
public int removeLast() {
return remove(size - 1);
}
至此韩肝，我們已經(jīng)完成了數(shù)組的增刪改查操作触菜，下面我們寫個測試類，來使用一下我們自己寫的簡單版數(shù)組
public class ArrayExampleTest {
@Test
public void testAdd() {
// 初始化數(shù)組容量大小為5哀峻，目前數(shù)組中沒有任何元素
ArrayExample arrayExample = new ArrayExample(5);
System.out.println(arrayExample);
// 向數(shù)組中歐添加第一個元素
arrayExample.addFirst(1);
System.out.println(arrayExample);
// 向數(shù)組中添加最后一個元素
arrayExample.addLast(2);
System.out.println(arrayExample);
// 向數(shù)組中索引為0的位置添加元素
arrayExample.add(0, 10);
System.out.println(arrayExample);
}
// TODO 其它測試方法涡相，讀者可以自行測試
}
運(yùn)行結(jié)果
ArrayExample{data=[0, 0, 0, 0, 0], size=0,capacity=5}
ArrayExample{data=[1, 0, 0, 0, 0], size=1,capacity=5}
ArrayExample{data=[1, 2, 0, 0, 0], size=2,capacity=5}
ArrayExample{data=[10, 1, 2, 0, 0], size=3,capacity=5}
完整版代碼GitHub倉庫地址：Java版數(shù)據(jù)結(jié)構(gòu)-數(shù)組 歡迎大家關(guān)注和Star
本次我們完成的是靜態(tài)數(shù)組的實(shí)現(xiàn)哲泊，往往靜態(tài)數(shù)組不夠靈活，后面筆者會在代碼倉庫中實(shí)現(xiàn)動態(tài)數(shù)組漾峡，就不作為一個篇幅來講解了攻旦，接下來喻旷，筆者還會一一的實(shí)現(xiàn)其它常見的數(shù)組結(jié)構(gòu)生逸。
- 靜態(tài)數(shù)組
- 動態(tài)數(shù)組
- 棧
- 隊(duì)列
- 鏈表
- 循環(huán)鏈表
- 二分搜索樹
- 優(yōu)先隊(duì)列
- 堆
- 線段樹
- 字典樹
- AVL
- 紅黑樹
- 哈希表
- ....
持續(xù)更新中，歡迎大家關(guān)注公眾號：小白程序之路（whiteontheroad）且预，第一時間獲取最新信息２郯馈！锋谐！
博客地址：http:www.gulj.cn
