轉(zhuǎn)載請標(biāo)明出處，謝謝！
http://www.itdecent.cn/p/3aeb5998e79e
關(guān)聯(lián)文章
冒泡、選擇排序 http://www.itdecent.cn/p/176b0b892591
棧和隊(duì)列 http://www.itdecent.cn/p/8cb602ef4e21
順序表、單雙鏈表 http://www.itdecent.cn/p/3aeb5998e79e
二叉樹 http://www.itdecent.cn/p/de829eab944c
圖論 http://www.itdecent.cn/p/cf03e51a3ca2
順序表
在順序表中，最常見的操作當(dāng)然是查找（搜索），插入和刪除了，現(xiàn)在對這三種操作的復(fù)雜度進(jìn)行簡要的分析。
第一，搜索：
順序表的順序搜索算法，它的主要內(nèi)容就是從順序表的第一項(xiàng)開始，根據(jù)要查找的給定值x，然后在順序表中逐次進(jìn)行比較。若相等，則搜索成功，返回它的所在位置。若遍歷整個(gè)表，沒有值與其相等，則返回搜索失敗。
一般來說，搜索算法的復(fù)雜度是根據(jù)比較次數(shù)來決定的。簡要分析，如果我們要找的值在第一個(gè)表項(xiàng)，那么它的比較次數(shù)就是1，當(dāng)然要是在第二個(gè)表項(xiàng)，次數(shù)就為2，依次類推，在第n個(gè)表項(xiàng)，比較次數(shù)就為n。好了啦，現(xiàn)在我們可以計(jì)算它的平均比較次數(shù)了。假定每個(gè)表項(xiàng)的可能性都相等，那么我們有：
Acn=1/nΣi=1/n(1+2+.....+n)=1/nn(n+1)/2=(n+1)/2;
所以平均比較次數(shù)為(n+1)/2；
第二，插入：
順序表的插入和刪除算法復(fù)雜度與其表項(xiàng)循環(huán)內(nèi)數(shù)據(jù)移動(dòng)次數(shù)直接有關(guān)，先分析插入。我們知道，順序表中如果要在某個(gè)位置插入一個(gè)元素，就必須把那個(gè)空出來，怎么空出來呢，其實(shí)就是把它以及它后面的元素向后移動(dòng)一位。那么就是這樣的，如果將新表項(xiàng)插入至第i個(gè)表項(xiàng)后面，可以從后向前循環(huán)，逐個(gè)向后移動(dòng)n-i個(gè)表項(xiàng)。最好的情形就是在表尾追加新元素。那么它的移動(dòng)次數(shù)為0，相反，最壞情形是在第一個(gè)表項(xiàng)位置插入。那么移動(dòng)次數(shù)為n。來看平均移動(dòng)次數(shù)。
Amn=1/(n+1)Σ(n-i)=1/(n+1)((n-1)+...+1+0)=(n)/2;
第三，刪除：
在刪除第i個(gè)表項(xiàng)時(shí)，是逐個(gè)移動(dòng)n-i個(gè)表項(xiàng)。最好的情況是在刪去最后的n個(gè)表項(xiàng)。次數(shù)為0，最壞情況是刪除第一個(gè)表項(xiàng)。移動(dòng)個(gè)數(shù)為n-1。那么平均移動(dòng)個(gè)數(shù)：
Amn=1/nΣ(n-i)=1/n((n-1)+...+1+0)=(n-1)/2;
原文：https://blog.csdn.net/lifestylegoingon/article/details/47903743
總結(jié)：
通過上述的分析，我們對順序表的實(shí)現(xiàn)已有了比較清晰的認(rèn)識，接下來看一下順序表的執(zhí)行效率問題，主要針對獲取、插入、修改、刪除等主要操作。前面分析過，由于順序表內(nèi)部采用了數(shù)組作為存儲容器，而數(shù)組又是隨機(jī)存取結(jié)構(gòu)的容器，也就是說在創(chuàng)建數(shù)組時(shí)操作系統(tǒng)給數(shù)組分配的是一塊連續(xù)的內(nèi)存空間，數(shù)組中每個(gè)存儲單元的地址都是連續(xù)的，所以在知道數(shù)組基地址后可以通過一個(gè)簡單的乘法和加法運(yùn)算即可計(jì)算出其他存儲單元的內(nèi)存地址(實(shí)際上計(jì)算機(jī)內(nèi)部也就是這么做的)，這兩個(gè)運(yùn)算的執(zhí)行時(shí)間是常數(shù)時(shí)間，因此可以認(rèn)為數(shù)組的訪問操作能在常數(shù)時(shí)間內(nèi)完成，即順序表的訪問操作(獲取和修改元素值)的時(shí)間復(fù)雜為O(1)。
對于在順序表中插入或者刪除元素，從效率上則顯得不太理想了，由于插入或者刪除操作是基于位置的，需要移動(dòng)數(shù)組中的其他元素，所以順序表的插入或刪除操作，算法所花費(fèi)的時(shí)間主要是用于移動(dòng)元素，如在順序表頭部插入或刪除時(shí)，效率就顯得相當(dāng)糟糕了。
優(yōu)點(diǎn)
使用數(shù)組作為內(nèi)部容器簡單且易用
在訪問元素方面效率高
數(shù)組具有內(nèi)存空間局部性的特點(diǎn)，由于本身定義為連續(xù)的內(nèi)存塊，所以任何元素與其相鄰的元素在物理地址上也是相鄰的。
缺點(diǎn)
內(nèi)部數(shù)組大小是靜態(tài)的，在使用前必須指定大小，如果遇到容量不足時(shí)，需動(dòng)態(tài)拓展內(nèi)部數(shù)組的大小，會造成額外的時(shí)間和空間開銷
在內(nèi)部創(chuàng)建數(shù)組時(shí)提供的是一塊連續(xù)的空間塊，當(dāng)規(guī)模較大時(shí)可能會無法分配數(shù)組所需要的內(nèi)存空間
順序表的插入和刪除是基于位置的操作，如果需要在數(shù)組中的指定位置插入或者刪除元素，可能需要移動(dòng)內(nèi)部數(shù)組中的其他元素，這樣會造成較大的時(shí)間開銷，時(shí)間復(fù)雜度為O(n)
鏈表
通過前面對線性順序表的分析，我們知道當(dāng)創(chuàng)建順序表時(shí)必須分配一塊連續(xù)的內(nèi)存存儲空間，而當(dāng)順序表內(nèi)部數(shù)組的容量不足時(shí)，則必須創(chuàng)建一個(gè)新的數(shù)組，然后把原數(shù)組的的元素復(fù)制到新的數(shù)組中，這將浪費(fèi)大量的時(shí)間。而在插入或刪除元素時(shí)，可能需要移動(dòng)數(shù)組中的元素，這也將消耗一定的時(shí)間。鑒于這種種原因，于是鏈表就出場了，鏈表在初始化時(shí)僅需要分配一個(gè)元素的存儲空間，并且插入和刪除新的元素也相當(dāng)便捷，同時(shí)鏈表在內(nèi)存分配上可以是不連續(xù)的內(nèi)存，也不需要做任何內(nèi)存復(fù)制和重新分配的操作。
public class Node<T> {
//鏈表數(shù)據(jù)域
T t;
//鏈表指針域
Node<T> next;
public Node(T t) {
this.t = t;
}
}
public Node<T> head;
public int size;
}
單鏈表添加：鏈表添加分為頭部添加和其他
/**
* 單鏈表添加數(shù)據(jù)
*
* @param index
* @param data
*/
public void add(int index, T data) {
if (data == null) {
return;
}
if (index < 0 || index > size) {
System.out.println("插入位置不對");
return;
}
//在頭部插入
if (head == null ) {
head = new Node(data);
} else {
Node front = head;
//找到要插入結(jié)點(diǎn)位置的前一個(gè)結(jié)點(diǎn)
for (int i = 0; i < index - 1; i++) {
if (front.next != null) {
front = front.next;
}
}
Node newNode = new Node(data);
newNode.next = front.next;
front.next = newNode;
}
size++;
}
添加頭部位置：頭部結(jié)點(diǎn)為空所以直接將新結(jié)點(diǎn)賦值給頭部位置
添加中間(尾部)位置：先找到要添加結(jié)點(diǎn)的前一個(gè)位置，新結(jié)點(diǎn)的next=front.next, front.next指向新結(jié)點(diǎn)的位置。記得判空，因?yàn)槲膊康膎ext是空
單鏈表刪除：鏈表刪除分為頭部刪除和其他
刪除頭部位置：刪除頭部位置，及它的next變成新的head.
刪除中間位置：先找到要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)位置，該位置的next直接指向該位置next的next.
/**
* 刪除結(jié)點(diǎn)
*
* @param index
*/
public void delNode(int index) {
if (index < 0 || index > size) {
System.out.println("刪除位置不對");
return;
}
/*刪除頭結(jié)點(diǎn)*/
if (index == 0 && head != null) {
head = head.next;
} else {
Node front = head;
//找到要?jiǎng)h除結(jié)點(diǎn)位置的前一個(gè)結(jié)點(diǎn)
for (int i = 0; i < index - 1; i++) {
if (front.next != null) {
front = front.next;
}
}
if (front.next != null) {
front.next = front.next.next;
}
}
size--;
}
其他方法：
/**
* 判斷是否是空
* @return
*/
public boolean isEmpty() {
return head == null;
}
/**
* 清空結(jié)點(diǎn)
*/
public void clearLinked() {
if (!isEmpty()) {
head = null;
}
}
/**
* 顯示出所有的節(jié)點(diǎn)信息
*/
public void displayAllNode() {
Node current = head;
while (current != null) {
System.out.print(current.t + " ");
current = current.next;
}
}
測試：
@Test
public void test() {
SignLinkedList signLinkedList = new SignLinkedList();
signLinkedList.add(0, "a");
signLinkedList.add(1, "b");
signLinkedList.add(2, "c");
signLinkedList.add(3, "d");
signLinkedList.add(4, "e");
signLinkedList.displayAllNode();
System.out.println("\n----刪除頭結(jié)點(diǎn)----");
signLinkedList.delNode(0);
signLinkedList.displayAllNode();
System.out.println("\n----刪除中間結(jié)點(diǎn)----");
signLinkedList.delNode(2);
signLinkedList.displayAllNode();
System.out.println("\n----刪除尾結(jié)點(diǎn)----");
signLinkedList.delNode(2);
signLinkedList.displayAllNode();
System.out.println("\n----清空數(shù)據(jù)----");
signLinkedList.clearLinked();
signLinkedList.displayAllNode();
}
單鏈表性能分析：
由于單鏈表并不是隨機(jī)存取結(jié)構(gòu)，即使單鏈表在訪問第一個(gè)結(jié)點(diǎn)時(shí)花費(fèi)的時(shí)間為常數(shù)時(shí)間，但是如果需要訪問第i(0<i<n)個(gè)結(jié)點(diǎn)，需要從頭結(jié)點(diǎn)head開始遍歷部分鏈表，進(jìn)行i次的p=p.next操作，這點(diǎn)從上述的圖文分析我們也可以看出，這種情況類似于前面計(jì)算順序表需要平均移動(dòng)元素的總數(shù)，因此鏈表也需要平均進(jìn)行n2n2次的p=p.next操作，也就是說get(i)和set(i,x)的時(shí)間復(fù)雜度都為O(n)。
由于鏈表在插入和刪除結(jié)點(diǎn)方面十分高效的，因此鏈表比較適合那些插入刪除頻繁的場景使用，單純從插入操作來看，我們假設(shè)front指向的是單鏈表中的一個(gè)結(jié)點(diǎn)，此時(shí)插入front的后繼結(jié)點(diǎn)所消耗的時(shí)間為常數(shù)時(shí)間O(1),但如果此時(shí)需要在front的前面插入一個(gè)結(jié)點(diǎn)或者刪除結(jié)點(diǎn)自己時(shí)，由于front并沒有前驅(qū)指針，單憑front根本無法知道前驅(qū)結(jié)點(diǎn)，所以必須從鏈表的表頭遍歷至front的前一個(gè)結(jié)點(diǎn)再執(zhí)行插入或者刪除操作，而這個(gè)查詢操作所消耗的時(shí)間為O(n),因此在已知front結(jié)點(diǎn)需要插入前驅(qū)結(jié)點(diǎn)或者刪除結(jié)點(diǎn)自己時(shí)，消耗的時(shí)間為O(n)。當(dāng)然這種情況并不是無法解決的，后面我們要分析到的雙鏈表就可以很好解決這個(gè)問題，雙鏈表是每個(gè)結(jié)點(diǎn)都同時(shí)擁有前后繼結(jié)點(diǎn)的鏈表，這樣的話上面的問題就迎刃而解了。上述是從已知單鏈表中front結(jié)點(diǎn)的情況下討論的單鏈表的插入刪除效率。
我們可能會有個(gè)疑問，從前面單鏈表的插入刪除的代碼實(shí)現(xiàn)上來說，我們并不知道front結(jié)點(diǎn)的，每次插入和刪除結(jié)點(diǎn)，都需要從表頭開始遍歷至要插入或者刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，而這個(gè)過程所花費(fèi)的時(shí)間和訪問結(jié)點(diǎn)所花費(fèi)的時(shí)間是一樣的，即O(n)，
也就是說從實(shí)現(xiàn)上來說確實(shí)單鏈表的插入刪除操作花費(fèi)時(shí)間也是O(n)，而順序表插入和刪除的時(shí)間也是O(n)，那為什么說單鏈表的插入和刪除的效率高呢？這里我們要明白的是鏈表的插入和刪除之所以是O(N)，是因?yàn)椴樵儾迦朦c(diǎn)所消耗的，找到插入點(diǎn)后插入操作消耗時(shí)間只為O(1)，而順序表查找插入點(diǎn)的時(shí)間為O(1)，但要把后面的元素全部后移一位，消耗時(shí)間為O(n)。問題是大部分情況下查找所需時(shí)間比移動(dòng)短多了，還有就是鏈表不需要連續(xù)空間也不需要擴(kuò)容操作，因此即使時(shí)間復(fù)雜度都是O(n)，所以相對來說鏈表更適合插入刪除操作。
原文：https://blog.csdn.net/javazejian/article/details/52953190
單鏈表的反轉(zhuǎn)
https://mp.weixin.qq.com/s?src=11×tamp=1590225130&ver=2356&signature=ir7GLbKq7oqI0usHtgvIBItkfEZScqO0XH3inr2F2in9Bb36xsWkOblF8An6XqTLG3ff0jyoHPUzLGqQZVw0RAvcHU-NYudxl3lNQX-kPLpI9fD0uxFx1nLlb4g395&new=1
雙鏈表
雙鏈表的主要優(yōu)點(diǎn)是對于任意給的結(jié)點(diǎn)，都可以很輕易的獲取其前驅(qū)結(jié)點(diǎn)或者后繼結(jié)點(diǎn)，而主要缺點(diǎn)是每個(gè)結(jié)點(diǎn)需要添加額外的next域，因此需要更多的空間開銷，同時(shí)結(jié)點(diǎn)的插入與刪除操作也將更加耗時(shí)，因?yàn)樾枰嗟闹羔樦赶虿僮鳌?/p>
在插入雙鏈表時(shí)需分兩種情況，一種是在插入空雙鏈表和尾部插入，另一種是雙鏈表的中間插入，如下圖在空雙鏈表插入值x：
原文：https://blog.csdn.net/javazejian/article/details/52953190
代碼：
public class Node<T> {
public Node pre;
public Node next;
public T data;
public Node(Node pre, Node next, T data) {
this.pre = pre;
this.next = next;
this.data = data;
}
}
尾部的插入：如果是空表則將新節(jié)點(diǎn)設(shè)置位first結(jié)點(diǎn)，反之添加在尾部位置。
/**
* 從尾部添加
* @param data
*/
public void addLast(T data) {
Node newNode = new Node(last, null, data);
Node l = last;
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
指定位置添加： 在指定位置添加需要將新結(jié)點(diǎn)的前驅(qū)指向front后繼指向front的next。故新結(jié)點(diǎn)為：
Node newNode = new Node(front, front.next, data);
接著更改front的next指向newNode，front的next的pre指向newNode。這樣原本A、B兩個(gè)的連接點(diǎn)就斷開，重新指向新的位置。
代碼表示：
/**
* 指定位置添加
* @param index
* @param data
*/
public void add(int index, T data) {
if (data == null) {
return;
}
if (index < 0 || index > size) {
System.out.println("插入位置不對");
return;
}
/*如果指定的位置等于在表的尾部*/
if (index == size) {
addLast(data);
} else {
Node front = first;
/*先將指針移向?qū)⒁鋈胛恢玫那耙粋€(gè)位置*/
for (int i = 0; i < index - 1; i++) {
if (front.next != null) {
front = front.next;
}
}
/*創(chuàng)建將要插入的結(jié)點(diǎn) 新結(jié)點(diǎn)前驅(qū)指向front,后繼指向front的后繼*/
Node newNode = new Node(front, front.next, data);
if (front.next != null) {
front.next.pre = newNode;
//更改front的后繼指針
front.next = newNode;
}
size++;
}
}
根據(jù)index獲取結(jié)點(diǎn)
/**
* 根據(jù)index獲取結(jié)點(diǎn)
* @param index
* @return
*/
private Node<T> getNode(int index) {
Node node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
刪除結(jié)點(diǎn)：刪除結(jié)點(diǎn)包括刪除尾結(jié)點(diǎn)，頭結(jié)點(diǎn)以及中間結(jié)點(diǎn)。
/**
* 刪除結(jié)點(diǎn)
* @param index
*/
public void removeNode(int index){
if(index<0||index>size){
System.out.println("刪除位置不對");
return;
}
/*根據(jù)指定位置獲取當(dāng)前要?jiǎng)h除的結(jié)點(diǎn)*/
Node delNode = getNode(index);
/*刪除頭結(jié)點(diǎn)*/
if(delNode.pre == null){
first = delNode.next ;
}
/*刪除尾結(jié)點(diǎn)*/
if(delNode.next == null){
last = delNode.pre;
}
/*刪除中間結(jié)點(diǎn)*/
if(delNode.pre !=null && delNode.next!=null){
delNode.pre.next = delNode.next ;
delNode.next.pre = delNode.pre;
}
size-- ;
}
測試：
@Test
public void test() {
LinkedList linkedList = new LinkedList();
linkedList.add(0, "1");
linkedList.add(1, "2");
linkedList.add(2, "3");
linkedList.add(3, "4");
linkedList.add(3,"5");
linkedList.add("last");
for (int i = 0; i < linkedList.size; i++) {
System.out.println("位置 " + linkedList.getData(i));
}
linkedList.removeNode(2);
linkedList.removeNode(linkedList.size-1);
System.out.println("刪除數(shù)據(jù)后");
for (int i = 0; i < linkedList.size; i++) {
System.out.println("位置 " + linkedList.getData(i));
}
}
總結(jié)
順序表和鏈表存儲的優(yōu)缺點(diǎn)
1.順序表存儲
原理：順序表存儲是將數(shù)據(jù)元素放到一塊連續(xù)的內(nèi)存存儲空間，存取效率高，速度快。但是不可以動(dòng)態(tài)增加長度
優(yōu)點(diǎn)：存取速度高效，通過下標(biāo)來直接存儲
缺點(diǎn)：1.插入和刪除比較慢，2.不可以增長長度
比如：插入或者刪除一個(gè)元素時(shí)，整個(gè)表需要遍歷移動(dòng)元素來重新排一次順序
2.鏈表存儲
原理：鏈表存儲是在程序運(yùn)行過程中動(dòng)態(tài)的分配空間，只要存儲器還有空間，就不會發(fā)生存儲溢出問題
優(yōu)點(diǎn)：插入和刪除速度快，保留原有的物理順序，比如：插入或者刪除一個(gè)元素時(shí)，只需要改變指針指向即可
缺點(diǎn)：查找速度慢，因?yàn)椴檎視r(shí)，需要循環(huán)鏈表訪問
從它們的存儲優(yōu)缺點(diǎn)來看，各自有各自的使用場景，比如：頻繁的查找卻很少的插入和刪除操作可以用順序表存儲，如果頻繁的插入和刪除操作很少的查詢就可以使用鏈表存儲
原文鏈接：https://blog.csdn.net/u013538542/article/details/47336179
