引入:

數(shù)據(jù)結(jié)構(gòu)的分類，數(shù)據(jù)結(jié)構(gòu)可以分成：線性表，樹形結(jié)構(gòu)，圖形結(jié)構(gòu)。

• 線性結(jié)構(gòu)(線性表)包括:數(shù)組、鏈表、棧隊(duì)列

• 樹形結(jié)構(gòu):二叉樹、AVL樹、紅黑樹、B樹、堆、Trie、哈夫曼樹、并查集

• 圖形結(jié)構(gòu):鄰接矩陣、鄰接表

線性表是具有存儲(chǔ)n個(gè)元素的線性序列，常見的線性表有順序表(數(shù)組)和鏈表兩種實(shí)現(xiàn)方式。

為什么會(huì)出現(xiàn)ArrayList動(dòng)態(tài)數(shù)組？

• 在很多開發(fā)語言中數(shù)組有一個(gè)致命的缺點(diǎn)，就是數(shù)組的長度一旦確定，就不能再更改。
• 我們?cè)趯?shí)際的開發(fā)中，更希望數(shù)組是可變的。

這個(gè)時(shí)候我們就可以使用數(shù)組去封裝一個(gè)動(dòng)態(tài)數(shù)組，java中的ArrayList的出現(xiàn)就是為了彌補(bǔ)數(shù)組長度不可變的缺點(diǎn)。

ArrayList的實(shí)現(xiàn)：

我們要對(duì)數(shù)組進(jìn)行封裝，也就是讓這個(gè)數(shù)組如果元素裝滿了之后，重新創(chuàng)建一個(gè)更大的數(shù)組，將原來的元素復(fù)制過去。

分析:

實(shí)現(xiàn)動(dòng)態(tài)數(shù)組，我們要?jiǎng)?chuàng)建一個(gè)類叫做ArrayList,因?yàn)樗艽鎯?chǔ)所有引用類型的元素，我們要給它加一個(gè)泛型/，它要能動(dòng)態(tài)獲取它存儲(chǔ)的元素的數(shù)量，所以它可以得到它應(yīng)該有一個(gè)size成員，既然是一個(gè)動(dòng)態(tài)數(shù)組，它的類成員一定有一個(gè)容器數(shù)組elements。這樣我們就可以確定兩個(gè)成員size和elements;

這個(gè)動(dòng)態(tài)數(shù)組需要?jiǎng)?chuàng)建，所以我們得提供構(gòu)造方法，既然它底層還是數(shù)組，那么創(chuàng)建的時(shí)候還是需要指定大小，可以自定義也可以創(chuàng)建一個(gè)默認(rèn)大小的數(shù)組。java底層默認(rèn)創(chuàng)建的是一個(gè)大小為10的數(shù)組。

package com.lut.dynamicArray;public class ArrayList<E> {//所裝元素的數(shù)量public int size;//數(shù)組private E[] elements;//創(chuàng)建ArrayList底層數(shù)組默認(rèn)的大小private static final int DEFAULT_CAPACITY = 10;//構(gòu)造方法，自定義初始的ArrayList的大小，和java.util.ArrayList實(shí)現(xiàn)有所不同，可以自己進(jìn)源碼查看public ArrayList(int capacity){capacity = (capacity < DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;elements = (E[]) new Object[capacity];}public ArrayList(){//elements=new int[DEFAULT_CAPACITY];this(DEFAULT_CAPACITY);}
}

接口(方法)分析：

? 這個(gè)類已經(jīng)創(chuàng)建出來了，我們就需要向外界提供操作這個(gè)動(dòng)態(tài)數(shù)組的方法。比如必須能夠向這個(gè)ArrayList的對(duì)象里面添加元素、刪除元素、按索引查找元素、按元素查索引、獲取這個(gè)對(duì)象里面存儲(chǔ)的元素個(gè)數(shù)等可以操作的方法。

? 它至少包括以下方法:

int size();// 元素的數(shù)量
boolean isEmpty(); // 是否為空
boolean contains(E element);// 是否包含某個(gè)元素
void add(E element);// 添加元素到最后面
E get(int index);/返回index位置對(duì)應(yīng)的元素
E set(int index, E element);//設(shè)置index位置的元素
void add(int index, E element);//往index位置添加元素
E remove(int index);// 刪除index位置對(duì)應(yīng)的元素
int index0f(E element);// 查看元素的位置
void clear();// 清除所有元素

