作者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