结构设计

传统的单向链表是根据结点开始书写的，数据域存放用户创建数据的指针，假设用户创建的数据仍然是 Person 类型的结构体，传统链表的结构如下图。

  1. typedef struct person {
  2.     char name [64];
  3.     int age;
  4. } Person;

链表的功能就是将数据连接起来，那么我们不需要非得依托于创建结点来实现数据结构。我们可以在用户端的数据上进行连接（Person 结构体），这样就可以避免多使用一个 void* 指针来指向数据，同时也可以将任意类型的数据连接起来。

  1. typedef struct linkNode {
  2.     struct linkNode * next;
  3. } LinkNode;
  5. typedef struct person {
  6.     struct LinkNode node; // 任意指针都可
  7.     char name[64];
  8.     int age;
  9. } Person;

用户所做的就是在每个数据顶部上空出一个指针的大小（通常是一个只有一个指针的结构体，指针指向下一块数据，是否取结构体指针不重要），在书写链表的 API 时，我们只假设我们拿到的前四/八个字节，其他字节为用户自定义的区域。

  1. typedef struct {
  2.     LinkNode node;
  3.     char name [64];
  4.     int age;
  5. } Person;

我们仍然需要一个结构体来表示整个链表，LList 的头结点尽量不要是指针，不然还得额外初始化头结点。

  1. typedef struct linkNode {
  2.     struct linkNode * next;
  3. } LinkNode;
  5. typedef struct {
  6.     LinkNode pHeader;
  7.     int size;
  8. } LList;
  10. typedef void* LinkList;

初始化

  1. LinkList init() {
  2.     LList* llist = (LList*)malloc(sizeof(LList));
  3.     if (llist == NULL) {
  4.         return NULL;
  5.     }
  7.     llist->pHeader.next = NULL;
  8.     llist->size = 0;
  10.     return (LinkList)llist;
  11. }

插入

  1.  void insert(LinkList list, void* data, int index) {
  2.     if (data == NULL || list == NULL || index < 0) {
  3.         return;
  4.     }
  5.     LList* llist = (LList*)list;
  7.     if (index > llist->size) {
  8.         return;
  9.     }
  11.     LinkNode * myNode = (LinkNode*)data; // 取出前四个字节来用
  12.     LinkNode* pCurrent = &(llist->pHeader);
  14.     for (int i = 0; i<index; i++) {
  15.         pCurrent = pCurrent->next;
  16.     }
  18.     myNode->next = pCurrent->next;
  19.     pCurrent->next = myNode;
  21.     llist->size += 1;
  22. }

遍历

  1. void travel(LinkList list, void (*callback)(void*)) {
  2.     if (list == NULL) {
  3.         return;
  4.     }
  5.     LList* llist = (LList*)list;
  6.     LinkNode* pCurrent = llist->pHeader.next;
  8.     for (int i = 0; i<llist->size; i++) {
  9.         callback(pCurrent);
  10.         pCurrent = pCurrent->next;
  11.     }
  12. }

删除

  1. void remove(LinkList list, int index) {
  2.     if (list == NULL) { 
  3.         return;
  4.     }
  5.     LList* llist = (LList*)list;
  7.     if (index < 0 || index > llist->size-1) {
  8.         return;
  9.     }
  11.     LinkNode* pCurrent = &(llist->pHeader);
  13.     for (int i = 0; i < index; i++) {
  14.         pCurrent = pCurrent->next;
  15.     }
  17.     LinkNode* pDel = pCurrent->next;
  19.     pCurrent->next = pDel->next; // 不要 free 掉 pDel 这是用户数据
  21.     pDel->next = NULL;
  23.     llist->size -= 1;
  24. }

销毁

  1. void destory(LinkList * list) {
  2.     if (list == NULL) {
  3.         return;
  4.     }
  5.     LList* llist = (LList*)(*list);
  6.     LinkNode* pCurrent = &(llist->pHeader);
  7.     LinkNode* pNext = llist->pHeader.next;
  8.     while (pNext != NULL) {
  9.         pCurrent->next = NULL;
  10.         pCurrent = pNext;
  11.         pNext = pNext -> next;
  12.     }
  14.     pCurrent->next = NULL;
  16.     free(*list);
  17.     *list = NULL;
  18. }

测试

  1. void myPrintf(void* data) {
  2.     Person* person = (Person*)data;
  3.     printf("%s,%d\n", person->name, person->age);
  4. }