欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

双向链表

程序员文章站 2022-05-12 16:25:09
...

1、双向链表定义

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

2、双向链表的存储结构

线性表的双向链表存储结构

typedef struct DuLNode
{
   ElemType data;
   struct DuLNode *pre,*next;
}DuLNode,*DuLinkList;

双向链表

从上述的双向链表的存储结构可以看出,前后的指针与节点是一体的。

3、插入

双向链表

void insertNode(DuLNode *New, DuLNode *Pre,DuLNode *Next)
{
    Next->pre = New;
    New->pre = Pre;
    New->next = Next;
    Pre->next = New;
}

4、删除

双向链表

void delNode(DuLNode *Pre,DuLNode *Next)
{
    Pre->next = Next->next;
    Next->next->pre = Pre;

    delete Next;
}

5 linux内核双向链表实现

5.1 定义

内核的双链表设计成了一种侵入式的结构,只定义了链表的前驱与后继的指针,使用时将这个结构放在要使用链表的结构中。

定义如下:
linux-3.0.35\include\linux\Types.h

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

5.2 如何获取数据

只有链表的指针,那么如何取到节点的数据呢?这就不得不说到一个宏了:

#define container_of(ptr, type, member) ({          \
    const typeof(((type *)0)->member)*__mptr = (ptr);    \
             (type *)((char *)__mptr - offsetof(type, member)); })

双向链表

参考

http://ds.hitwh.edu.cn/Class.asp?ID=21
https://blog.csdn.net/murphykwu/article/details/47417047

相关标签: struct