圖片.png
目錄
一洞慎、什么是數(shù)據(jù)結(jié)構(gòu)丹弱？
二庐船、線性表
2.1 數(shù)組（Array）
2.2 動態(tài)數(shù)組(Dynamic Array)接口設(shè)計
2.3 動態(tài)數(shù)組(Dynamic Array)示例
一昆庇、什么是數(shù)據(jù)結(jié)構(gòu)歇万？
概念:數(shù)據(jù)結(jié)構(gòu)是計算存儲揩晴、組織數(shù)據(jù)的方式
在實(shí)際應(yīng)用中，根據(jù)使用場景來選擇最合適的數(shù)據(jù)結(jié)構(gòu)
常見的數(shù)據(jù)結(jié)構(gòu)
二贪磺、線性表線性表
線性表示具有n相同類型元素的有限序列（n>=0）
圖片.png
常見的線性表有
- 數(shù)組
- 鏈表
- 棧
- 隊(duì)列
- 哈希表（散列表）
2.1 數(shù)組（Array）：
int[] array = new int[]{11,2,33};
2.2 動態(tài)數(shù)組(Dynamic Array)接口設(shè)計
? int size(); // 元素的數(shù)量
? boolean isEmpty(); // 是否為空
? boolean contains(E element); // 是否包含某元素
? void add(E element); // 添加元素到最后面
? E get(int index); // 返回index位置對應(yīng)的元素
? E set(int index, E element); // 設(shè)置index位置的元素
? void add(int index, E element); // 往index位置添加元素
? E remove(int index); // 刪除index位置對應(yīng)的元素
? int indexOf(E element); // 查看元素的位置
? void clear(); // 清除所有元素
2.3 動態(tài)數(shù)組(Dynamic Array)示例
動態(tài)數(shù)組的屬性設(shè)計
圖片.png
數(shù)組的常見操作無非就是 增硫兰、刪、查寒锚、改
ArrayList初始化操作
//泛型 可以存放任何數(shù)據(jù)類型（int/string/double）
//java中在定義類的時候就要 定義泛型
//<E> 表示泛型 E:表示類型名 （名字隨便自己冉儆场）
//后面用到E都表示是可以變的 E存放元素的類型
//在java中 所有的類都繼承Object
public class ArrayList<E> {
//成員變量
private int size; //元素的數(shù)量
public E[] elements; //所有的元素
private static final int DEFAULT_CAPACICY = 2;
private static final int ELEMENT_NOT_FOUND = -1;
//初始化
@SuppressWarnings("unchecked")
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACICY)?DEFAULT_CAPACICY:capaticy;
//強(qiáng)制轉(zhuǎn)換
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
this(DEFAULT_CAPACICY);
}
增
/**
* 添加元素到尾部
* */
public void add(E element ) {
add(size, element);
}
/**
* 在index位置插入一個元素
* */
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 ++;
}
圖片.png
刪
/**
* 刪除index位置的元素
* */
public void remove(int index) {
rangeCheck(index);
for (int i = index + 1; i < size; i++) {
elements[i- 1] = elements[i];
}
elements[--size] = null;
}
/**
* 刪除某個元素
* */
public void removeElement(E element) {
remove(indexOf(element));
}
/**
* 清除所有元素
*/
public void clear() {
// elements =null; 與for的區(qū)別
// 推薦使用for 能循環(huán)利用則循環(huán)利用
// elements =null指的是直接將棧空間 向堆空間申請的線斷掉 則堆空間所有數(shù)組刹前、內(nèi)存都清除 那意味著下次又要new一個數(shù)組
// for則表示的是 讓數(shù)組里面指向的對象為null
//清空內(nèi)存
for (int i = 0; i < size; i++) {
elements[i]= null;
}
// elements =null;
size = 0;
}
圖片.png
查
/**
* 獲取index位置的元素
* */
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/**
* 查看元素的索引
* */
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 ;
}
/**
* 元素的數(shù)量
*/
public int size() {
return size;
}
圖片.png
改
/**
* 設(shè)置index位置的元素
* */
public void set(int index,E element) {
rangeCheck(index);
elements[index] = element;
}
圖片.png
其他操作
/**
* 是否為空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某個元素
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
//擴(kuò)容
//保證容量
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return; //不需要擴(kuò)容
//擴(kuò)容 oldCapacity >> 1 等價于 *1.5 但是*1.5比位運(yùn)算耗時間
//新容量為舊容量的1.5倍 oldCapacity >> 1 意思是 >>(右移) /2 泳赋， 如果是 <<(左移) *2
int newCapacity = oldCapacity + (oldCapacity >> 1);
@SuppressWarnings("unchecked")
E[] newElements = (E[])new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity+ "擴(kuò)容為:" + newCapacity);
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
public void rangeCheck(int index) {
if (index<0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
@Override
public String toString() {
//size = 3, [1,2,3]
StringBuilder string = new StringBuilder();
string.append("size = ").append(size).append(", [");
for (int i = 0; i < size; i++) {
//方式一：細(xì)節(jié)處理的更加好一點(diǎn)
if(i != 0) {
string.append(",");
}
string.append(elements[i]);
//方式二：需要做減法操作
// if (i != size - 1) {
// string.append(",");
// }
}
string.append("]");
return string.toString();
}
