链表（C）

本文主要说明C的链表实现，方式来源于rt-thread，实际好像是来源于linux内核，后者没看过，不清楚咯。这种链表就很科学，通用性很高。也扔到了github仓库中，list文件夹下。

1 双向链表

1.1 与传统链表的不同

传统链表是怎么实现的呢，随便搜索”链表 C”打开个链接都基本相同，定义一个结构体，然后结构体的一个成员是一个指向此结构体的指针。如下:

typedef struct sLinkList{
    int data;
    struct sLinkList *next;
} LinkList;

这种方式就很死板，不同使用场景就需要定义新的结构体，实现新的链表。但接下来这种方式就把链表相关操作抽取了出来，弄成了一个可重复利用的工具。

1.2 使用

首先来看看这种链表的使用方式

• 定义新的结构体，只需要加入一个链表成员即可

  typedef struct text
  {
  	int data;
  	list_t list;
  	int data2;
  }test_t;
  
  typedef struct text2
  {
  	int data;
  	list_t list;
  }test_t2;

• 然后将三个结构体数据连接起来

  //三个示例的节点，链表部分为0则表示未连接状态
  static test_t node1={1,{0,0},1};
  static test_t node2={2,{0,0},2};
  static test_t node3={3,{0,0},3};
  
  //将三个节点关联起来
  void main()
  {
      list_t head;//新建了一个链表，关联所有加入的节点
      list_init(&head);
  
      //分别将节点加入
      list_inster_after(&head,&node1.list);
      list_inster_after(&head,&node2.list);
      list_inster_after(&head,&node3.list);
  }

• 然后就是获取链表中节点的信息

  void test(list_t *head)
  {
      test_t *object;
      printf("len=%d\n",list_len(head));
  
      list_t *temp=0;
      //轮询链表，第一个节点为头指针所指所以是temp=head->next
      //由于是循环链表，所以最后一个节点指向了头temp!=head
      //切换到下一个节点temp=temp->next
      for(temp=head->next;temp!=head;temp=temp->next)
      {
          //使用此宏可以由结构体的链表成员得到此节点的首地址
          object = LIST_ENTER(temp,test_t,list);
          printf("node:data=%d\n",object->data);
      }
  }

1.3 实现

1.3.1 获取结构体首地址的关键宏

/*!
 * @brief 成员地址-成员偏移=首地址
 * &((type *)0)->member :将0转化为结构体指针，则起始地址为0，然后成员以0为基础进行偏移，所得的便是member成员的偏移量
 * (char *)(ptr)：控制运算时步长为1字节
 */
#define LIST_ENTER(ptr, type, member) \
    ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

不看看别人的代码长长见识，我自己想是肯定弄不出这么巧妙的方式的。
这里通过传入结构体链表成员指针、结构体、结构体链表成员来计算结构节点的首地址。
我们都知道，在实例一个结构体的时候，里面成员存储位置是连续的，例如下列结构体

typedef struct tt
{
    char a;
    char b;
    char c;
}tt_t;
tt_t t;

如果t.a的地址是0x407970，那么t.b的地址则是0x407971，&((tt_t *)0)->b的意思则是如果t.a的地址是0，那么t.b的地址是多少呢，很显示就是1了，这样就得到了改成员相较于首地址的偏移量。
所以在实际下列结构体时，我们先知道了一个指针指向了list_t list这个成员，然后也知道了改成员相较于首地址的便宜了，那么直接相减便得到了节点的首地址咯。

typedef struct text
{
	int data;
	list_t list;
	int data2;
}test_t;

1.3.2 初始化链表

这里函数均使用了内联的方式，也就在调用的时候是直接将函数代码复制到相应位置的。
初始化也即将头节点的首尾指针相连接。

/*!
 * 环形链表
 */
struct sList
{
    struct sList *next;                         
    struct sList *prev;                          
};
typedef struct sList list_t;    

static __inline void list_init(list_t *l)
{
    l->next = l->prev = l;
}

1.3.3 插入新节点

/**
 * @brief 在指向链表节点前插入
 * @param l 插入的链表
 * @param n 新节点
 */
static __inline void list_inster_after(list_t *l, list_t *n)
{
    l->next->prev = n;
    n->next = l->next;

    l->next = n;
    n->prev = l;
}

/**
 * @brief 在指向链表节点后插入
 * @param l 插入的链表
 * @param n 新节点
 */
static __inline void list_insert_before(list_t *l, list_t *n)
{
    l->prev->next = n;
    n->prev = l->prev;

    l->prev = n;
    n->next = l;
}

1.3.4 删除新节点

/**
 * @brief 从链表中删除此节点
 * @param n 待删除节点.
 */
static __inline void list_remove(list_t *n)
{
    n->next->prev = n->prev;
    n->prev->next = n->next;

    n->next = n->prev = n;
}

1.3.5 获取链表长度

仍然传入链表头，然后轮询，直到最后一个节点指向了链表头

/**
 * @brief 获取链表长度
 * @param l the list to get.
 */
static __inline unsigned int list_len(const list_t *l)
{
    unsigned int len = 0;
    const list_t *p = l;
    while (p->next != l)
    {
        p = p->next;
        len ++;
    }

    return len;
}