參考書籍《大話數(shù)據(jù)結(jié)構(gòu)》，實現(xiàn)參考JDK1.8
線性表：
Java實現(xiàn)類有ArrayList，LinkedList
ArrayList：
動態(tài)容量數(shù)組的列表旋炒，擴(kuò)展類有序數(shù)組
int size;//數(shù)據(jù)大小
Object[] data;//容量數(shù)組
默認(rèn)數(shù)組是空數(shù)組霎桅，容量為0旅择，默認(rèn)增加容量值是10，DEFAULT_CAPACITY
擴(kuò)容規(guī)則：傳入擴(kuò)容值為minCapacity预麸，若當(dāng)前數(shù)組是空數(shù)組瞪浸，擴(kuò)容值為max(minCapacity,DEFAULT_CAPACITY)，否則判斷minCapacity - size吏祸，若大于0默認(rèn)將當(dāng)前容量 + 當(dāng)前容量擴(kuò)大2倍為newCapacity对蒲，newCapacity若小于minCapacity，容量值為minCapacity贡翘，否則為newCapacity蹈矮，然后進(jìn)行數(shù)組拷貝生成新數(shù)組。
添加/插入：添加時先檢查是否需要擴(kuò)容鸣驱，然后給size+1賦值泛鸟，插入操作是檢查插入位置是否在范圍，不在范圍就拋異常踊东，在范圍進(jìn)行檢查是否需要擴(kuò)容北滥，然后進(jìn)行數(shù)據(jù)移動拷貝arraycopy（data,index,data,index+1,size - index），data[size++] = o闸翅，底層C實現(xiàn)再芋，時間復(fù)雜度O(n)
刪除：檢查刪除位置是否在范圍，然后再進(jìn)行數(shù)據(jù)移動拷貝(data,index + 1,data,index - 1, size - index - 1)坚冀，data[--size] = null
查找/搜索：指定位置查找济赎，O(1)，對象查找indexOf(Object) 順序查找O(n)，
排序：冒泡排序O(n^2)
優(yōu)缺點：順序儲存司训，索引查找快构捡，增刪慢
LinkedList（實現(xiàn)了Deque雙端隊列接口）：
鏈表：動態(tài)容量的雙向鏈?zhǔn)搅斜恚瑪U(kuò)展類有單向鏈表豁遭，循環(huán)鏈表叭喜，雙向鏈表，靜態(tài)鏈表
int size;//數(shù)據(jù)大小
Node<E> first;//頭節(jié)點
Node<E> last;//尾節(jié)點
class Node<E>{
E item;//數(shù)據(jù)元素
Node<E> prev;//節(jié)點前驅(qū)
Node<E> next;//節(jié)點后驅(qū)
}
默認(rèn)是空鏈表蓖谢，容量為0
擴(kuò)容規(guī)則：無數(shù)量限制捂蕴，添加多少元素增加多少節(jié)點，數(shù)量為size
添加/插入：
//默認(rèn)添加是從尾部插入
Node l = last;
Node newNode = (l,o,null);
last = newMode;
if(l== null) first = newNode;
else l.next = newMode;
size++;
//頭部插入
Node l = first闪幽；
Node newNode = (null,o,l);
first = newMode;
if(l == null) last = newMode;
else l.prev = newMode;size++;
查找/搜索：雙向鏈表通過傳入的index/2判斷從頭部還是尾部遍歷搜索啥辨，查找到節(jié)點E，次數(shù)為n/2盯腌，O(n)
刪除：remove()方法默認(rèn)刪除頭部溉知，傳入obj進(jìn)行刪除的話，步驟是先查找到節(jié)點S腕够，然后進(jìn)行鏈接清除
Node prev = s.prev;Node next = s.next;
if(prev != null){prev.next = next;s.prev=null;}else{first=next};
if(next != null){next.prev = prev;s.next=null;}else{last=next};
s.item = null;
size--;
具有Collection的操作方法
add();
remove();
具有隊列Queue的操作方法
peek(),element();
offer();
poll();
E remove();
peek()方法取出隊列頭部元素時候级乍，不刪除該元素，而poll()方法取出元素時會刪除元素帚湘。如果遇到隊列為空的情況是玫荣，兩者都會返回null，element()會拋出異常
雙端隊列Deque(繼承隊列接口大诸，具有棧)的操作方法：
所有的操作方法peekFirst,peekLast.....
push()無空間會拋異常
pop()無元素會拋異常
優(yōu)缺點：不受固定的存儲空間限制捅厂，快速的插入和刪除操作，整塊集合插入為O(1)资柔，查詢效率比順序列表低焙贷，O(n)
棧和隊列：
棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表
隊列是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表
棧/隊列的二種實現(xiàn)：數(shù)組實現(xiàn)棧贿堰，隊列辙芍，鏈表實現(xiàn)簡述（見上面LinkedList）
ArrayDeque
object[] elements;//元素數(shù)組
int head;//頭部數(shù)據(jù)的位置索引
int tail;//尾部數(shù)據(jù)的位置索引
擴(kuò)容規(guī)則：默認(rèn)長度16，傳入值會轉(zhuǎn)換成2^n官边，當(dāng)頭部head == tail時沸手，說明沒有位置可以儲存數(shù)據(jù)，進(jìn)行擴(kuò)容2倍注簿，然后將數(shù)據(jù)拷貝到新數(shù)組頭部契吉，head重新賦值0，tail賦值為原來的數(shù)組長度n
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
添加/插入：設(shè)置后檢測是否需要擴(kuò)容
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
刪除：刪除前后元素時間復(fù)雜度為O(1)诡渴，然后修改head或者tail捐晶，刪除對象會遍歷數(shù)組O(n)菲语，找到相應(yīng)下標(biāo)，然后移動拷貝整個數(shù)組
查找/搜索：獲取前后元素為O(1)
排序：無
優(yōu)缺點：查找元素惑灵，刪除前后元素效率高山上，刪除其他位置O(n)
棧（LIFO,FILO）常用方法是void push()，E pop()英支，操作失敗拋出異常佩憾，默認(rèn)調(diào)用的是addFirst，removeFirst
隊列（FIFO）常用方法是boolean offer(E)干花，E poll()妄帘，操作失敗返回false，null池凄，默認(rèn)調(diào)用的是addLast抡驼，pollFirst
串
零個或多個字符組成的有限序列
String
char[] value;//字符數(shù)組
int hash;//hash值
固定長度，構(gòu)造方法不傳如數(shù)組或串肿仑，默認(rèn)為空串""致盟，不可變類，操作形成新的String對象
操作方法:
String(char[] arr)
String(String str)
String(byte[] bytes)
length()
getChars(char[] buf,int len)
isEmpty()
charAt(int index)
compareTo
startWith
indexOf
subString
replaceAll
split
concat
startWith尤慰，endWitdh
偏移length進(jìn)行普通匹配算法O(n-m+1)
indexOf
普通匹配算法O(n-m+1)*m馏锡，KMP子串匹配算法O(n+m)
replaceAll
正則匹配實現(xiàn)
