1. 什么是數(shù)據(jù)結(jié)構(gòu) ？
- 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)組織數(shù)據(jù)的方式奠涌。
1.1 線(xiàn)性結(jié)構(gòu)
- 數(shù)組、鏈表磷杏、棧溜畅、隊(duì)列、哈希表极祸。
1.2 樹(shù)形結(jié)構(gòu)
- 二叉樹(shù)慈格、AVL樹(shù)、紅黑樹(shù)遥金、B樹(shù)浴捆、堆、Trie稿械、哈夫曼樹(shù)选泻、并查集。
1.3 圖形結(jié)構(gòu)
- 鄰接矩陣美莫、鄰接表页眯。
2. 線(xiàn)性表
- 線(xiàn)性表是有n個(gè)相同類(lèi)型元素的有限序列。（n >= 0）厢呵。
線(xiàn)性表
a1是首節(jié)點(diǎn)（首元素）窝撵，an是尾節(jié)點(diǎn)（尾元素）。
a1 是 a2 的前驅(qū)述吸，a2是a1的后繼忿族。
2.1 常見(jiàn)的線(xiàn)性表
數(shù)組。
鏈表蝌矛。
棧。
隊(duì)列错英。
哈希表(散列表)入撒。
2.2 數(shù)組
- 數(shù)組是一種順序存儲(chǔ)的線(xiàn)性表，所有元素的
內(nèi)存地址都是連續(xù)的椭岩。
數(shù)組
在很多編程語(yǔ)言中茅逮，數(shù)組都有一個(gè)致命的缺點(diǎn)：無(wú)法動(dòng)態(tài)的修改容量。
在實(shí)際開(kāi)發(fā)中判哥，我們希望數(shù)組容量是可以動(dòng)態(tài)改變的献雅。
2.3 動(dòng)態(tài)數(shù)組
動(dòng)態(tài)數(shù)組的簡(jiǎn)單實(shí)現(xiàn) （int類(lèi)型）
-
定義一個(gè)
ArrayList類(lèi)。
- 定義成員和靜態(tài)變量 ：
/**
* 數(shù)組的尺寸
*/
private int size = 0;
/**
* 數(shù)組實(shí)例
*/
private int[] elements;
/**
* 定義一個(gè)默認(rèn)的數(shù)組容量 為 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 元素未找到 返回 -1
*/
private static final int ELEMENT_NOT_FOUNT = -1;
- 定義有參構(gòu)造和無(wú)參構(gòu)造用于初始化數(shù)組：
/**
* 無(wú)參構(gòu)造塌计，通過(guò)this(param) 調(diào)用有參構(gòu)造
*/
public ArrayList() {
// this() 調(diào)用自身有參構(gòu)造函數(shù)
this(DEFAULT_CAPACITY);
}
/**
* 定義有參構(gòu)造方便進(jìn)行初始化
*
* @param capacity
*/
public ArrayList(int capacity) {
// 如果傳遞的容量 小于默認(rèn)的容量將使用默認(rèn)容量 否則使用傳遞的數(shù)組容量
capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
elements = new int[capacity];
}
-
size()方法 返回?cái)?shù)組的長(zhǎng)度：
/**
* 返回?cái)?shù)組中元素的個(gè)數(shù)
*
* @return
*/
public int size() {
return size;
}
-
isEmpty()判斷當(dāng)前數(shù)組是否為空：
/**
* 數(shù)組是否為空
*
* @return
*/
public boolean isEmpty() {
// 判斷size 是不是等于 0 即可 如果size == 0 表示 數(shù)組是空的
return size == 0;
}
-
contains(int element)判斷數(shù)組中是否包含某個(gè)元素：
public boolean contains(T element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
-
void add(int element)向數(shù)組中添加指定的元素:
public void add(int element) {
// size是動(dòng)態(tài)變化的 初始值是 0 添加第一個(gè)元素 在添加完成一個(gè)元素最后將 size + 1 操作
// elements[size++] = element;
// 直接調(diào)用在指定位置添加元素的方法
add(size, element);
}
-
int get(int index)返回指定index處的元素:
public int get(int index) {
// 首先判斷一下傳遞進(jìn)來(lái)的索引值是否合法
rangeCheck(index);
return elements[index];
}
-
int set(int index, int element)設(shè)置index位置的元素為某值,并返回之前的值:
public int set(int index, int element) {
// 首先判斷一下傳遞進(jìn)來(lái)的索引值是否合法
rangeCheck(index);
int old = elements[index];
elements[index] = element;
return old;
}
-
void add(int index, int element)向指定位置添加元素 ：
簡(jiǎn)單圖解
public void add(int index, int element) {
// 這里index的范圍是允許等于size的因?yàn)椴迦氲臅r(shí)候可能是在最后一個(gè)位置插入一個(gè)元素
rangeCheckForAd(index);
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
// 將空出的位置填入值
elements[index] = element;
// size 加一
size++;
}
-
int remove(int index)刪除index位置的元素 并返回刪除的值: 由于數(shù)組的內(nèi)存地址是連續(xù)的挺身，無(wú)法直接挖掉某個(gè)元素，所以必須將數(shù)組進(jìn)行移動(dòng)锌仅，刪除元素章钾。
簡(jiǎn)單圖解
圖中需要將 index = 3 位置的元素 55 刪除 墙贱，需要移動(dòng)的范圍是 [4,6],未移動(dòng)之前的數(shù)組 size = 7 , index = 3. 得出需要移動(dòng)的通項(xiàng) [index + 1 , size - 1]
public int remove(int index) {
rangeCheck(index);
// 記錄一下即將需要?jiǎng)h除的值
int old = elements[index];
// 循環(huán)的范圍就是需要移動(dòng)的元素的范圍 ， 因?yàn)樾枰苿?dòng)這么多個(gè)元素 從 [index + 1,size -1]
for (int i = index + 1; i <= size - 1; i++) {
elements[i - 1] = elements[i];
}
// 長(zhǎng)度減一
size--;
return old;
}
-
int indexOf(int element)查找元素在數(shù)組中的位置:
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (elements[i] == element) {
return i;
}
}
return ELEMENT_NOT_FOUNT;
}
-
void clear()清除數(shù)組中所有元素:
public void clear() {
size = 0;
}
- 重寫(xiě)默認(rèn)的
toString()方法 ：
@Override
public String toString() {
// 字符串拼接使用StringBuilder 提高效率
StringBuilder str = new StringBuilder();
// 拼接格式 size = 3 [88,33,99]
str.append("size = ").append(size).append(" [ ");
for (int i = 0; i < size; i++) {
// 和 i != size -1 對(duì)比優(yōu)先選擇 i != 0, 因?yàn)?size - 1 需要進(jìn)行一次運(yùn)算
if (i != 0) {
str.append(", ");
}
str.append(elements[i]);
}
str.append("]");
return str.toString();
}
15 . 檢查 index 的范圍：
/**
* 檢查index的范圍
*
* @param index
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
// index 是傳遞的索引 >= size 表示該索引已經(jīng)越界
ouOfBound(index);
}
}
/**
* 統(tǒng)一拋出異常
*
* @param index
*/
private void ouOfBound(int index) {
throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
}
- 檢查
index的范圍-添加元素時(shí)是允許size == index:
/**
* 判斷添加元素時(shí)的index 的范圍
*
* @param index
*/
private void rangeCheckForAdd(int index) {
// 添加的時(shí)候可能是添加到了最后一個(gè)元素 所以是允許 index 等于 size的
if (index < 0 || index > size) {
// index 是傳遞的索引 >= size 表示該索引已經(jīng)越界
ouOfBound(index);
}
}
2.4 細(xì)節(jié)優(yōu)化
使用泛型改寫(xiě)動(dòng)態(tài)數(shù)組
@SuppressWarnings("all")
public class ArrayList<T> {
/**
* 記錄的是數(shù)組的尺寸
*/
private int size = 0;
/**
* 定義一個(gè)數(shù)組
*/
private T[] elements;
/**
* 數(shù)組默認(rèn)容量
*/
private final static int DEFAULT_CAPACITY = 10;
/**
* 元素未找到的時(shí)候返回 -1
*/
private final static int ELEMENT_NOT_FOUND = -1;
/**
* 無(wú)參構(gòu)造調(diào)用有參構(gòu)造
*/
public ArrayList() {
this(DEFAULT_CAPACITY);
}
/**
* @param capacicy
*/
public ArrayList(int capacicy) {
// 判斷當(dāng)前傳遞的數(shù)組容量和默認(rèn)的數(shù)組容量 如果傳遞容量小于默認(rèn)的容量就使用默認(rèn)的數(shù)組容量
capacicy = capacicy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacicy;
// 如果是 int 分配的是連續(xù)的四十個(gè)字節(jié)
// 對(duì)象數(shù)組中存儲(chǔ)的是對(duì)象的地址值 因?yàn)椴煌瑢?duì)象大占用的內(nèi)存空間可能是不一樣的
// 對(duì)象不再不引用的時(shí)候就會(huì)被釋放
elements = (T[]) new Object[capacicy];
}
/**
* 返回?cái)?shù)組的尺寸
*
* @return
*/
public int size() {
return size;
}
/**
* 判斷數(shù)組是否為空
*
* @return
*/
public boolean isEmpty() {
// 如果size 等于 0 表示數(shù)組為空
return size == 0;
}
/**
* 判斷數(shù)組中是否存在某個(gè)元素
*
* @param element
* @return
*/
public boolean contains(T element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 向數(shù)組末尾添加一個(gè)元素
*
* @param element
*/
public void add(T element) {
add(size, element);
}
/**
* 向數(shù)組中指定位置添加某個(gè)元素
*
* @param index
* @param element
*/
public void add(int index, T element) {
// 檢查index的范圍
rangeCheckForAdd(index);
// 判斷當(dāng)前的容量進(jìn)行擴(kuò)容操作看看后面一個(gè)位置
ensureCapacity(size + 1);
// 這里的移動(dòng)必須是從后往前移
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size++;
}
/**
* 根據(jù) index 獲取元素
*
* @param index
* @return
*/
public T get(int index) {
rangeCheck(index);
return elements[index];
}
/**
* 將 index 位置的元素設(shè)置為 element 并將原來(lái)的元素返回
*
* @param index
* @param element
* @return
*/
public T set(int index, T element) {
rangeCheckForAdd(index);
// 將舊元素事先保存起來(lái)
T oldElement = elements[index];
elements[index] = element;
return oldElement;
}
/**
* 移除 index 處的元素 并返回被移除的元素
*
* @param index
* @return
*/
public T remove(int index) {
rangeCheck(index);
// 記錄需要?jiǎng)h除的元素
T oldElement = elements[index];
for (int i = index + 1; i <= size - 1; i++) {
elements[i - 1] = elements[i];
}
size--;
// 最后一個(gè)位置的元素 清空
elements[size] = null;
return oldElement;
}
/**
* 返回某個(gè)元素在數(shù)組中的位置
*
* @param element
* @return
*/
public int indexOf(T element) {
for (int i = 0; i < size; i++) {
if (elements.equals(elements)) {
return i;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 清空數(shù)組
* <p>
* 現(xiàn)在泛型的形式 size = 0 已經(jīng)不能這樣寫(xiě)了
* <p>
* 不引用的對(duì)象就會(huì)被銷(xiāo)毀
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null; // 將 數(shù)組中 實(shí)例 與 每個(gè)對(duì)象斷開(kāi)
}
// elements = null; // 直接釋放數(shù)組不可行 贱傀，下次需要再 new 一個(gè)數(shù)組
size = 0;
}
/**
* 判斷index的范圍
*
* @param index
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBound(index);
}
}
private void outOfBound(int index) {
throw new IndexOutOfBoundsException(" index : " + index + " size : " + size);
}
/**
* 適用于添加方法
*
* @param index
*/
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBound(index);
}
}
/**
* 保證數(shù)組的容量
*
* @param capacity
*/
private void ensureCapacity(int capacity) {
// 獲取當(dāng)前數(shù)組元素最大的容量
int oldCapacity = elements.length;
if (oldCapacity > capacity) {
return;
}
// 否則將進(jìn)行擴(kuò)容 擴(kuò)容為原來(lái)的 1.5倍 (oldCapacity >> 1) => (oldCapacity / 2)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 使用新的容量創(chuàng)建一個(gè)新的數(shù)組
T[] newElements = (T[]) new Object[newCapacity];
// 將原數(shù)組中的元素移動(dòng)到新的數(shù)組中
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
// 將原來(lái)的數(shù)組實(shí)例指向新的數(shù)組實(shí)例
elements = newElements;
System.out.println(oldCapacity + "擴(kuò)容為:" + newCapacity);
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append("size = ").append(size).append(" [");
for (int i = 0; i < size; i++) {
if (i != 0) {
str.append(", ");
}
str.append(elements[i]);
}
str.append("] ");
return str.toString();
}
}
創(chuàng)建數(shù)組時(shí)使用所有類(lèi)的父類(lèi) Object 創(chuàng)建對(duì)象數(shù)組
elements = (T[]) new Object[capacicy];
clear() 方法細(xì)節(jié)
對(duì)象數(shù)組
- 對(duì)
clear()方法進(jìn)行優(yōu)化 惨撇。因?yàn)楫?dāng)前數(shù)組中存儲(chǔ)的是對(duì)象，在釋放數(shù)組的資源的時(shí)候需要進(jìn)行如下的處理府寒，防止資源的浪費(fèi)：
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null; // 將 數(shù)組中 實(shí)例 與 每個(gè)對(duì)象斷開(kāi)
}
// elements = null; // 直接釋放數(shù)組不可行 魁衙，下次需要再 new 一個(gè)數(shù)組
size = 0;
}
remove()方法細(xì)節(jié)
- 在移除某個(gè)元素時(shí)，需要將元素從后往前移動(dòng)株搔，最后會(huì)保留最后一個(gè)
size - 1的位置存著一個(gè)之前的對(duì)象纺棺，此時(shí)需要將其進(jìn)行釋放:
public T remove(int index) {
rangeCheck(index);
// 記錄需要?jiǎng)h除的元素
T oldElement = elements[index];
for (int i = index + 1; i <= size - 1; i++) {
elements[i - 1] = elements[i];
}
size--;
// 最后一個(gè)位置的元素 清空
elements[size] = null;
return oldElement;
}
數(shù)組動(dòng)態(tài)擴(kuò)容細(xì)節(jié)
- 當(dāng)在添加元素的時(shí)候需要對(duì)數(shù)組進(jìn)行動(dòng)態(tài)的擴(kuò)容操作：
首先傳遞的參數(shù)為，我們即將添加元素的位置邪狞。將此位置作為標(biāo)準(zhǔn) 和 數(shù)組當(dāng)前的容量進(jìn)行比較祷蝌。
如果當(dāng)前的數(shù)組容量 數(shù)組.length 是大于該位置所需容量的，將直接返回帆卓，否則將進(jìn)行擴(kuò)容操作巨朦。
擴(kuò)容是將數(shù)組擴(kuò)容為原來(lái)的 1.5 倍。之后創(chuàng)建一個(gè)新的數(shù)組對(duì)象剑令，將原數(shù)組中的元素復(fù)制到新數(shù)組中糊啡。
將原數(shù)組的引用指向新的數(shù)組對(duì)象。
/**
* 保證數(shù)組的容量
*
* @param capacity
*/
private void ensureCapacity(int capacity) {
// 獲取當(dāng)前數(shù)組元素最大的容量
int oldCapacity = elements.length;
if (oldCapacity > capacity) {
return;
}
// 否則將進(jìn)行擴(kuò)容 擴(kuò)容為原來(lái)的 1.5倍 (oldCapacity >> 1) => (oldCapacity / 2)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 使用新的容量創(chuàng)建一個(gè)新的數(shù)組
T[] newElements = (T[]) new Object[newCapacity];
// 將原數(shù)組中的元素移動(dòng)到新的數(shù)組中
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
// 將原來(lái)的數(shù)組實(shí)例指向新的數(shù)組實(shí)例
elements = newElements;
System.out.println(oldCapacity + "擴(kuò)容為:" + newCapacity);
}
如何判斷某個(gè)對(duì)象是否被回收
- 重寫(xiě)實(shí)體類(lèi)中的
finalize方法吁津，該方法在對(duì)象被回收之前會(huì)執(zhí)行棚蓄。
@Override
protected void finalize() throws Throwable {
super.finalize();
System.out.println("對(duì)象被回收");
}
- 但是對(duì)象不再被引用是JVM不會(huì)馬上進(jìn)行回收，如果需要進(jìn)行立即回收可以使用如下代碼 :
// 提醒 JVM的垃圾回收機(jī)制 回收垃圾
System.gc();
重寫(xiě)equals() 方法指定比較規(guī)則
-
equals() 方法默認(rèn)比較的是對(duì)象的地址值碍脏。
/**
* 重寫(xiě) equals方法 指定比較規(guī)則
* @param obj
* @return
*/
@Override
public boolean equals(Object obj) {
Person person = (Person) obj;
return this.name == person.name && this.age == person.age;
}
空值處理
- 在可以使用泛型的動(dòng)態(tài)數(shù)組中可能會(huì)出現(xiàn)包含空值的情況梭依，其實(shí)其中的
indexOf()方法就需要進(jìn)行處理。
/**
* 返回某個(gè)元素在數(shù)組中的位置典尾，如果在數(shù)組中是允許存儲(chǔ)空值的在判斷的時(shí)候就需要注意對(duì)空值的處理
*
* @param element
* @return
*/
public int indexOf(T element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) {
return i;
}
}
} else {
// 需要將 element 寫(xiě)在前面 elements[i] 可能會(huì)出現(xiàn)空值 null 如果不進(jìn)行處理的話(huà)可能就會(huì)出現(xiàn)空指針異常
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
優(yōu)化 remove()方法中的循環(huán)條件
- 優(yōu)化前 ：
public T remove(int index) {
rangeCheck(index);
// 記錄需要?jiǎng)h除的元素
T oldElement = elements[index];
for (int i = index + 1; i <= size - 1; i++) {
elements[i] = elements[i - 1];
}
size--;
// 最后一個(gè)位置的元素 清空
elements[size] = null;
return oldElement;
}
- 優(yōu)化后：
public T remove(int index) {
rangeCheck(index);
// 記錄需要?jiǎng)h除的元素
T oldElement = elements[index];
// 原來(lái)的循環(huán)條件 : int i = index + 1; i <= size - 1; i++
for (int i = index; i < size; i++) {
elements[i] = elements[i - 1];
}
size--;
// 最后一個(gè)位置的元素 清空
elements[size] = null;
return oldElement;
}
優(yōu)化 add() 方法中的循環(huán)條件
- 優(yōu)化前：
public void add(int index, T element) {
// 檢查index的范圍
rangeCheckForAdd(index);
// 判斷當(dāng)前的容量進(jìn)行擴(kuò)容操作看看后面一個(gè)位置
ensureCapacity(size + 1);
// 這里的移動(dòng)必須是從后往前移
for (int i = size - 1; i >= index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
- 優(yōu)化后：
public void add(int index, T element) {
// 檢查index的范圍
rangeCheckForAdd(index);
// 判斷當(dāng)前的容量進(jìn)行擴(kuò)容操作看看后面一個(gè)位置
ensureCapacity(size + 1);
// 這里的移動(dòng)必須是從后往前移 原來(lái)的循環(huán)條件 int i = size - 1; i >= index; i--
// 原來(lái)的循環(huán)條件 int i = size - 1; i >= index; i--
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
優(yōu)化Person對(duì)象中的equals()方法
- 對(duì)
equals()方法中添加對(duì)類(lèi)型的檢查役拴，判斷是否屬于當(dāng)前類(lèi)型或其子類(lèi)等。
@Override
public boolean equals(Object obj) {
// 為了嚴(yán)謹(jǐn)起見(jiàn) 需要進(jìn)行以下修改
if (obj == null) {
return false;
}
// 判斷其是否屬于Person類(lèi)型 钾埂，如果是則將其進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換這樣才不會(huì)報(bào)錯(cuò)
if (obj instanceof Person) {
Person person = (Person) obj;
return this.name == person.name && this.age == person.age;
}
return false;
}
