数据结构

listNode

  1. typedef struct listNode {
  3.     // 前置节点
  4.     struct listNode *prev;
  6.     // 后置节点
  7.     struct listNode *next;
  9.     // 节点的值
  10.     void *value;
  12. } listNode;
  1.        +--------+   +--------+   +--------+
  2. ... -->|listNode|-->|listNode|-->|listNode|--> ...
  3.        |--------|   |--------|   |--------|
  4. ... <--| value  |<--| value  |<--| value  |<-- ...
  5.        +--------+   +--------+   +--------+

list

  1. typedef struct list {
  3.     // 表头节点
  4.     listNode *head;
  6.     // 表尾节点
  7.     listNode *tail;
  9.     // 链表所包含的节点数量
  10.     unsigned long len;
  12.     // 节点值复制函数
  13.     void *(*dup)(void *ptr);
  15.     // 节点值释放函数
  16.     void (*free)(void *ptr);
  18.     // 节点值对比函数
  19.     int (*match)(void *ptr, void *key);
  21. } list;
  1. +-----+
  2. |list |
  3. |-----|               +--------+   +--------+   +--------+ 
  4. |head |-------------->|listNode|-->|listNode|-->|listNode|--> NULL
  5. |-----|               |--------|   |--------|   |--------|
  6. |tail |--+    NULL <--| value  |<--| value  |<--| value  |<---+        
  7. |-----|  |            +--------+   +--------+   +--------+    |
  8. |len  |  +----------------------------------------------------+
  9. |-----|
  10. |dup  |--> ...
  11. |-----|
  12. |free |--> ...
  13. |-----|
  14. |match|--> ...
  15. +-----+

PS：和 java.util.LinkedList 相似

特性

  1. 双向：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是 O(1)；
  2. 无环：表头节点的 prev 指针和表尾的 next 指针都指向 null，对链表的访问以 null 为终点；
  3. 带表头和表尾指针：通过 list 的 head 和 tail 指针，获取链表的表头节点和表尾节点时间复杂度为 O(1)；
  4. 带链表长度计数器：通过 len 属性来对链表节点进行计数，获取链表的节点数量时间复杂度为 O(1)；
  5. 多态：链表节点受用 void* 指针来保存节点值，所以链表可以用于保存各种不同类型的数据。