作者adrianshum (Alien)
看板Programming
標題Re: [問題] linked list& array
時間Fri Feb 25 17:26:58 2011
※ 引述《yauhh (喲)》之銘言：
[43]
:
※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 218.160.212.40
: → loveme00835:你真的很屌...回得出這個 140.121.197.115 02/25 13:14
: → loveme00835:stack 可以實作 linked list, 那stack 140.121.197.115 02/25 13:35
: → loveme00835:要用什麼實作? 難道用 linked list? 140.121.197.115 02/25 13:36
: → adrianshum:樓上大概沒看懂原po的意思.你把linked 61.238.156.185 02/25 16:45
: → adrianshum:list 看成是一種實作那當然覺得別扭.原 61.238.156.185 02/25 16:46
: → adrianshum:po想說的,就是你可以把 array/linked 61.238.156.185 02/25 16:46
: → adrianshum:list 想成一種interface 一種協定. 61.238.156.185 02/25 16:47
: → adrianshum:那麼, 底層用任何的stack impl 來達成y 61.238.156.185 02/25 16:50
: → adrianshum:這協定, 就是原po 要解決的問題 61.238.156.185 02/25 16:51
: → loveme00835:這個叫做介面配接, 不叫實作 140.121.197.115 02/25 16:54
: → loveme00835:而原PO問的就是"製作" 140.121.197.115 02/25 16:56
我乾脆來回文好了.
你所謂的 "配接" 和實作根本是沒有衝突的概念.
重點的是你大概還是不太明白原 po 的用意:
大家說: 用 stack 實作 linked list 或 array 不合理,
是建基於大家把 array & linked list 想成是一
種實作.
不過, 為什麼不能把 array & linked list 想成是一種
介面呢?
舉個例子, 假設我寫個 Stack impl, 是建基於任一 List,
大家會覺得很正常.
e.g.
interface List<T> {
T get(int index);
void insert(T data, int index);
T remove(int index);
} // 很正常的基本 List interface
interface Stack<T> {
push(T);
T pop();
} // 基本的 Stack Interface
class MyStackImpl<T> {
private list List<T>;
MyStackImpl(List<T> list) {
this.list = list;
}
void push(T data) {
this.list.insert(data, 0);
}
T pop() {
return this.list.remove(0);
}
};
這種 "以 list 來實作 stack" 大家應該看得很舒服對吧?
用 stack 實作 Linked List 又是什麼一回事?
我們為什麼不可以把 LinkedList 想成一個 interface?
interface LinkedList<T> {
Node<T> getHead();
}
interface Node<T> {
T getData();
Node<T> getNext();
setNext(LinkedListNode<T> next);
}
為什麼我們不可以利用 stack 來實作這樣的 interface?
class MyLinkedList<T> {
Stack<MyNode<T>> nodes;
class MyNode<T> implements Node<T> {
MyLinkedList<T> myList;
...
Node<T> getNext() {
Stack<T> tmpNodeStack = new StackImpl<T>();
myList.nodes 一個個 pop 出來, 直到找到 this;
result = myList.pop();
把 result & tmpNodeStack 一個個push 回 myList;
return result;
}
// setNext 不難自己想了吧?
}
.....
}
這樣不就是 "利用 stack 來實作 linked list" 了嗎?
最重點的是, 你要明白, 你看起來好像是實作手段的東西 (linked list),
經過思考和設計, 其實也可以設計成一個協定.
沒錯, 這樣的 LinkedList interface 實際應用上未必有什麼價值, 可是
整篇文章中最有價值的不是 LinkedList interface, 而是怎麼去看事物和抽象化
的過程.
Alien
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.238.156.185
※ 編輯: adrianshum 來自: 61.238.156.185 (02/25 17:29)
1F：→ Lordaeron:你這樣只能叫用link來實作link118.160.171.237 02/26 01:31
2F：→ Lordaeron:Link是資料存放的方法, stack是處理資料118.160.171.237 02/26 01:31
3F：→ Lordaeron:的方式. 兩個是不同的東西118.160.171.237 02/26 01:32
4F：→ adrianshum:這裡要表達的就是如果把 Linked List 183.179.61.91 02/26 04:38
5F：→ adrianshum:抽象化成一種 interface, 代表其 data 183.179.61.91 02/26 04:39
6F：→ adrianshum:iteration 的方法，這裡的 Linked List 183.179.61.91 02/26 04:39
7F：→ adrianshum:就不再是一種資料存放的方法。這裡和上 183.179.61.91 02/26 04:40
8F：→ adrianshum:一篇要說的大概就是這種意思。實際上出 183.179.61.91 02/26 04:41
9F：→ adrianshum:來的結果可能沒有什麼價值可是重點是在 183.179.61.91 02/26 04:41
10F：→ adrianshum:於抽象化的思考過程。 183.179.61.91 02/26 04:42
11F：→ yoco315:通常(通常)array會要求O(1) random access 118.160.111.92 02/26 14:20
12F：→ yoco315:可能的話還會要求連續記憶空間.. 118.160.111.92 02/26 14:20