单向链表

链表是一种链式存储结构，物理层面是一段地址不一定连续的存储空间

结点是链表的最小单位，每个结点都有有唯一后继。

概念:

  • 首元节点：第一个有效的数据元素

  • 头节点：头节点是首元节点的前置节点，其数据域可不存放数据，也可以利用该数据区域存放链表节点个数等其他附加信息。

  • 头指针：指向链表的第一个节点。如果链表没有头节点，则头指针指向首元节点。如果链表存在头结点，则头指针指向头节点。

链表的存储结构

结点用LNode结构体表示，由存储数据data和指向下一个结构体的指针域组成。

特别的头指针使用*LinkList来表示一个链表，LNode用于表示节点，这样对链表和节点有很好的区分，可以提高代码的可读性。在后续的LNode *LocateElem(LinkList L,ElemType e);函数中我们可以发现传入的参数为链表，返回节点指针。

1
2
3
4
5
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

链表的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*初始化链表*/
Status InitList(LinkList &L);
/*头插法*/
Status HeadCreateList(LinkList &L);
/*尾插法*/
Status TailCreateList(LinkList &L);
/*获取第i个元素*/
Status GetElem(LinkList L,int i,ElemType &e);
/*按值查找节点并返回*/
LNode *LocateElem(LinkList L,ElemType e);
/*在第i个位置插入元素e*/
Status ListInsert(LinkList &L,int i,ElemType e);
/*删除第i个元素*/
Status ListDelete(LinkList &L,int i);
/*删除节点*/
Status DeleteNode(LNode &p);
/*遍历链表*/
Status PrintList(LinkList L);

链表初始化

在链表的初始化中，我们会申请一块内存，作为头节点，L指针存储头结点的地址。链表此时无元素，所以头节点的后继设为NULL。

1
2
3
4
5
6
7
8
/*初始化链表*/
Status InitList(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    if(L==NULL) return ERROR;
    L->next==NULL;
    return OK;
}

头插法和尾插法

头插法:在链表头结点之后进行插入。因此头插法得到的数据是逆序存放的。

头插法直接在头结点后面插入，执行效率高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*头插法*/
Status HeadCreateList(LinkList &L)
{
    int num;
    ElemType data;
    std::cin>>num;
    for(int i=0;i<num;i++){  
        std::cin>>data;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        if(!s)  return ERROR;
        s->data=data;
        s->next=L->next;
        L->next=s;
    }
    return OK;
}

尾插法:在链表尾部进行插入操作，得到顺序序列

尾插法每次需要从头开始逐个访问链表结点，将指针定位到链表的尾部，在尾部进行插入操作，为了提高效率，我们可以设置一个尾指针，指向链表尾部元素，每次插入元素后更新尾指针的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*尾插法创建链表*/
Status TailCreateList(LinkList &L)
{
    LNode *tail=L;
    int num;
    ElemType data;
    std::cin>>num;
    for(int i=0;i<num;i++){  
        std::cin>>data;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->next=NULL;
        if(!s) return ERROR;
        s->data=data;
        tail->next=s;
        tail=s;
    }
    return OK;
}

链表的删除操作

删除第i个元素。首先使用变量i记录当前访问的元素，开始时p指向首元节点，索引值为1。

当访问到链表尾部或当访问到第i-1的元素时停止向后访问。将第i-1个元素的后继设为第i-2个元素，释放第i个元素的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*删除第i个元素*/
Status ListDelete(LinkList &L,int i)
{
    int j=1;
    LNode* p=L->next;
    /*找到第i-1个元素*/
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p || j>i) return ERROR;
    LNode *s=p->next;
    p->next=s->next;
    free(s);
    return OK;
}

给定一个节点指针，如何将它删除呢?常规操作肯定是pre->next=pre->next->next;使用pre前驱节点来删除元素，当我们并没有待删除节p的前驱节点信息。我们只能删除该节点的后继节点，利用这一点，我们可以将后继节点的值赋给要删除的节点P，然后删除后继节点。使用这招偷梁换柱，便可以达到删除节点的效果。

1
2
3
4
5
6
7
8
9
/*删除节点*/
Status DeleteNode(LNode* p)
{
    LNode *s=p->next;
    p->data=s->data;/*拷贝后继节点的值到当前节点*/
    p->next=s->next;/*删除后继节点*/
    free(s);
    return OK;
}

链表的插入操作

在第i个位置进行插入操作。找到第i-1个节点p，待插入节点指向第i个节点(p->next),第i-1个节点再指向待插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*插入元素*/
Status ListInsert(LinkList &L,int i,ElemType e)
{
    int j=1;
    LNode* p=L->next;
    /*找到第i-1个元素*/
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    LNode* s=(LNode*)malloc(sizeof(LNode));
    if(!s) return ERROR;
    s->data=e;
    /* s指向第i个元素  */
    s->next=p->next;
    /* 第i-个元素指向s */
    p->next=s;
    return OK;
}

