什么是數(shù)組

數(shù)組(Array): 有限個相同類型的變量所組成的有序集合，數(shù)組中的每一個變量稱為元素。

數(shù)組在內(nèi)存中順序存儲。

Python中使用列表(list)和元組(tuple)這兩種集合，本質(zhì)上是對數(shù)組的封裝；

列表是一個動態(tài)可擴展的數(shù)組，支持任意的增、刪、改；

元組是一個不可變集合，一旦創(chuàng)建就不再支持修改

數(shù)組的優(yōu)勢與劣勢：

• 數(shù)組擁有非常高效的隨機訪問能力，只要給出下標(biāo)，就可以用常量時間找到對應(yīng)元素。運用該優(yōu)勢的算法：二分查找

• 插入、刪除元素都會導(dǎo)致大量元素被迫移動，影響效率

• 數(shù)組適合的是讀操作多、寫操作少的場景

什么是鏈表

鏈表(linked list)是一種物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(node)所組成。

單向鏈表中每個節(jié)點包含兩部分，一是存放數(shù)據(jù)變量的data，另一個部分是指向下一個節(jié)點的指針next。

雙向鏈表：每個節(jié)點除了擁有data和next指針，還擁有指向前置節(jié)點的prev指針。

數(shù)組的存儲方式：順序存儲

鏈表的存儲方式：隨機存儲

數(shù)組的優(yōu)勢在于能夠快速定位元素，對于讀操作多、寫操作少的場景來說，用數(shù)組更合適一些；

鏈表的優(yōu)勢在于能夠靈活地進行插入和刪除操作，如果需要頻繁插入、刪除元素，用鏈表更合適一些

棧和隊列

棧(stack)是一種線性數(shù)據(jù)結(jié)構(gòu)，棧中的元素只能先入后出(First In Last Out, FILO)；

最早進入元素存放的位置叫做棧底(bottom)，最后進入的元素存放的位置叫做棧頂(top)；

?？捎脭?shù)組或者鏈表來實現(xiàn)

棧的基本操作包括 入棧(push)和出棧(pop)

入棧操作（push）就是把新元素放入棧中，只允許從棧頂一側(cè)放入元素，新元素的位置將會成為新的棧頂。

Python語言中，列表實現(xiàn)了棧的功能，append(element)相當(dāng)于入棧，pop(element)相當(dāng)于出棧

隊列(queue)是一種線性數(shù)據(jù)結(jié)構(gòu)，隊列中的元素只能先入先出(First In First Out,FIFO)；

隊列的入口端叫做隊尾，隊列的出口端叫做隊頭;

隊列可以用數(shù)組或者鏈表來實現(xiàn)

隊列的基本操作：入隊(enqueue)和出隊(dequeue)

入隊: 在隊尾的位置放入元素，新元素的下一個位置將會成為新的隊尾

出隊: 只允許在隊頭一側(cè)移出元素，出隊元素的后一個元素將會成為新的隊頭

循環(huán)隊列：假設(shè)一個隊列經(jīng)過反復(fù)的入隊和出隊操作，還剩下2個元素，在“物理”上分布于數(shù)組的末尾位置。這時又有一個新元素將要入隊。在數(shù)組不做擴容的前提下，我們可以利用已出隊元素留下的空間，讓隊尾指針重新指回數(shù)組的首位。這樣一來，整個隊列的元素就“循環(huán)”起來了。

在Python中，表示隊列的工具由collections.deque、queue.Queue等

棧的應(yīng)用:?

• 實現(xiàn)遞歸的邏輯

• 面包屑導(dǎo)航

隊列的應(yīng)用:?

• 在多線程中，爭奪公平鎖的等待隊列

• 網(wǎng)絡(luò)爬蟲實現(xiàn)網(wǎng)站抓取
  

雙端隊列：

雙端隊列可以從隊頭一端可以入隊或出隊，也可以從隊尾一端也可以入隊或出隊。

優(yōu)先隊列:?

誰的優(yōu)先級最高，誰先出隊，優(yōu)先隊列已經(jīng)不屬于線性數(shù)據(jù)結(jié)構(gòu)的范疇了，它是基于二叉堆來實現(xiàn)的。

