玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)從入門(mén)到進(jìn)階d社區(qū)dmzshequ

1、玩兒轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)liuyubobobo鏈表線性數(shù)據(jù)結(jié)構(gòu) 動(dòng)態(tài)數(shù)組üï底層依托靜態(tài)數(shù)組；靠resize解決固定容問(wèn)題 棧ýïïþ 隊(duì) 鏈表真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)為么鏈表很重要 鏈表真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 深入的解引用（或者指針） 深入的解遞歸 輔助組成其他數(shù)據(jù)結(jié)構(gòu)鏈表 Linked List在“節(jié)點(diǎn)”（Node）中 數(shù)據(jù)classENodee;NULL123Nodenext;鏈表 Linked List 數(shù)據(jù)存儲(chǔ)在“節(jié)點(diǎn)”（Node）中NULL123 優(yōu)點(diǎn)：真正的動(dòng)態(tài)，需要處固定容的問(wèn)題 缺點(diǎn)：?jiǎn)适щS機(jī)訪問(wèn)的能數(shù)組和鏈表的對(duì)

2、比 數(shù)組最好用于索引有語(yǔ)意的情況。scores2 最大的優(yōu)點(diǎn)：支持快速查詢 鏈表適合用于索引有語(yǔ)意的情況。 最大的優(yōu)點(diǎn)：動(dòng)態(tài)實(shí)踐：鏈表基礎(chǔ)向鏈表中添加元素鏈表 Linked ListNULL01234head實(shí)踐：鏈表基礎(chǔ)在鏈表頭添加元素node666NULL01234headnode.next=head在鏈表頭添加元素nodeNULL01234headnode.next=headhead=node666在鏈表頭添加元素nodeNULL66601234headnode.next=headhead=node實(shí)踐：在鏈表頭添加元素在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL0

3、1234nodehead666在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL01234nodehead666在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL01234nodeheadnode.next=prev.next666在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL0234nodeheadnode.nextprev.next=prev.nextnode6661在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL0666234headnode.nextprev.next=prev.nextnode 關(guān)鍵：找到要添加的節(jié)

4、點(diǎn)的前一個(gè)節(jié)點(diǎn)1在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL01234nodeheadprev.next=node666在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL0234nodeheadprev.next=node6661在鏈表中間添加元素 在索引為2的地方添加元素666prevNULL0234node 順序很重要prev.next node.nexthead=nodeprev.next6661實(shí)踐：在鏈表中間添加元素為鏈表設(shè)立虛擬頭結(jié)點(diǎn)為鏈表設(shè)立虛擬頭結(jié)點(diǎn)NULL01234head為鏈表設(shè)立虛擬頭結(jié)點(diǎn)NULLnull01234head為鏈表設(shè)立虛

5、擬頭結(jié)點(diǎn)NULLnull01234dummyHead實(shí)踐：為鏈表設(shè)立虛擬頭結(jié)點(diǎn)鏈表元素的，新與遍歷實(shí)踐：鏈表元素的遍歷，與新鏈表元素的刪除鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull01234dummyHead鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull01234dummyHead鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull01234dummyHeaddelNodeprev.next=delNode.next鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull0234dummyHeaddelNodeprev.next=delNod

6、e.next1鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull034dummyHeadNULLprev.next2=delNode.nextdelNode1鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull034dummyHeadNULLprev.next2=delNode.nextdelNode.next=nulldelNode1鏈表元素刪除常見(jiàn)的錯(cuò)誤 刪除索引為2位置的元素curNULLnull01234dummyHead鏈表元素刪除常見(jiàn)的錯(cuò)誤 刪除索引為2位置的元素curNULLnull01234dummyHead鏈表元素刪除常見(jiàn)的錯(cuò)誤 刪除索引為2位置的元素c

7、urNULLnull01234dummyHeadcur=cur.next鏈表元素的刪除 刪除索引為2位置的元素prevNULLnull034dummyHeadNULLprev.next2=delNode.nextdelNode.next=nulldelNode1實(shí)踐：鏈表元素的刪除鏈表的時(shí)間復(fù)雜度分析 添加操作O(n)addLast(e)O(n)addFirst(e)O(1)add(index, e)O(n/2) = O(n)鏈表的時(shí)間復(fù)雜度分析 刪除操作O(n)removeLast(e)O(n)removeFirst(e)O(1)remove(index, e)O(n/2) = O(n)鏈表

8、的時(shí)間復(fù)雜度分析 修改操作O(n)set(index, e)O(n)鏈表的時(shí)間復(fù)雜度分析 查找操作O(n)get(index)O(n)contains(e)O(n)find(e)O(n)鏈表的時(shí)間復(fù)雜度分析 增 ： O(n)如果只對(duì)鏈表頭進(jìn)操作：O(1) 刪 ： O(n) 改 ： O(n) 查 ： O(n)鏈表的時(shí)間復(fù)雜度分析 增 ： O(n)如果只對(duì)鏈表頭進(jìn)操作：O(1) 刪 ： O(n) 改 ： O(n) 查 ： O(n)鏈表的時(shí)間復(fù)雜度分析 增 ： O(n)如果只對(duì)鏈表頭進(jìn)操作：O(1) 刪 ： O(n) 改 ： O(n) 查 ： O(n)只查鏈表頭的元素：O(1)使用鏈表實(shí)現(xiàn)棧鏈表的時(shí)

9、間復(fù)雜度分析 增 ： O(n)如果只對(duì)鏈表頭進(jìn)操作：O(1) 刪 ： O(n) 改 ： O(n) 查 ： O(n)只查鏈表頭的元素：O(1)使用鏈表實(shí)現(xiàn)棧InterfaceStack<E>LinkedListStack<E>voidpush(E)implementEpop()Epeek()intgetSize()booleanisEmpty()實(shí)踐：使用鏈表實(shí)現(xiàn)棧使用鏈表實(shí)現(xiàn)隊(duì)鏈表的時(shí)間復(fù)雜度分析 增 ： O(n)如果只對(duì)鏈表頭進(jìn)操作：O(1) 刪 ： O(n) 改 ： O(n) 查 ： O(n)只查鏈表頭的元素：O(1)循環(huán)隊(duì)frontdata01234567tailbcde改進(jìn)我們的鏈表NULL01234headtail 從兩端插入元素都是容的改進(jìn)我們的鏈表NULL01234headtail 從tail刪除元素容改進(jìn)我們的鏈表