Javascript中的array跟資料結構中的List和Array是一回事嗎?

javascript 資料結構數據結構

Nissen 2018-10-12 15:11:52 ‧ 12975 瀏覽

分享至

最近在學習資料結構
我大概知道

array:
﹒線型資料
．每筆資料有自己的編號array[0]~array[n]因此查找簡單
．刪除、增加資料困難
．儲存在連續的記憶體當中

list:
．線型資料資料
．可以儲存在不連續記憶體，每筆資料(以指標)指向前後資料
．刪除、增加資料簡單
．缺點就是查找困難(要從第一個找)

(以上有觀念有問題歡迎指出><)

但數據結構的教材通常都是以JAVA C 之類的語言為範例，但是我目前只會js，因此常常無法體會他們在講什麼。

因此我想請問Js的Array跟上述的資料結構介紹的Array是一樣的概念嗎?

．兩者是否指涉同個類型的資料結構?
．是否儲存在連續的記憶體當中
．是否同樣具有刪除、增加資料的困難
．還有為甚麼JS沒有LIST呢?

感謝><

froce iT邦大師 1 級 ‧ 2018-10-12 15:23:41 檢舉

你覺得JS的array和你列出來的那個比較像呢？

㊣浩瀚星空㊣ iT邦大神 1 級 ‧ 2018-10-12 16:39:54 檢舉

這種觀念性的問題，真要解釋起來。還真不知道該怎麼說明比較好。

我用比較白話的答案好了。

1.兩者是否指涉同個類型的資料結構?
答：可以說是同樣運用的架構沒錯。但還是有結構上不同的地方。

2.是否儲存在連續的記憶體當中?
答：這超出我能理解的範圍，不想回答。
不是啦，只是依目前的多工技術來說,很難對你說是還是不是。
你可以當「是」

3.是否同樣具有刪除、增加資料的困難
這其實要看你所謂困難的程度指的是什麼。
如果是要做到那種「喊水就結凍」的地步。
那我只能說很困難。

4.還有為甚麼JS沒有LIST呢?
這點其實要從很久之前的第一套瀏覽器來談起了。
啊人家當初就沒規劃出list出來。然後現在是各瀏覽器通用的模式
又卡在前端語言無法變動性的問題。當然就沒有了
可是現在javascrip的擴充性很高，否則怎麼會出現像jquery、vue這些東西出來。

以上，可是好好的一一回答了。

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

2 個回答

跟著鄉民看熱鬧

iT邦高手 1 級 ‧ 2018-10-12 15:24:26

請參考，不再重述～
https://stackoverflow.com/questions/1748794/is-there-an-arraylist-in-javascript

回應
分享
檢舉

登入發表回應

小碼農米爾

iT邦高手 1 級 ‧ 2018-10-13 01:22:30

您的問題很棒，學習程式要有追根究柢的精神，話雖如此但這些問題我也沒有細想過，今天學習了。

Google 後找到這篇，內容有提到 js 陣列底層實現。
https://stackoverflow.com/questions/20321047/how-are-javascript-arrays-represented-in-physical-memory

以狹義的角度來看

JS 的陣列的確和 C 的不一樣，JS 陣列是類似 Hashtable (雜湊表) 的結構，時間複雜度是 O(1)，會比陣列慢一點 (指C語言)。

以廣義的角度來看

JS 和 C 的陣列兩者都是線型資料、可用索引存取、增刪資料困難，因此可將兩者當成相同的結構。

最後一個問題為甚麼JS沒有LIST呢?

以語言底層來看，JS 的確沒有提供 list 結構，但同樣 C 也沒有，C 的 list 是 STL 函式庫中的一個類別，並不是語言本身提供，我們也可以自己用 JS 寫一個，其實除了少數幾個程式語言本身提供外，大部分的資料結構都是另外寫的 (自己寫或函式庫)。

回應 4
分享
檢舉

看更多先前的回應...收起先前的回應...

Homura iT邦高手 1 級 ‧ 2018-10-14 00:32:54 檢舉

JS連內建的時間函數都很難用

小碼農米爾 iT邦高手 1 級 ‧ 2018-10-15 08:46:20 檢舉

JS 的 new 也不太會用。

fillano iT邦超人 1 級 ‧ 2018-10-15 10:13:27 檢舉

DOM裡面倒是定義了許多List，要把他當作Array用還得花些功夫XD

大部分語言的Array是有型別的，裡面只能放同型別的東西，這樣比較容易用連續的記憶體來實做。（但是實際上是怎麼運作就很難說，而且現在很多語言是編譯成中間表示式在執行的，例如Java跟C#等等，過度與C或Assembly等的觀念對應有時，可能會不太精確）反觀Javascript的Array可以放進任何型別的東西...

小碼農米爾 iT邦高手 1 級 ‧ 2018-10-15 22:56:34 檢舉

感謝 fillano 大大拋磚引玉，Google 後找到這兩篇講 C# 的。

[1] https://stackoverflow.com/questions/487202/memory-layout-of-a-net-array
[2] https://windowsdebugging.wordpress.com/2012/04/07/memorylayoutofarrays/

內容提到 C# 的陣列在記憶體中是連續的，不過開頭的地方會存放 方法表 和 陣列大小 等資訊，所以還是和 C、Assembly 完全乾淨的陣列空間不太一樣。
而 Javascript 的 Array 反而更像字典，陣列索引也只是字典中的 key 值，這樣看來 Javascript 處處都是 key/value 呢，這樣能放任何型別也符合邏輯了。