linux 循环双链表 list.h

1万 · 2016-3-25 10:52

双链表结构体一般如下

typedef struct __Node{
int data; 数据
struct __Node *pre; 指向前一个结点指针
struct __Node *next; 指向下一个结点指针
}Node;

而在linux下双链表结构体一般如下

struct list_head {
　　struct list_head *next, *prev;
};

struct i2c_dev {
struct list_head list;
struct i2c_adapter *adap;
struct device *dev;
};

区别很明显，第一个链表直接和结构体挂钩，链表指针指向的就是结构体本身，而第二个链表更纯粹，是单独，就是用来链接，没有特别的实际意义。显然第一种方式更容易理解，也更简单。为何linux不采用第一种方法，我猜想是为了更好的模块化。

试想一下如果采用第一种方法，不同的数据均要建立一个新链表结构，导致每一种链表都要实现一套插入、删除、遍历等功能函数，而函数实现其实都是一样，这样就很累赘，何不把链表单独提出来，因此有第二种方法。

让我们再看看第二种方式，它固定了双链表结构，以固定的成员变量出现（struct list_head list），不同的结构体都包含该同一类型链表，然后将链表链接起来。这也带来一个问题如何从链表这个成员变量获取该结构体中的其他成员变量（对应第一种很简单链表指针直接指向的就是结构体）？？？

1万 · 2016-3-25 10:53

如何从链表获取结构体变量，从而获取该结构体的真正需求的变量，例如上面例子中的struct i2c_adapter *adap;struct device *dev

linux 通过一个巧妙的函数实现了，container_of 实现通过结构中的某个变量获取结构本身的指针

#define container_of(ptr,type,member) ( {\ ---ptr指向的是type.member类型的数据，用来推算出以ptr指向的对象作为成员的结构体的起始地址

　　const typeof( ((type*)0)->member ) *__mptr=(ptr);\ ---typeof 是取变量的类型，例如 int a; typeof(a) b; //typeof(a) b 等同 int b

　　(type*)( (char*)__mptr - offsetof(type,member) );} )

#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER )

宏功能：获得一个结构体变量成员在此结构体中的偏移量。

1. ( (TYPE *)0 ) 将零转型为TYPE类型指针;
2. ((TYPE *)0)->MEMBER 访问结构中的数据成员;

3. &( ( (TYPE *)0 )->MEMBER )取出数据成员的地址，即相对于0的偏移量，要的就这个;
4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型，size_t应该最终为unsigned int类型。

struct i2c_dev i2c_dev_test;

container_of（&i2c_devtest.list, struct i2c_dev, list ）----通过i2c_devtest.list成员变量，返回i2c_dev_test的结构体的地址（指针）

1万 · 2016-3-25 10:54

static LIST_HEAD(i2c_dev_list);

#define LIST_HEAD(name) /
struct list_head name = { &name, &name }

struct i2c_dev *i2c_dev;

list_for_each_entry(i2c_dev, &i2c_dev_list, list) //从链表头i2c_dev_list开始向后循环，一直循环到链表尾, 对链表中对应的所有的struct i2c_dev结构体变量轮询一遍处理

#define list_for_each_entry(pos, head, member)             \ 链表是由pos.member为节点连接的。head是链表的头。搜寻整个链表，对pos类型的数据进行处理。
for (pos = list_entry((head)->next, typeof(*pos), member); \
      prefetch(pos->member.next), &pos->member != (head);  \
      pos = list_entry(pos->member.next, typeof(*pos), member))

#define list_entry(ptr,type,member)\

　　container_of(ptr,type,member)

双链表是循环的条件：尾结点的后指针指向头指针（头结点）, 头指针的前指针指向尾结点

1万 · 2016-3-25 12:26

楼主对双链表有什么运用经验没有？

1万 · 2016-3-25 14:14

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

1万 · 2016-3-25 14:16

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

1万 · 2016-3-25 14:28

线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
带头结点的双向循环链表的基本操作
void InitList(DuLinkList L)
{ /* 产生空的双向循环链表L */
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
L->next=L->prior=L;
else
exit(OVERFLOW);
}

销毁双向循环链表L
void DestroyList(DuLinkList L)
{
DuLinkList q,p=(*L)->next; /* p指向第一个结点 */
while(p!=*L) /* p没到表头 */
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
}

