簡介
SPL是用于解決典型問題(standard problems)的一組接口與類的集合，包括數(shù)據(jù)結(jié)構(gòu)、迭代器钮科、接口、異常等婆赠。鏈表是一種物理存儲單元上非連續(xù)绵脯、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成蛆挫，結(jié)點可以在運行時動態(tài)生成赃承。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域璃吧。 相比于線性表順序結(jié)構(gòu)楣导，操作復(fù)雜。由于不必須按順序存儲畜挨，鏈表在插入的時候可以達(dá)到O(1)的復(fù)雜度筒繁，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間巴元，而線性表和順序表相應(yīng)的時間復(fù)雜度分別是O(logn)和O(1)毡咏。
雙向鏈表在PHP SPL里面有2種實現(xiàn)，一種是棧逮刨，特性是FIFO（first input first output）呕缭，先進(jìn)先出，就像咱排隊上地鐵一樣修己，排在前面的先上地鐵恢总；還有一種是隊列。特性是LIFO（last input first output）睬愤，后進(jìn)先出片仿，這個看上去有點不合常理，在日常生活中的例子就是往箱子里面放東西尤辱，你肯定要把后面放進(jìn)去的東西先拿出來才能拿最底下的東西砂豌。在SPL里面，全部提供了實現(xiàn)光督，這個比你自己實現(xiàn)效率高多了阳距。
1.類摘要
SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
/* 方法 */
public __construct ( void )
public void add ( mixed $index , mixed $newval ) #添加一個元素
public mixed bottom ( void )
public int count ( void )
public mixed current ( void ) # 返回當(dāng)前指針指向的元素
public int getIteratorMode ( void ) # 返回迭代模式
public bool isEmpty ( void )
public mixed key ( void )
public void next ( void ) # 移動指針到下一個元素
public bool offsetExists ( mixed $index )
public mixed offsetGet ( mixed $index )
public void offsetSet ( mixed $index , mixed $newval )
public void offsetUnset ( mixed $index )
public mixed pop ( void ) # 彈出一個元素，從隊列頭出列
public void prev ( void )
public void push ( mixed $value ) # 增加一個元素结借，從隊列頭入列
public void rewind ( void ) # 初始化隊列
public string serialize ( void )
public void setIteratorMode ( int $mode ) # 設(shè)置迭代模式筐摘，棧或者隊列
public mixed shift ( void ) # 彈出一個元素船老，從隊列尾出列
public mixed top ( void )
public void unserialize ( string $serialized )
public void unshift ( mixed $value ) # 增加一個元素咖熟，從隊列尾入列
public bool valid ( void )
}
2.實例
<?php
$dll = new SplDoublyLinkedList();
# 添加元素
$dll->add(0, 'a');
$dll->add(1, 'b');
$dll->add(2, 'c');
$dll->add(3, 'd');
# 遍歷鏈表，這個迭代模式有4種,源碼里面定義的內(nèi)容
# const IT_MODE_LIFO = 2; 后進(jìn)先出努隙，其實就是棧
# const IT_MODE_FIFO = 0; 先進(jìn)先出球恤，其實就是隊列
# const IT_MODE_DELETE = 1; 刪除元素
# const IT_MODE_KEEP = 0; 保持原來的順序
$dll->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
for ($dll->rewind(); $dll->valid(); $dll->next()) {
var_dump($dll->current()) . "\n";
}
3.總結(jié)
平時寫業(yè)務(wù)代碼很少用到這些東西辜昵，不過很多PHP框架其實都用到這些了荸镊，一些庫的底層也用到了，畢竟數(shù)據(jù)結(jié)構(gòu)都是通用的，了解一下還是不錯滴
