链表

单向链表

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

链表的头指针标志着链表的起始位置

结点是链表的最小单位，每个结点都有有唯一指向

存储结构

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

在头结点中，data用于表示链表的结点个数

在非头结点中,data存放数据元素

typedef struct Node
{
	int data;
	struct Node* next;
}Node;

链表初始化

链表节点数为0,头结点指针域指向空，头结点的data域为零

struct Node* InitList()
{
	struct Node* L=(struct Node*)malloc(sizeof(struct Node));
	L->next=NULL;
	L->data=0;//记录结点个数，初始节点数为0
	return L;
}

头插法和尾插法

头插法:在链表头结点之后进行插入

给定一个序列1,2,3,4,5使用头插法进行插入，得到的链表序列为5,4,3,2,1

//头插法，顺序存放
void HeadInsert(struct Node* L,int data)
{
	struct Node* p=(struct Node*)malloc(sizeof(struct Node));
	p->data=data;
	p->next=L->next;//新结点指向首结点
	L->next=p;//头结点指向新结点，新结点成为首结点
	L->data++;
}

尾插法

通过逐个访问链表结点，将指针定位到链表的尾部，在尾部进行插入操作

//尾插法，逆序存放
void TailInsert(struct Node* L,int data)
{	
	struct Node* p=L;
	struct Node* node=(struct Node*)malloc(sizeof(struct Node));
	node->data=data;
	node->next=NULL;
	while(p->next!=NULL)//定位到尾结点
	{
		p=p->next;	
	}
	p->next=node;//尾部插入
	L->data++;

}

链表的删除操作

按索引删除时

index变量用于记录当前指针指向结点的索引，当前索引值等于要删除结点的索引值时进行删除操作

通过将当前结点的前驱结点指针域指向当前结点的后继结点完成删除操作，

使用双指针pre和cur分别记录当前结点的前驱结点和当前结点，以便进行删除

//按位删除，删除第K个结点
Status DeleteKth(struct Node* L,int k)
{
	int index=0;//索引从0开始
	struct Node* pre=L;//前驱结点，便于删除
	struct Node* cur=L->next;
	//超出结点数量
	if(k>(L->data)){
		printf("k out of range\n");
		return ERROR;
	}
	while(cur!=NULL){
		if(index==k){
			pre->next=cur->next;//改变前驱结点的指针指向
			L->data--;
			free(cur);
			return OK;
		}
		else{
			index++;
			pre=cur;
			cur=cur->next;
		}
	}
	return OK;
}		

按值删除

在遍历结点过程中，如果当前结点的值等于要删除结点值时，改变当前结点的前驱结点指针域

//按值删除
Status DeleteValue(struct Node* L,int value)
{
	struct Node* pre=L;
	struct Node* cur=L->next;
	while(cur!=NULL){
		if(cur->data==value){
			pre->next=cur->next;
			L->data--;
			free(cur);
			return OK;
		}
		else{
			pre=cur;
			cur=cur->next;
		}
	}	
	printf("not find the node value equal %d\n",value);
	return ERROR;

}

链表的插入操作

//在值为value的结点之前插入
Status InsertValBefore(struct Node* L,int value,int data)
{
	struct Node* pre=L;
	struct Node* cur=L->next;
	struct Node* node=(struct Node*)malloc(sizeof(struct Node));
	node->data=data;
	node->next=NULL;
	while(cur!=NULL){
		if(cur->data==value){
			node->next=cur;
			pre->next=node;
			L->data++;
			return OK;	
		}
		else{
			pre=cur;
			cur=cur->next;
		}
	}
	printf("not the node value equ %d\n",value);
	free(node);
	return ERROR;
}

//在值为value的结点之后插入
Status InsertValAfter(struct Node* L,int value,int data)
{
	struct Node* p=L->next;
	struct Node* node=(struct Node*)malloc(sizeof(struct Node));
	node->next=NULL;
	node->data=data;
	while(p!=NULL)
	{
		if(p->data==value){
			node->next=p->next;
			p->next=node;
			L->data++;
			return OK;
		}
		else{
			p=p->next;
		}
	}
	printf("can not find the node value equal %d\n",value);
	free(node);
	return ERROR;	
}

