Re: [問題] linked list& array

看板Programming作者adrianshum (Alien)時間14年前 (2011/02/25 17:27)推噓0(0推 0噓 12→)

留言12則, 3人參與討論串3/9 (看更多)

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