需要注意的是，我們需要通過add方法不斷地向ArrayList的對(duì)象里面添加元素，如果元素操作了我們創(chuàng)建ArrayList指定的大小，這個(gè)時(shí)候就需要擴(kuò)容，所以我們?cè)谔砑釉刂?#xff0c;需要調(diào)用ensureCapacity方法（這個(gè)方法只是為了方便理解，官方方法寫的很復(fù)雜，名字也不叫ensureCapacity，不夠調(diào)用的時(shí)機(jī)和位置一樣），確保下一個(gè)元素不會(huì)索引越界，如果越界就需要進(jìn)行擴(kuò)容處理，擴(kuò)容是直接在原數(shù)組的大小基礎(chǔ)上擴(kuò)大1.5倍。

我們?cè)诓檎以氐臅r(shí)候或者是按索引添加元素的時(shí)候可能存在索引大于了ArrayList的默認(rèn)的size或者為負(fù)數(shù)等不合理的輸入，這個(gè)時(shí)候我們需要在這些方法前面調(diào)用一個(gè)rangeCheck(index)函數(shù)，確保傳入的索引合適，而添加的時(shí)候索引可以比size大1，所以單獨(dú)定義了一個(gè)rangeCheckForAdd(index),如果rangeCheck或者rangeCheckForAdd方法在檢查索引發(fā)現(xiàn)不合適的時(shí)候就會(huì)調(diào)用outOfBounds方法。

下面是自定義低配版ArrayList的簡單實(shí)現(xiàn)

private void ensureCapacity(int capacity) {int oldCapacity = elements.length;if(oldCapacity>=capacity) return;//新容量為舊容量的1.5倍int newCapacity = oldCapacity+(oldCapacity >> 1);//位運(yùn)算右移1除以2，相當(dāng)于舊容量1.5倍，相反左移1相當(dāng)于乘以2E[] newElements = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newElements[i]=elements[i];}elements=newElements;System.out.println(oldCapacity+"擴(kuò)容為:"+newCapacity);
}

下面對(duì)ArrayList進(jìn)行了簡單的實(shí)現(xiàn)

package com.lut.dynamicArray;@SuppressWarnings("unchecked")
public class ArrayList<E> {//元素的數(shù)量public int size;//所有的元素private E[] elements;//static能保證內(nèi)存中只有一份此數(shù)據(jù)private static final int DEFAULT_CAPACITY = 10;//元素是否找到private static final int ELEMENT_NOT_FOUND = -1;public ArrayList(int capacity){capacity = (capacity < DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;elements = (E[]) new Object[capacity];//釋放時(shí)機(jī)和外面的ArrayList同時(shí)釋放}public ArrayList(){this(DEFAULT_CAPACITY);}/*** 清楚所有元素*/public void clear(){for (int i = 0; i < size; i++) {elements[i] = null;}size = 0;}/*** 元素的數(shù)量* @return*/public int size(){return size;}/*** 是否為空* @return*/public boolean isEmpty(){return size==0;}/*** 是否包含某個(gè)元素* @param element* @return*/public  boolean contains(E element){return indexOf(element) != ELEMENT_NOT_FOUND;}/*** 添加到元素尾部*/public void add(E element){add(size,element);}/*** 獲取index位置的元素*/public E get(int index){rangeCheck(index);return elements[index];}/*** 設(shè)置index位置的元素* @return 原來的元素*/public E set(int index,E element){rangeCheck(index);E old = elements[index];elements[index] = element;return old;}/*** 在index位置插入一個(gè)元素*/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++;}/*** 刪除index位置的元素* @return 返回刪除的元素*/public E remove(int index){rangeCheck(index);E temp = elements[index];for (int i = index+1; i < size; i++) {elements[i-1]=elements[i];}//size--;elements[--size] = null;return temp;}/*** 查看元素的索引，沒找到返回-1*/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++) {//未重寫的equals方法，就是默認(rèn)比較的兩個(gè)對(duì)象的地址if(element.equals(elements[i])) return i;}}return ELEMENT_NOT_FOUND;}/*** 保證要有capacity的容量* @param capacity*/private void ensureCapacity(int capacity) {int oldCapacity = elements.length;if(oldCapacity>=capacity) return;//新容量為舊容量的1.5倍int newCapacity = oldCapacity+(oldCapacity >> 1);//位運(yùn)算右移1除以2，相當(dāng)于舊容量1.5倍，相反左移1相當(dāng)于乘以2E[] 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 outOfBounds(int index){throw new IndexOutOfBoundsException();}private void rangeCheck(int index){if(index<0||index>=size){outOfBounds(index);}}private void rangeCheckForAdd(int index){if(index<0||index>size){outOfBounds(index);}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size=").append(size).append(",[");for (int i = 0; i < size;java i++) {if(i!=0){string.append(",");}string.append(elements[i]);}string.append("]");return string.toString();}
}

