[爆卦]python鏈結串列是什麼?優點缺點精華區懶人包

為什麼這篇python鏈結串列鄉民發文收入到精華區:因為在python鏈結串列這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者yauhh (喲)看板Soft_Job標題Re: [請益] 請問學哪個比較實用時間Sat Feb...


※ 引述《remmurds (雷穆爾德‧小一)》之銘言:
: ※ 引述《Smurf (哈里歐)》之銘言:
: : 我表達能力不夠好 讓大大誤會了 想學C++是因為我想知道封裝的實作細節
: : 例如Java的ArrayList其實就是先預設一個size
: : 超過這個size要重新配置 所以元素太多時用ArrayList效能會降低
: : LinkedList的實做就是Double Linked List資料結構 要用哪個視情況而定
:   你還是沒看懂我在說什麼。想知道封裝的細節跟想學C++有什麼絕對的關連?請自行
: 搜尋一下天●書局的網站,看看那些以資料結構為主題的書是不是都只用C++。
:   再強調一次,就資料結構或演算法而言,學哪種語言根本不是重點。如果一開始就被
: 語言綁住,就會像我一個學弟先前鬧出的笑話:「我學的是Python,我沒辦法寫鍊結串列
^^^^

這裡我稍有些疑議,我以為linked list就是綁在C或C++這種指標串連資料結構的語言.
如果選用別的語言,linked不linked可能都不重要.

像 Erlang 好了,list就是愛連就連,不用也不會像陣列一樣用太多空間,因為底層的
抽像機已經把一些linked的結構做好了. 它所謂linked list就是:
[1|[2|[3|[]]]]
語法上省略寫為
[1,2,3]
所謂linked就是一個結構包含另一個結構.
Linked list則是結構的包含方式比較有規律.

在這方面,我覺得要說語言不重要,在linked list上面不是如此.
Linked list用C或C++寫才會特別把link帶出來. 用Python,談什麼link呢?

而真要說不被語言綁住的,是stack,queue,tree,graph這些language-free的東西.



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.68.175
remmurds:不管是哪種LinkedList 它們最大的優點不就是解決陣列只有 02/20 21:40
remmurds:固定空間的問題? 這跟一種語言有沒有指標沒關係吧? 02/20 21:41
yauhh:但問題是,陣列只有固定空間不就是C語言特徵來的嗎 02/20 21:47
yauhh:當你遇到另一種語言,陣列空間基本已經不是問題,linked list 02/20 21:48
yauhh:就變得很不必要了. 02/20 21:48
remmurds:有陣列固定空間問題的又不是只有C或C++ Java、C#和其他那 02/20 21:52
remmurds:些常見的程式語言通通都有 只不過以Java和C#來說 已經有 02/20 21:53
remmurds:包裝好的東西可以直接拿來用 就跟你提到的Erlang一樣 02/20 21:53
remmurds:但不管有沒有現成的東西可以用 別忘了原原PO現在是要學這 02/20 21:54
remmurds:些資料結構 如果不從原理看起 就算有現成的東西 原原PO又 02/20 21:55
remmurds:怎麼知道這些東西的優缺點在哪?什麼時候可以派得上用場? 02/20 21:55
ledia:既然你提到 Erlang, 如果不知道 linked list 的特性 02/20 23:04
ledia:你怎麼知道要用 Result++H 還是 [H|Result] 的效率比較好? 02/20 23:05
yauhh:喔,沒想到會提到++... 應該是Result++[H]. 我想對於++的了解 02/20 23:48
yauhh:不是知不知道linked list的特性,而是++的定義如何. 02/20 23:49
yauhh:[] ++ X -> X; [X|Y] ++ Z -> X ++ [Y|Z]. 02/20 23:51
yauhh:因為++是用了許多list運算處理左項,所以耗費較多計算時間. 02/20 23:52
yauhh: [X|Y] ++ Z -> [X|(Y++Z)] 寫錯,更正. 02/20 23:54
yauhh:這個跟linked list概念可以連接得上嗎? 我覺得很難... 02/20 23:55
ledia:那不就是 linked list 的特性嗎? :p 02/20 23:55
ledia:你寫的這些式子就在解釋 linked list 是怎麼運作的 02/20 23:56
ledia:如果你沒有這些基礎的知識, 怎知道 ++ 會有什麼 performance 02/20 23:57
ledia:的 impact 02/20 23:57
yauhh:嗯,對耶... 受教了. 02/21 00:16
yauhh:不過回remmurds,不用這東西不表示不該知道它啦.而是在別的 02/21 00:18
yauhh:語言中,可能說linked list並且做了半天,那個模型仍然消失在 02/21 00:18
yauhh:語法中. 像Erlang就是. 所以倒不如不要計較這個小事. 02/21 00:19
Huangs:linked-list的好處不只是空間使用有彈性 02/21 02:17
Huangs:當資料要搬動時 也非常靈活 例如要在list中插入新元素 02/21 02:17
Huangs:陣列必須把所有元素都往後移一位 挪出空間 02/21 02:18
Huangs:linked-list可以直接插入 一個是 O(N) 一個是 O(1) 02/21 02:18
yauhh:linked list調整空間的彈性當然不用說,而且像Erlang及一些 02/21 08:09
yauhh:不錯的語言本身已經有這種有彈性的list特質. 02/21 08:10
yauhh:至於插入或刪除資料的O(1)和O(N)的比較,是因為有個固定陣列 02/21 08:12
yauhh:的基礎,才會冒出這個問題. 這問題在Erlang本身並不存在. 02/21 08:13
yauhh:因為不是先宣告空間再賦值,而是把資料取來直接合併成list. 02/21 08:14

