2. 链表

相关文件

adlist.h
adlist.c

1. 定义

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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;

• dup函数用于复制链表节点所保存的值
• free函数用于释放链表节点所保存的值
• match函数则用于对比链表节点的值和另一个值是否相等

特点

1. 双端链表

   访问前置和后置节点的时间复杂度都是O(1)

2. 链表表头和表尾的listNode节点的prev和next都是NULL，对链表访问以NULL为终点

3. list中保存有表头和表尾指针，方便访问

4. list中保存有链表长度

5. 多态：listNode使用void*来保存节点值，可以通过list中的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。下面的代码给出int和double的支持。

   int int_match(void *ptr, void *key) {
       int v1 = (*(int *)ptr);
       int v2 = (*(int *)key);
       return v1 == v2;
   }
   
   int double_match(void *ptr, void *key) {
       double v1 = (*(double *)ptr);
       double v2 = (*(double *)key);
       return v1 == v2;
   }
   
   void cmp(int flag){
       if(flag) printf("true\n");
       else printf("false\n");
   }
   
   int main() {
       struct list int_list;
       struct list double_list;
   
       int_list.match = int_match;
       double_list.match = double_match;
       
       struct listNode int_node;
       int* v1 = malloc(sizeof(int));
       *v1 = 1;
       int_node.value = v1;
       int v2 = 1;
       cmp(int_list.match(int_node.value, &v2));
   
       struct listNode double_node;
       double* v3 = malloc(sizeof(double));
       *v3 = 2.0;
       double_node.value = v3;
       double v4 = 2.0;
   
       cmp(double_list.match(double_node.value, &v4));
   }