仔細(xì)閱讀上面的代碼我們可以發(fā)現(xiàn)ArrayList有以下缺點(diǎn):

1. 固定大小：ArrayList的大小是固定的，一旦初始化后，無法動(dòng)態(tài)調(diào)整大小，如果需要?jiǎng)討B(tài)增加或減少元素，就需要?jiǎng)?chuàng)建一個(gè)新的數(shù)組elements，并將元素復(fù)制過去，這樣會(huì)增加額外的開銷。
2. 性能問題：在插入或刪除元素時(shí)，ArrayList的elements數(shù)組需要移動(dòng)其他元素來保持連續(xù)性，這會(huì)導(dǎo)致性能下降，尤其是在大型數(shù)據(jù)集上。
3. 內(nèi)存占用：ArrayList在內(nèi)存使用上比較消耗，因?yàn)樗枰~外的空間來存儲(chǔ)元素的索引和容量信息。

那么有沒有和ArrayList一樣的數(shù)據(jù)結(jié)構(gòu)能夠方便元素的插入刪除，同時(shí)能夠靈活的利用內(nèi)存空間呢？有,LinkedList

LinkedList實(shí)現(xiàn)

分析:

LinkedList也是一個(gè)動(dòng)態(tài)的線性表，所以它就必須能夠存儲(chǔ)元素，能夠獲取大小，ArrayList底層是通過一個(gè)數(shù)組存儲(chǔ)元素，LinkedList內(nèi)部是通過一個(gè)結(jié)點(diǎn)類來存儲(chǔ)元素，同時(shí)這個(gè)Node里面有兩個(gè)指針,prev指向前一個(gè)結(jié)點(diǎn)、next指向下一個(gè)結(jié)點(diǎn)，同時(shí)提供一個(gè)構(gòu)造方法，當(dāng)我們需要添加一個(gè)元素的時(shí)候本質(zhì)是添加一個(gè)結(jié)點(diǎn)，再把這個(gè)元素放入到這個(gè)結(jié)點(diǎn)內(nèi)部，同時(shí)維護(hù)好這個(gè)結(jié)點(diǎn)的前后結(jié)點(diǎn)。

所以LinkedList需要兩個(gè)成員至少size和一個(gè)內(nèi)部類Node

Node:

	private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(Node<E> prev, E element, Node<E> next) {this.prev = prev;this.element = element;this.next = next;}}

為了方便獲取頭節(jié)點(diǎn)，我們還需要指定一個(gè)頭結(jié)點(diǎn)，我們需要一個(gè)成員變量Node類型的first

package com.lut.list;public class LinkedList<E>{private Node<E> first;private int size;private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(Node<E> prev, E element, Node<E> next) {this.prev = prev;this.element = element;this.next = next;}}
}

ArrayList和LinkedList我們經(jīng)常使用，ArrayList又叫做動(dòng)態(tài)數(shù)組底層是由數(shù)組實(shí)現(xiàn)的，LinkedList底層是基于鏈表實(shí)現(xiàn)的集合，它們都是線性的數(shù)據(jù)結(jié)構(gòu)。

既然ArrayList和LinkedList都具有相同的方法，我們就可以把這些相同的方法給提取出來成為一個(gè)單獨(dú)的接口，這個(gè)接口就是List接口。

public interface List<E> {//如果元素未找到返回-1static final int ELEMENT_NOT_FOUND = -1;//清除所有元素void clear();//元素的數(shù)量int size();// 是否為空boolean isEmpty();//是否包含某個(gè)元素boolean contains(E element);//添加元素到尾部void add(E element);//獲取index位置的元素E get(int index);//獲取index位置的元素E set(int index, E element);//在index位置插入一個(gè)元素void add(int index, E element);//刪除index位置的元素E remove(int index);//查看元素的索引int indexOf(E element);
}

所以我們只需要去LinkedList去實(shí)現(xiàn)這些接口就可以了，然后對(duì)于LinkedList里面還有一些和ArrayList連實(shí)現(xiàn)都一樣的方法，我們就可以單獨(dú)寫一個(gè)AbstractList/抽象類來復(fù)用相同的方法。

