iT邦幫忙

2

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

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

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

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

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

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

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

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

感謝><

froce iT邦大師 3 級 ‧ 2018-10-12 15:23:41 檢舉
你覺得JS的array和你列出來的那個比較像呢?
這種觀念性的問題,真要解釋起來。還真不知道該怎麼說明比較好。

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


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

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

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

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

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

2 個回答

5
fysh711426
iT邦研究生 3 級 ‧ 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 寫一個,其實除了少數幾個程式語言本身提供外,大部分的資料結構都是另外寫的 (自己寫或函式庫)。

看更多先前的回應...收起先前的回應...
Homura iT邦高手 1 級 ‧ 2018-10-14 00:32:54 檢舉

JS連內建的時間函數都很難用/images/emoticon/emoticon05.gif

fysh711426 iT邦研究生 3 級 ‧ 2018-10-15 08:46:20 檢舉

JS 的 new 也不太會用。 /images/emoticon/emoticon16.gif

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

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

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

fysh711426 iT邦研究生 3 級 ‧ 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 呢,這樣能放任何型別也符合邏輯了。
/images/emoticon/emoticon37.gif

我要發表回答

立即登入回答