例如,要做個key-value的linked list,結構是這樣:
[{Key,Value},Next]
Next如果是空節點,表達為 [].

串列建立函數是
create() -> [].
加入新節點是
add([], Node) -> [Node,[]];
add([L|List], Node) -> [L|add(List,Node)].

所以先 L1 = add([], {a, 100}):
add([], {a,100}) -> [{a,100},[]]
再 L2 = add(L1, {b, 200}):
add([{a,100},[]], {b,200}) -> [{a,100}|add([],{b,200}]
-> [{a,100}|[{b,200},[]]] -> [{a,100},{b,200},[]]
再 L3 = add(L2, {c, 300}):
add([{a,100},{b,200},[]], {c,300}) -> [{a,100}|add([{b,200},[]],{c,300})]
-> [{a,100}|[{b,200}|add({c,300},[])]]
-> [{a,100}|[{b,200}|[{c,300},[]]]] -> [{a,100},{b,200},{c,300},[]]
而以上依序插入 {a,100}, {b,200}, {c,300} 的結果可以寫成一個普通的list:
[{a,100},{b,200},{c,300}]

節點插入函數是O(N)的走訪與O(1)的插入,
insert(LList, 1, [Data,_]) -> [Data|LList];
insert([L|List], N, [Data,_]) when N > 1 -> [L|insert(List,N-1,
[Data,[]])];
insert(LList, _, _) -> LList.
這一點linked list和普通list沒有差別.

以前面試考過的串列倒排,可以做得一模一樣. 如果有一列串列是
[{a,100},{b,200},{c,300},[]]
除了第一節點之外,後面節點是走訪到就把節點抓出來放到串列前端,
[{a,100},{b,200},{c,300},[]]
-> [{b,200}|[{a,100},{c,300},[]]]
-> [{c,300}|[{b,200}|[{a,100},[]]]]
-> [{c,300},{b,200},{a,100},[]]
串列倒排函數是
reverse([]) -> [];
reverse([Data,[]]) -> [Data,[]];
reverse([First,Second|Next]) -> [NH|NT] = reverse_partial([First|Next]),
[NH, Second | NT].
reverse_partial([F,S|Next]) -> [S | revesre([F|Next])].
但這樣寫起來好麻煩,倒是以下這種標準型好寫一點;只是缺點是慢一點點:
rev([]) -> [];
rev([H|T]) -> rev(T) ++ [H].
另外有比較快的,用一個額外的變數累積結果的技巧:
reverse(Any) -> rev(Any, []).
rev([], Result) -> Result;
rev([H|T], Part) -> rev(T, [H|Part]).

使用Python這種有函數風格的語言,
思考資料結構的方式或許不同,但內涵一樣有相當多的東西可引用.
這是我的一點意見.

※ 編輯: yauhh 來自: 61.231.68.175 (02/21 09:32)
Huangs:我不會 Erlang 語言 但這些資料結構底層的實作 02/21 09:27
Huangs:還是不脫 array, linked-list, tree, hash 等方式 02/21 09:27
Huangs:而這些實作方式都有不同的效率和使用時機 02/21 09:27
Huangs:O(N) vs. O(1) 之類的複雜度差異永遠存在 02/21 09:28
Huangs:高階語言只是把這些資料結構包裝起來了 問題仍然存在的 02/21 09:28
Huangs:看來只是用不同的語法在操作linked-list 02/21 09:37
Huangs:反而是你一開始的命題「linked-list綁C/C++等語言」的反例? 02/21 09:40
※ 編輯: yauhh 來自: 61.231.68.175 (02/21 09:49)
yauhh:不是,我覺得是在Erlang中,刻意做linked list雖然做出來, 02/21 09:51
yauhh:但卻是跟普通的資料型態一模一樣.結論是在Erlang根本不用做. 02/21 09:52
yauhh:我的reverse/1做錯了,果然,要直接對應仍然有些困難. 02/21 09:53

reverse/1改一下是
reverse([]) -> [];
reverse([LList,[]]) -> LList;
reverse([First,Second|Next]) when is_atom(First)
-> reverse([[Second,First,[]] | Next]);
reverse([First,Second|Next]) when is_list(First)
-> reverse([[Second|First] | Next]).
這樣符合前一段論述.

Huangs:那當有兩種 case 時: 大量 random access 和大量插入刪除 02/21 09:54
Huangs:在 Erlang 要如何選擇container? 02/21 09:55
※ 編輯: yauhh 來自: 61.231.68.175 (02/21 10:17)
yauhh:random access有Erlang Term Service和Dictionary可用 02/21 10:30
yauhh: Store 02/21 10:39
lovekkk:我以為 linked list 主要用處是插入資料方便? 02/21 10:42
lovekkk:長度的話 array 也可以用外部檔案分批存取來解決 02/21 10:43
lovekkk:linked list 要多存鏈結, 一次能讀入的資料搞不好還比較少 02/21 10:45
remmurds:陣列只有固定長度的問題不只有空間不夠 也包含空間浪費 02/21 10:48
lovekkk:沒關係, 有浪費問題表示...還夠用 :p 02/21 10:49
Huangs:所以說 Erlang 的程師設計師 仍然要了解Linked-list 02/21 16:11
Huangs:與array的特性 才能正確使用適合的資料結構 02/21 16:12
Huangs:所以並沒有因為選用了Erlang或其他高階語言 02/21 16:12
Huangs:linked-list就變得不重要啊 02/21 16:12
Huangs:說穿了 在高階語言上 即使沒有指標 02/21 16:14
Huangs:仍然是透過其他方式來操作 linked-list 02/21 16:14
ledia:推樓上 02/21 21:44
yauhh:不過,據個人所知,函數語言的程式改良比較不會在這小地方鑽. 02/22 00:41
yauhh:畢竟你說用錯資料結構,會有什麼機會用錯呢? 基本型態就幾種 02/22 00:42
yauhh:而已.實在是蠻難延用C語言處理資料空間的思考方式. 02/22 00:43
yauhh:嗯...我真的沒說linked list不重要,而是 "在Erlang談什麼 02/22 00:58
yauhh:linked list呢?" 意思是說,list本身就有linked list的彈性. 02/22 00:59
yauhh:所以像Python之流的函數語言,如前文所嗤笑的不懂linked list 02/22 00:59
yauhh:我個人是看不懂有什麼可笑的.不需要用就不要用,也很有效率啊 02/22 01:00
Huangs:Python 內建的 list 是用 array 實作 02/22 01:15
Huangs:當程式需要大量插入、刪除、搬移的時候 效率很差 02/22 01:15
Huangs:怎麼能夠說「不需要用就不要用,也很有效率啊」 @@ 02/22 01:15
TonyQ:有點像是要說過度最佳化的問題 , 不過我認為多瞭解點無妨. 02/22 01:34
yauhh:現在很明顯,你一直說這個,卻沒有給個很明確的示範告訴我 02/22 01:39
yauhh:為什麼*任何程式語言*都要懂array與linked list的差異. 02/22 01:40
yauhh:然而我卻給個直接的例子告訴你並非如此,用Python之類的討論 02/22 01:42
yauhh:資料結構時,對於linked list是想都不必想的. 02/22 01:42
Huangs:Python 也可以自己實作 linked-list 啊 02/22 01:46
Huangs:你 Google "python linked-list" 就有許多文章了 02/22 01:46
Huangs:怎麼會是"想都不用想"??? 02/22 01:46
yauhh:很明白告訴你了,特地做這個東西是白作工. 02/22 01:48
Huangs:當效能出現問題時候 就必須要有資料結構的知識 02/22 01:49
yauhh:就像現在,給你看了例子,你還是不信. 那我真沒輒. 02/22 01:49
Huangs:不論你用什麼語言 都要有這些知識 02/22 01:49
Huangs:有時甚至為了改善效能而必須用更合適的語言 02/22 01:50
Huangs:為什麼是白工? 兩者的時間複雜度可不一樣耶 02/22 01:50
yauhh:我手上有一本函數語言的演算法書籍,資料結構部份的確什麼都 02/22 02:00
yauhh:有,但是獨缺linked list. 那你是否覺得搞這個的白痴到不把 02/22 02:01
yauhh:linked list列入討論範圍? 02/22 02:01
yauhh:很抱歉,我沒跟你談各種資料結構,我只談linked list. 02/22 02:02
Huangs:拿一本書就可以證明 python 裡不需要 linked-list? 02/22 02:02
Huangs:你還沒解釋為什麼在python裡做linked-list是白工喔 :P 02/22 02:09
yauhh:Huangs兄,讓我告訴你二件殘酷的事實: 1) Erlang的list就是 02/22 12:22
yauhh:跟linked list一樣的東西,所以我沒有理由再實作linked list 02/22 12:22
yauhh:2) Erlang基本資料型態根本沒有array,所以何必硬說要知道 02/22 12:23
yauhh:array跟linked list的差別? 要用array可以掛上array模組, 02/22 12:23
yauhh:但是普通程式我根本不用考慮什麼array空間有限的問題. 02/22 12:24
yauhh:你不知道Erlang卻敢隨便說任何語言都要考慮array跟linked 02/22 12:25
yauhh:list的差異,我只覺得這是否言過其實了? 02/22 12:26
Huangs:那如果現在的case需要 random access,Erlang 怎麼辦? 02/22 13:53
Huangs:只好用內建的 linked-list 很慢的操作囉? 02/22 13:54
Huangs:而且你剛講得不是 python 嗎?怎麼又變回 Erlang 了? 02/22 13:54
Huangs:我不知道 Erlang 是否可以用 array 來作 random access 02/22 13:55
Huangs:但程式設計師在寫Erlang仍然必需意識到這麼問題 02/22 13:56
Huangs:如果遇到的case需要大量的random access 02/22 13:56
Huangs:那麼不支援random access的語言 可能就存在效能的問題 02/22 13:57
Huangs:當效能問題嚴重時 甚至必需換語言 02/22 13:57
Huangs:所以說用任何語言 都要考慮 array 與 linked-list 的差異 02/22 13:58
xvid:linked-list是資料結構 怎麼會綁語言呢... 02/22 19:56

你可能也想看看

搜尋相關網站