public abstract class AbstractList<E>  {/*** 元素的數(shù)量*/protected int size;/*** 元素的數(shù)量* @return*/public int size() {return size;}/*** 是否為空* @return*/public boolean isEmpty() {return size == 0;}/*** 是否包含某個(gè)元素* @param element* @return*/public boolean contains(E element) {return indexOf(element) != ELEMENT_NOT_FOUND;}/*** 添加元素到尾部* @param element*/public void add(E element) {add(size, element);}protected void outOfBounds(int index) {throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);}protected void rangeCheck(int index) {if (index < 0 || index >= size) {outOfBounds(index);}}javaprotected void rangeCheckForAdd(int index) {if (index < 0 || index > size) {outOfBounds(index);}}
}

現(xiàn)在我們就可以直接實(shí)現(xiàn)專注實(shí)現(xiàn)List里面的不同的方法了。

需要注意理解里面的add方法，添加的時(shí)候，無論是調(diào)用add(E element)還是add(int index,E element),我們調(diào)用的add(E element)方法均會(huì)成為調(diào)用add(int index,E element)方法，原因是 public void add(E element) {add(size, element);}。

還需要注意，如果我們第一次添加的時(shí)候，需要把first指向它

下面是LinkedList的簡單實(shí)現(xiàn):

package com.lut.list;public class LinkedList<E> extends AbstractList<E> implements List<E>{private Node<E> first;private static class Node<E>{E element;Node<E> next;public Node(E element, Node<E> next) {this.element = element;this.next = next;}}@Overridepublic void clear() {size = 0;first = null;}@Overridepublic E get(int index) {return node(index).element;}//復(fù)雜度跟node方法有關(guān)，它的復(fù)雜度為O(n)@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}//O(n)@Overridepublic void add(int index, E element) {if(index == 0){first = new Node<>(element,first);}else{Node<E> prev = node(index - 1);prev.next = new Node<>(element, prev.next);}size++;}//最好:O(1)//最壞:O(n)//平均:O(n)//可以換一個(gè)算法，傳入一個(gè)節(jié)點(diǎn)直接可以刪，這樣才體現(xiàn)鏈表的節(jié)點(diǎn)，增刪快查找慢@Overridepublic E remove(int index) {E old = node(index).element;if(index == 0){first=first.next;}else{Node<E> prev = node(index - 1);prev.next = prev.next.next;}size--;return old;}//O(n)@Overridepublic int indexOf(E element) {if (element == null) {for (int i = 0; i < size; i++) {if (element == node(i).element) {return i;}}} else {for (int i = 0; i < size; i++) {if (element.equals(node(i).element)) {return i;}}}return ELEMENT_NOT_FOUND;}/*** 獲取index位置對(duì)應(yīng)的節(jié)點(diǎn)的對(duì)象*/private Node<E> node(int index){rangeCheck(index);Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size=").append(size).append(",[");for (int i = 0; i < size; i++) {if(i!=0){string.append(",");}string.append(node(i).element);}string.append("]");return string.toString();}
}

ArrayList優(yōu)化:上面我們的ArrayList只是在添加滿的時(shí)候進(jìn)行了擴(kuò)容，但是對(duì)于刪除的時(shí)候我們還需要進(jìn)行縮容，不然會(huì)浪費(fèi)存儲(chǔ)空間?？s容的時(shí)機(jī)是當(dāng)我們刪除元素的時(shí)候，在remove方法之前進(jìn)行判斷是否可以進(jìn)行縮容，如果可以就進(jìn)行縮容操作。