链表的遍历

1
2
3
4
5
6
7
8
9
10
Status PrintList(LinkList L)
{
    LNode *p=L->next;
    while(p){
        std::cout<<p->data<<"->";
        p=p->next;
    }
    std::cout<<std::endl;
    return OK;
}

单向循环链表

单项循环链表的尾节点指向头指针，而不是指向NULL。

链表结构

1
2
3
4
5
typedef struct Node
{
    int data;
    struct Node* next;
}Node;

初始化

1
2
3
4
5
6
7
struct Node* InitList()
{
    struct Node* L=(struct Node*)malloc(sizeof(struct Node));
    L->next=L;
    L->data=0;
    return L;
}

头插法和尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void HeadInsert(struct Node* L,int data)
{
    struct Node* node=(struct Node*)malloc(sizeof(struct Node));
    node->data=data;
    node->next=L->next;
    L->next=node;
    L->data++;
}
void TailInsert(struct Node* L,int data)
{
    struct Node* tail=L;
    struct Node* node=(struct Node*)malloc(sizeof(struct Node));
    node->data=data;
    while(tail->next!=L)
    {
        tail=tail->next;
    }
    node->next=L;
    tail->next=node;
    L->data++;
}

删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status DeleteVal(struct Node* L,int value)
{
    Node* pre=L;
    Node* cur=L->next;
    while(cur!=L){
        if(cur->data==value){
            pre->next=cur->next;
            free(cur);
            L->data--;
            return OK;
        }
        pre=cur;
        cur=cur->next;
    }
    printf("cant not find the value equal %d in the linklist\n",value);
    return ERROR;
}

遍历链表

1
2
3
4
5
6
7
8
9
10
void PrintList(struct Node* L)
{
    struct Node* node=L->next;
    printf("L->");
    while(node!=L){
        printf("%d->",node->data);
        node=node->next;
    }
    printf("L\n");
}

插入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status InsertNodeAfterVal(struct Node* L,int value,int node_data)
{
    struct Node* cur=L->next;
    struct Node* node=(struct Node*)malloc(sizeof(struct Node));
    node->data=node_data;
    while(cur!=L){
        if(cur->data==value){
            node->next=cur->next;
            cur->next=node;
            return OK;
        }
            cur=cur->next;
    }
    printf("cant not find the value equal %d in the linklist\n",value);
    free(node);
    return ERROR;
}

linux内核链表

链表

linux中的链表将数据域与指针域进行分离。

通过list_head怎么访问其他成员变量？

这就要依靠container_of宏了。指针域相对于结构体首地址的偏移量是固定的

指针域地址-相当偏移地址=结构体首地址。偏移量求解的办法offset宏

1
2
3
#define container_of(ptr,type,member)    \
        const typeof((type *)0->member) *_ptr=(ptr); \
        (type *)((char *)_ptr-offset(type,member))

offset是内置的函数，也可以用上面的方法实现

1
#define offset(type,member) (unsigned long)(&(type)(0)->member)

使用0地址作为结构体的起始地址，成员的地址就是相对与0号地址的偏移地址

链表头

静态创建链表头

1
2
3
4
struct Node Head{
    .data=data;
    .list=List_Head_Init(Head.list),
}

动态创建链表头

1
2
3
struct Node* HeadNode=malloc()
Head->data;
List_Head_Init(Head->list);

添加节点

在某一位置插入

1
list_add(struct list_head *new,struct list_head *head)

在尾部插入

1
list_add_tail(struct list_head *new,struct list_head *head);

删除节点

1
list_del(struct list_head *entry)

具体实现

1
2
3
4
5
6
7
static inline void __list_del(struct list_head *prev,struct list_head *next){
    next->prev=prev;
    prev->next=next;
}
static inline void list_del(struct list_head *entry){
    __list_del(entry->prev,entry->next);
}

是否为空

1
list_empty(struct list_head *head);

遍历链表

1
list_for_each(p,list)/*temp:临时递归的变量*/

p表示循环中的临时变量，list表示遍历的起始位置

遍历实体

可以这样遍历

1
2
3
4
list_for_each(p,list){
    entry=list_entry()
    //后续操作
}

进行封装

1
2
3
4
5
6
7
/*
 *    pos:list_entry的返回值
 *  head:头节点/遍历的起始位置
 *  member:list_head的名字
 */

list_for_each_entry(pos,head,member)
1
2
3
list_for_each_entry(pos,head,member){
    printf(pos->member)
}

反向遍历链表

1
list_for_each_reverse(pos,head,member)

线程安全的链表