二 链表
1.链表节点使用ListNode结构，是一个双向的链表，同时，还实现了一个控制所有ListNode的结构list:
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
typedef struct list { // 表头节点 listNode *head; // 表尾节点 listNode *tail; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void (*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr, void *key); // 链表所包含的节点数量 unsigned long len; } list;
由list和listnode组成的基本结构如下，可见
- listNode里的prev和next构成双向列表
- list.head和list.tail使访问头尾node的复杂度为o(1)
- 头Node的prev和尾node的next指向NULL，不会成环
- list.len使访问list长度的复杂度为o(1)
- 多态：通过list.match，list.free和list.dup来实现多态，即支持各种类型的listnode.value