重置链表为空表
void ClearList(DuLinkList L) /* 不改变L */
{ 　DuLinkList q,p=L->next; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; /*头结点的两个指针域均指向自身 */
}

验证是否为空表
Status ListEmpty(DuLinkList L)
{ /* 初始条件：线性表L已存在
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}

1万 · 2016-3-25 16:06

都是泛泛而谈，没有具体的事例；

3万 · 2016-3-25 18:56

谢谢分享；

1万 · 2016-3-30 13:52

本帖最后由 huangcunxiake 于 2016-3-30 13:55 编辑

双向链表，顾名思义，就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表，主要有下面几个特点：

（1）在数据结构中具有双向指针

（2）插入数据的时候需要考虑前后的方向的操作

（3）同样，删除数据的是有也需要考虑前后方向的操作

那么，一个非循环的双向链表操作应该是怎么样的呢？我们可以自己尝试一下：

（1）定义双向链表的基本结构

typedef struct _DOUBLE_LINK_NODE
{
      int data;
      struct _DOUBLE_LINK_NODE* prev;
      struct _DOUBLE_LINK_NODE* next;

}DOUBLE_LINK_NODE;
（2）创建双向链表节点
DOUBLE_LINK_NODE* create_double_link_node(int value)
{
      DOUBLE_LINK_NODE* pDLinkNode = NULL;
      pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
      assert(NULL != pDLinkNode);

      memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
      pDLinkNode->data = value;
      return pDLinkNode;

}
（3）删除双向链表
void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
{
      DOUBLE_LINK_NODE* pNode;
      if(NULL == *pDLinkNode)
            return ;

      pNode = *pDLinkNode;
      *pDLinkNode = pNode->next;
      free(pNode);
      delete_all_double_link_node(pDLinkNode);

}
（4）在双向链表中查找数据
DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)
{
      DOUBLE_LINK_NODE* pNode = NULL;
      if(NULL == pDLinkNode)
            return NULL;

      pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
      while(NULL != pNode){
            if(data == pNode->data)
                     return pNode;
            pNode = pNode ->next;
      }

      return NULL;
}
  （5）双向链表中插入数据
STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
      DOUBLE_LINK_NODE* pNode;
      DOUBLE_LINK_NODE* pIndex;

      if(NULL == ppDLinkNode)
            return FALSE;

      if(NULL == *ppDLinkNode){
            pNode = create_double_link_node(data);
         assert(NULL != pNode);
            *ppDLinkNode = pNode;
            (*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
            return TRUE;
      }

      if(NULL != find_data_in_double_link(*ppDLinkNode, data))
            return FALSE;

      pNode = create_double_link_node(data);
      assert(NULL != pNode);

      pIndex = *ppDLinkNode;
      while(NULL != pIndex->next)
            pIndex = pIndex->next;

      pNode->prev = pIndex;
      pNode->next = pIndex->next;
      pIndex->next = pNode;
      return TRUE;
}

1万 · 2016-3-30 13:54

本帖最后由 huangcunxiake 于 2016-3-30 13:55 编辑

（6）双向链表中删除数据
STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
      DOUBLE_LINK_NODE* pNode;
      if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
            return FALSE;

      pNode = find_data_in_double_link(*ppDLinkNode, data);
      if(NULL == pNode)
            return FALSE;

      if(pNode == *ppDLinkNode){
            if(NULL == (*ppDLinkNode)->next){
                     *ppDLinkNode = NULL;
            }else{
                     *ppDLinkNode = pNode->next;
                     (*ppDLinkNode)->prev = NULL;
            }

      }else{
            if(pNode->next)
                  pNode->next->prev = pNode->prev;
         pNode->prev->next = pNode->next;
      }

      free(pNode);
      return TRUE;
}
（7）统计双向链表中数据的个数
int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)
{
      int count = 0;
      DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

      while(NULL != pNode){
            count ++;
            pNode = pNode->next;
      }
      return count;
}
（8）打印双向链表中数据
void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)
{
      DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

      while(NULL != pNode){
            printf("%d\n", pNode->data);
            pNode = pNode ->next;
      }
}

linux 循环双链表 list.h

技术导师奖章

七世轮回

沉静之湖泊

突出贡献奖章

技术领袖奖章

十世金身

坚毅之洋流

荣誉元老奖章