神奇的哈希表

哈希表(hash table)：散列表，提供鍵(Key)-值(Value)的映射關(guān)系，給出key，就可以高效地找到所匹配的Value

哈希表在本質(zhì)上也是一個數(shù)組，數(shù)組根據(jù)下標(biāo)，像a[0]、a[1]、a[2]、a[3]、a[4]這樣來訪

問，而哈希表則以字符串類型的Key為下標(biāo)進行訪問

Python中，哈希表對應(yīng)的集合為字典(dict)

在Python及大多數(shù)面向?qū)ο蟮恼Z言中，每一個對象都有屬于自己的hash值，這個hash值是區(qū)分不同對象的重要標(biāo)識。無論對象自身的類型是什么，它們的hash值都是一個整型變量

Python中的哈希函數(shù)利用了位運算的方式來優(yōu)化性能

通過哈希函數(shù)，可以把字符串或其他類型的Key，轉(zhuǎn)化成數(shù)組的下標(biāo)index

哈希表的寫操作(put)：

寫操作就是在哈希表中插入新的鍵值對(Entry)

哈希沖突: 由于數(shù)組的長度是有限的，當(dāng)插入的Entry越來越多時，不同的Key通過哈希函數(shù)獲得的下標(biāo)有可能是相同的

解決哈希沖突的方法主要有兩種，一種是開放尋址法，一種是鏈表法

開放尋址法: 當(dāng)一個Key通過哈希函數(shù)獲得對應(yīng)的數(shù)組下標(biāo)已被占用時，我們可以尋找下一個空當(dāng)位置

鏈表法: 哈希表數(shù)組的每一個元素不僅是一個Entry對象，還是一個鏈表的頭節(jié)點。每一個Entry對象通過next指針指向它的下一個Entry節(jié)點。當(dāng)新來的Entry映射到與之沖突的數(shù)組位置時，只需要插入對應(yīng)的鏈表中即可。

哈希表讀操作(get)：通過給定的Key，在哈希表中查找對應(yīng)的Value。

在眾多編程語言中，有些語言的哈希表采用了鏈表法，最具代表性的就是

Java中的HashMap；

有些編程語言采用的是開放尋址法，比如Python中的dict。

有興趣的讀者可以看一下Python官方解釋器（CPython）中，關(guān)于PyDictObject的C語言源碼實現(xiàn)。

哈希表可以說是數(shù)組和鏈表的結(jié)合，它在算法中的應(yīng)用很普遍，是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。

小結(jié)

什么是數(shù)組？

數(shù)組是由有限個相同類型的變量所組成的有序集合，它的物理存儲方式是順序存儲，訪問方式是隨機訪問。利用下標(biāo)查找數(shù)組元素的時間復(fù)雜度是O(1)，中間插入、刪除數(shù)組元素的時間復(fù)雜度是O(n）

什么是鏈表？

鏈表是一種鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，由若干節(jié)點組成，每個節(jié)點包含指向下一節(jié)點的指針。鏈表的物理存儲方式是隨機存儲，訪問方式是順序訪問。查找鏈表節(jié)點的時間復(fù)雜度是O(n)， 中間插入、刪除節(jié)點的時間復(fù)雜度是O(1)

什么是棧？

棧是一種線性邏輯結(jié)構(gòu)，可以用數(shù)組實現(xiàn)，也可以用鏈表實現(xiàn)；

棧包含入棧和出棧操作，遵循先入后出的原則(FILO)

什么是隊列？

隊列是一種線性邏輯結(jié)構(gòu)，可以用數(shù)組實現(xiàn)，也可以用鏈表實現(xiàn)；

隊列包含入隊和出隊的操作，遵循先入先出的原則(FIFO)

什么是哈希表？
哈希表也叫做散列表，是存儲Key-Value映射的集合；

對于某一個Key，哈希表可以在接近O(1)的時間內(nèi)進行讀寫操作；

哈希表通過哈希函數(shù)實現(xiàn)Key和數(shù)組下表的轉(zhuǎn)換，通過開放尋址法和鏈表法來解決哈希沖突