链表的遍历

//通过循环打印链表
Status PrintList(struct Node* L)
{
	struct Node* node=L->next;
	//链表为空不进入循环
	if(node==NULL){
		printf("list is empty\n");
		return ERROR;
	}
	printf("node number is %d  ",L->data);
	while(node){
		printf("%d->",node->data);
		node=node->next;
	}
	printf("NULL\n");
	return OK;
}
//递归打印链表
Status RecurPrint(struct Node* node)
{
	if(node==NULL){
		printf("NULL\n");
		return OK;
	}
	printf("%d->",node->data);
	RecurPrint(node->next);
	return OK;
}
//递归打印翻转链表
Status RecurReversePrint(struct Node* node)
{
	if(node==NULL){
		return OK;
	}
	RecurReversePrint(node->next);
	printf("%d->",node->data);
	return OK;
}

清空链表

Status FreeList(struct Node* L)
{
	struct Node* cur=L->next;
	while(cur!=NULL){
		struct Node* temp=cur;
		cur=cur->next;
		free(temp);
	}
	L->next=NULL;
	return OK;
}

单向循环链表

链表结构

typedef struct Node
{
	int data;
	struct Node* next;
}Node;

初始化

struct Node* InitList()
{
	struct Node* L=(struct Node*)malloc(sizeof(struct Node));
	L->next=L;
	L->data=0;
	return L;
}

头插法和尾插法

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++;
}

删除操作

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;
}

遍历链表

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");
}

插入数据

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;
}

双向链表

链表结构

typedef struct Node{
	struct Node* pre;
	int data;
	struct Node* next;
}Node;

链表初始化

struct Node* InitList()
{
	struct Node* L=(struct Node*)malloc(sizeof(struct Node));
	L->pre=NULL;
	L->next=NULL;
	L->data=0;
	return L;
}

头插法和尾插法

void HeadInsert(struct Node*L,int data)
{
	struct Node* node=(struct Node*)malloc(sizeof(struct Node));
	node->data=data;
	if(L->next==NULL){
		node->pre=L;
		node->next=L->next;
		L->next=node;
	}
	else{
		node->next=L->next;
		node->pre=L;
		L->next->pre=node;
		L->next=node;
	}	
	L->data++;
}
void TailInsert(struct Node* L,int data)
{
	struct Node* node=L->next; 
	struct Node* new_node=(struct Node*)malloc(sizeof(struct Node));
	new_node->data=data;
	new_node->next=NULL;
	while(node->next){
		node=node->next;
	}
	node->next=new_node;
	new_node->pre=node;
	L->data++;
}

遍历链表

void PrintList(struct Node* L)
{
	struct Node* node=L->next;
	printf("L<=>");
	while(node){
		printf("%d<=>",node->data);
		node=node->next;
	}
	printf("NULL\n");
}
void ReversePrintList(struct Node* L)
{
	struct Node* node=L->next;
	while(node->next){
		node=node->next;
	}
	while(node!=L){
		printf("%d->",node->data);
		node=node->pre;
	}
	printf("L\n");
}

删除

int Delete(struct Node* L,int data)
{
	struct Node* node=L->next;
	while(node){
		if(node->data==data){
			(node->next)->pre=node->pre;
			(node->pre)->next=node->next;
			free(node);
			L->data--;
			return 1;
		}
		node=node->next;
	}
	return 0;
}

linux内核链表

链表

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

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

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

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

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

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

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

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

链表头

静态创建链表头

struct Node Head{
    .data=data;
    .list=List_Head_Init(Head.list),
}

动态创建链表头

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

添加节点

在某一位置插入

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

在尾部插入

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

删除节点

list_del(struct list_head *entry)

具体实现

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);
}

是否为空

list_empty(struct list_head *head);

遍历链表

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

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

遍历实体

可以这样遍历

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

进行封装

/*
 *	pos:list_entry的返回值
 *  head:头节点/遍历的起始位置
 *  member:list_head的名字
 */

list_for_each_entry(pos,head,member)

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

反向遍历链表

list_for_each_reverse(pos,head,member)

线程安全的链表