Zend引擎中實現了很多基本的數據結構，這些接口貫穿PHP和Zend引擎的始末，這些數據結構以及相應的操作接口都可以作為通用的接口來使用。本小節再簡單描述一下 在Zend引擎中HashTable的使用非常頻繁，這得益于他良好的查找性能，如果讀者看過前一小節會知道哈希表會預先分配內容以提高性能，而很多時候數據規模不會很大，固然使用哈希表能提高查詢性能，但是某些場景下并不會對數據進行隨機查找，這時使用哈希表就有點浪費了。 Zend引擎中的鏈表是[雙鏈表](http://zh.wikipedia.org/wiki/%E5%8F%8C%E9%93%BE%E8%A1%A8)，通過雙鏈表的任意節點都能方便的對鏈表進行遍歷。 > Zend引擎的哈希表實現是哈希表和雙鏈表的混合實現，這也是為了方便哈希表的遍歷。 鏈表的實現很簡單，通常只需要三個關鍵元素： 1. 指向上個元素的指針 1. 指向下個元素的指針 1. 數據容器 Zend引擎的實現也很簡單，如下兩個是核心的數據接口，第一個是元素節點，第二個是鏈表容器。 typedef struct _zend_llist_element { struct _zend_llist_element *next; struct _zend_llist_element *prev; char data[1]; /* Needs to always be last in the struct */ } zend_llist_element; ? typedef struct _zend_llist { zend_llist_element *head; zend_llist_element *tail; size_t count; size_t size; llist_dtor_func_t dtor; unsigned char persistent; zend_llist_element *traverse_ptr; } zend_llist; 節點元素只含有前面提到的3個元素，第三個字段data和哈希表的實現一樣，是一個柔性結構體。  Zend zend_llist結構 如上圖所示，data字段的空間并不是只有一個字節，我們先看看元素插入的實現： ZEND_API void zend_llist_add_element(zend_llist *l, void *element) { zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent); ? tmp->prev = l->tail; tmp->next = NULL; if (l->tail) { l->tail->next = tmp; } else { l->head = tmp; } l->tail = tmp; memcpy(tmp->data, element, l->size); ? ++l->count; } 如方法第一行所示，申請空間是額外申請了`l->size - 1`的空間。`l->size`是在鏈表創建時指定的，`zend_llist_element`結構體最后那個字段的注釋提到這個字段必須放到最后也是這個原因，例如curl擴展中的例子：`zend_llist_init(&(*ch)->to_free->slist, sizeof(struct curl_slist), (llist_dtor_func_t) curl_free_slist, 0);`, `size`指的是要插入元素的空間大小，這樣不同的鏈表就可以插入不同大小的元素了。 為了提高性能增加了鏈表頭和尾節點地址，以及鏈表中元素的個數。 最后的traverse_ptr 字段是為了方便在遍歷過程中記錄當前鏈表的內部指針，和哈希表中的:`Bucket *pInternalPointer;`字段一個作用。 ### 操作接口 操作接口比較簡單，本文不打算介紹接口的使用，這里簡單說一下PHP源代碼中的一個小的約定， 如下為基本的鏈表遍歷操作接口： /* traversal */ ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos); ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos); ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos); ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos); ? #define zend_llist_get_first(l) zend_llist_get_first_ex(l, NULL) #define zend_llist_get_last(l) zend_llist_get_last_ex(l, NULL) #define zend_llist_get_next(l) zend_llist_get_next_ex(l, NULL) #define zend_llist_get_prev(l) zend_llist_get_prev_ex(l, NULL) 一般情況下我們遍歷只需要使用后面的那組宏定義函數即可，如果不想要改變鏈表內部指針，可以主動傳遞當前指針所指向的位置。 PHP中很多的函數都會有`*_ex()`以及不帶ex兩個版本的函數，這主要是為了方便使用，和上面的代碼一樣，ex版本的通常是一個功能較全或者可選參數較多的版本，而在代碼中很多地方默認的參數值都一樣，為了方便使用，再封裝一個普通版本。 這里之所以使用宏而不是定義另一個函數是為了避免函數調用帶來的消耗，不過有的情況下還要進行其他的操作，也是會再定義一個新的函數的。