public class ArrayList<E> extends AbstractList<E> implements List<E>{/*** 所有的元素*/private E[] elements;private static final int DEFAULT_CAPACITY = 10;public ArrayList2(int capaticy) {capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;elements = (E[]) new Object[capaticy];}public ArrayList2() {this(DEFAULT_CAPACITY);}/*** 清除所有元素*/public void clear() {for (int i = 0; i < size; i++) {elements[i] = null;}size = 0;// 僅供參考if (elements != null && elements.length > DEFAULT_CAPACITY) {elements = (E[]) new Object[DEFAULT_CAPACITY];}}/*** 獲取index位置的元素* @param index* @return*/public E get(int index) { // O(1)rangeCheck(index);return elements[index]; }/*** 設(shè)置index位置的元素* @param index* @param element* @return 原來的元素?*/public E set(int index, E element) { // O(1)rangeCheck(index);E old = elements[index];elements[index] = element;return old;}/*** 在index位置插入一個(gè)元素* @param index* @param element*/public void add(int index, E element) { /** 最好：O(1)* 最壞：O(n)* 平均：O(n)*/rangeCheckForAdd(index);ensureCapacity(size + 1);for (int i = size; i > index; i--) {elements[i] = elements[i - 1];}elements[index] = element;size++;} // size是數(shù)據(jù)規(guī)模/*** 刪除index位置的元素*/public E remove(int index) {/** 最好：O(1)* 最壞：O(n)* 平均：O(n)*/rangeCheck(index);E old = elements[index];for (int i = index + 1; i < size; i++) {elements[i - 1] = elements[i];}elements[--size] = null;trim();return old;}/*** 查看元素的索引*/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;}/*** 保證要有capacity的容量* @param capacity*/private void ensureCapacity(int capacity) {int oldCapacity = elements.length;if (oldCapacity >= capacity) return;// 新容量為舊容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);// 新容量為舊容量的2倍// int newCapacity = oldCapacity << 1;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 trim() {// 30int oldCapacity = elements.length;// 15int newCapacity = oldCapacity >> 1;if (size > (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) return;// 剩余空間還很多E[] newElements = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newElements[i] = elements[i];}elements = newElements;System.out.println(oldCapacity + "縮容為" + newCapacity);}@Overridepublic String toString() {// size=3, [99, 88, 77]StringBuilder string = new StringBuilder();string.append("size=").append(size).append(", [");for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(elements[i]);}string.append("]");return string.toString();}
}

總結(jié):

ArrayList 和 LinkedList 的區(qū)別是什么?

ArrayList 和 LinkedList 是 Java 中常用的兩種集合類，它們?cè)趯?shí)現(xiàn)上有一些區(qū)別：

1. 內(nèi)部數(shù)據(jù)結(jié)構(gòu)：

   • ArrayList 使用數(shù)組來存儲(chǔ)元素，可以通過索引直接訪問元素，因此查找速度較快，但插入和刪除操作需要移動(dòng)元素，效率較低。
   • LinkedList 使用雙向鏈表來存儲(chǔ)元素，每個(gè)元素都包含對(duì)前一個(gè)和后一個(gè)元素的引用，插入和刪除操作只需改變相鄰元素的引用，效率較高，但查找元素需要遍歷鏈表，效率較低。

2. 內(nèi)存占用：

   • ArrayList 在添加或刪除元素時(shí)可能需要重新分配內(nèi)存空間，因?yàn)閿?shù)組的大小是固定的，可能會(huì)導(dǎo)致內(nèi)存碎片。
   • LinkedList 每個(gè)元素都需要額外的空間來存儲(chǔ)前后元素的引用，可能會(huì)占用更多的內(nèi)存空間。

3. 隨機(jī)訪問和遍歷：

   • ArrayList 支持隨機(jī)訪問，可以通過索引直接訪問元素，適合需要頻繁訪問元素的場景。
   • LinkedList 需要從頭或尾開始遍歷鏈表才能訪問元素，不支持隨機(jī)訪問，適合需要頻繁插入和刪除元素的場景。

綜上所述，如果需要頻繁進(jìn)行插入和刪除操作，可以選擇使用 LinkedList；如果需要頻繁進(jìn)行隨機(jī)訪問操作，可以選擇使用 ArrayList。

ArrayList的擴(kuò)容和縮容是咋做的(基于官方的ArrayList)？

? ArrayList在創(chuàng)建的時(shí)候可以指定一個(gè)數(shù)組的大小，或者默認(rèn)給出一個(gè)長度為10的數(shù)組，當(dāng)我們每次向這個(gè)集合添加元素的時(shí)候，先會(huì)去判斷一下數(shù)組的容量還夠不夠，如果不夠就需要去擴(kuò)容，每次擴(kuò)容會(huì)擴(kuò)容原來容量的1.5倍。

? 而ArrayList 的縮容是自動(dòng)進(jìn)行的，無需手動(dòng)操作。當(dāng) ArrayList 中的元素?cái)?shù)量減少到當(dāng)前容量的一半以下時(shí)，ArrayList 會(huì)自動(dòng)進(jìn)行縮容操作，將容量減半。這樣可以節(jié)省內(nèi)存空間，并提高性能。因此，開發(fā)者無需手動(dòng)調(diào)用任何方法來進(jìn)行 ArrayList 的縮容操作。