2014年2月1日 星期六

javascript實作資料結構-LinkedList


簡介:

LinkedList為目前常用的資料結構之一,其優點在於加入、刪除節點時只需要O(1)的常數時間,且空間配置為動態,不像使用Array時須事先配置空間大小,如此一來若需求之空間較配置的空間大的情況之下,LinkedList必優於Array,因陣列需要重新配置空間大小並且逐一搬移,但LinkedList仍有其不足之地,e.g尋訪時需耗時O(n),無法像Array一般以索引尋訪。

功能操作:

通常各程式語言皆提供設計好之套件以供存取,常見功能。
1.addFirst();//插入首節點之前
2.addLast();//插入於尾端
3.addBefore(n);//插入某節點之前
4.addAfter(n);//插入某節點之後
4.size();//節點大小
5.search(n);//搜尋節點位置
6.remove(n);//刪除某節點

資料結構種類:

1.雙向鏈結(可取得上一節點位置)
2.環狀鏈結
3.堆疊
4.佇列
5.樹狀

刪除示意圖:



沒有留言:

張貼留言