Re: [問題] linked list& array

[adrianshum (Alien)]

※ 引述《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)
→ Lordaeron:你這樣只能叫用link來實作link
→ Lordaeron:Link是資料存放的方法, stack是處理資料
→ Lordaeron:的方式. 兩個是不同的東西
→ adrianshum:這裡要表達的就是如果把 Linked List
→ adrianshum:抽象化成一種 interface, 代表其 data
→ adrianshum:iteration 的方法，這裡的 Linked List
→ adrianshum:就不再是一種資料存放的方法。這裡和上
→ adrianshum:一篇要說的大概就是這種意思。實際上出
→ adrianshum:來的結果可能沒有什麼價值可是重點是在
→ adrianshum:於抽象化的思考過程。
→ yoco315:通常(通常)array會要求O(1) random access
→ yoco315:可能的話還會要求連續記憶空間..