※ 引述《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

例如,要做個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)
※ 編輯: yauhh 來自: 61.231.68.175 (02/21 09:49)

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]).
這樣符合前一段論述.

※ 編輯: yauhh 來自: 61.231.68.175 (02/21 10:17)