双向链表的C语言实现与基本操作（一）

淡淡的烟草味﹌ 2022-06-17 05:41 189阅读 0赞

**本文的主要目录：**

一、双向链表的基本概念

二、双向链表的简单实现

**一、双向链表的基本概念**

双向链表和上一节博客中的单向链表相比，只是在结点元素中多了一个指向前一个结点元素的指针。为什么需要双向链表，因为在实际的工程项目当中，有时候为了提高单向链表访问结点元素的效率，需要在链表结点元素中增加一个指向前驱的指针，提高对链表元素结点的访问速度。

一个基本的双向链表结点的C语言表示如下：

/* 双向链表结点元素 */
    struct dList{
        struct dList *next;
        struct dList *prev;
    };

**二、双向链表的基本实现**

在上一节单向链表实现的基础上来实现这个双向链表。

1、表示链表的结构体定义如下：

/* 定义一个表示链表的结构体指针 */
    struct list {
    	int id;			/* 标识这个元素方便查找 */
    	char data[20];		/* 链表中包含的元素 */
    	struct list *next;	/* 指向下一个结点的指针 */
    	struct list *prev;	/* 指向前一个结点的指针 */
    };

2、因为是双向链表所以定义了两个全局链表结点，一个用来指向链表头部，一个用来指向链表尾部

/* 定义一个链表头部 */
    static struct list *list_head = NULL;
    /* 定义一个链表尾部 */
    static struct list *list_tail = NULL;

3、头结点容易找到，但尾结点相对难一点，所以实现了一个找到尾结点元素的方法，并把尾结点的指针赋值给前面定义的全局尾部结点指针list\_tail。

/**	通过链表的头部找到链表的尾部
      *		head	:	链表的头部的地址
      *		返回值	:	返回链表尾部的地址
      */
    static struct list *find_list_tail(struct list **head)
    {
    	struct list *temp = *head;
    	struct list *p = NULL;
    
    	/* 判断链表是否为空 */
    	if(NULL == temp)		/* 为空 */
    	{
    		return NULL;
    	}
    	else					/* 不为空 */
    	{
    		while(temp)
    		{
    			p = temp;
    			temp = temp->next;
    			if(NULL == temp) return p;
    		}
    	}
    
    	return NULL;
    }

这个函数的思路是通过头结点找到尾结点，首先判断链表是否为空，不为空时对链表进行遍历，返回下一个结点为空的上一个结点，该结点即使结点的尾部。（注意：在使用这个函数获得尾结点指针时，必须在每次插入结点元素后重新获得，因为链表尾部结点是会随着结点的插入而发生变化）

4、仿照上一节单向链表遍历元素的方法，现在实现从尾部开始遍历结点元素的方法，把结点元素的内容倒序打印出来，原理和之前函数的实现类似。

/** 遍历一个链表，打印链表中每个元素所包含的数据
      * tail : 表示要遍历的链表的尾部的指针
      */
    static void list_print_tail(struct list **tail)
    {	
    	struct list *temp;
    
    	temp = *tail;
    
    	printf("list information form tail:\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		temp = temp->prev;
    	}
    }

5、在main函数中实现如下功能：动态分配是个元素并把元素加入到链表当中，先从链表头部打印结点元素数据，再从尾部打印结点元素数据。

/* 主函数，程序的入口 */
    int main(int argc, char *argv[])
    {
    	int i = 0;
    	struct list *lists = NULL;
    
    	/* 分配10个元素 */
    	lists = malloc(sizeof(struct list) * 10);
    	if(NULL == lists)
    	{
    		printf("malloc error!\n");
    		return -1;
    	}
    
    	/* 将分配的10个元素依次填充数据并加入到链表当中 */
    	for(i = 0; i < 10; i++)
    	{
    		lists[i].id = list_id++;
    		sprintf(lists[i].data, "TECH-PRO - %d", i);
    
    		list_add(&list_head, &lists[i]);
    	}
    
    	/* 从头部遍历链表，把链表中每个元素的信息都打印出来 */
    	list_print_head(&list_head);
    
    	/* 找到链表尾部 */
    	list_tail = find_list_tail(&list_head);
    
    	/* 从尾部遍历链表，把链表中每个元素的信息都打印出来 */
    	list_print_tail(&list_tail);
    
    	return 0;
    }

编译运行结果如下所示：  
![Center][]  
  
对于双向链表的基本操作（插入元素，删除元素，修改元素，查看元素）放在下一篇博客中来讲。

**附录：本篇文章实现的完整的双向链表的基本实现的代码如下所示：**

/* 包含的头文件 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    
    /* 定义一个表示链表的结构体指针 */
    struct list {
    	int id;			/* 标识这个元素方便查找 */
    	char data[20];		/* 链表中包含的元素 */
    	struct list *next;	/* 指向下一个结点的指针 */
    	struct list *prev;	/* 指向前一个结点的指针 */
    };
    
    /* 定义一个链表头部 */
    static struct list *list_head = NULL;
    
    /* 定义一个链表尾部 */
    static struct list *list_tail = NULL;
    
    /* 为了保证每一个链表元素的id不同，特意把id定义成一个全局静态变量 */
    static int list_id = 0;
    
    /**	将指定元素插入到聊表尾部
      * 	head	: 表示要插入元素的链表的头部的地址
      *	list    : 表示要插入到链表中的元素
      */
    static void list_add(struct list **head, struct list *list)
    {
    	struct list *temp;
    
    	/* 判断链表是否为空 */
    	if(NULL == *head)
    	{
    		/* 为空 */
    		*head = list;
    		(*head)->next = NULL;
    		(*head)->prev = NULL;
    	}
    	else
    	{
    		/* 不为空 */
    		temp = *head;
    		while(temp)
    		{
    			/* 将新结点插入到链表尾部 */
    			if(NULL == temp->next)
    			{
    				temp->next = list;
    				list->next = NULL;
    				list->prev = temp;
    				return;
    			}
    			temp = temp->next;
    		}
    	}
    }
    
    /**	通过链表的头部找到链表的尾部
      *		head	:	链表的头部的地址
      *		返回值	:	返回链表尾部的地址
      */
    static struct list *find_list_tail(struct list **head)
    {
    	struct list *temp = *head;
    	struct list *p = NULL;
    
    	/* 判断链表是否为空 */
    	if(NULL == temp)		/* 为空 */
    	{
    		return NULL;
    	}
    	else					/* 不为空 */
    	{
    		while(temp)
    		{
    			p = temp;
    			temp = temp->next;
    			if(NULL == temp) return p;
    		}
    	}
    
    	return NULL;
    }
    
    /** 遍历一个链表，打印链表中每个元素所包含的数据
      * head : 表示要遍历的链表的头部的指针
      */
    static void list_print_head(struct list **head)
    {	
    	struct list *temp;
    
    	temp = *head;
    
    	printf("list information form head:\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		temp = temp->next;
    	}
    }
    
    /** 遍历一个链表，打印链表中每个元素所包含的数据
      * tail : 表示要遍历的链表的尾部的指针
      */
    static void list_print_tail(struct list **tail)
    {	
    	struct list *temp;
    
    	temp = *tail;
    
    	printf("list information form tail:\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		temp = temp->prev;
    	}
    }
    
    
    /* 主函数，程序的入口 */
    int main(int argc, char *argv[])
    {
    	int i = 0;
    	struct list *lists = NULL;
    
    	/* 分配10个元素 */
    	lists = malloc(sizeof(struct list) * 10);
    	if(NULL == lists)
    	{
    		printf("malloc error!\n");
    		return -1;
    	}
    
    	/* 将分配的10个元素依次填充数据并加入到链表当中 */
    	for(i = 0; i < 10; i++)
    	{
    		lists[i].id = list_id++;
    		sprintf(lists[i].data, "TECH-PRO - %d", i);
    
    		list_add(&list_head, &lists[i]);
    	}
    
    	/* 从头部遍历链表，把链表中每个元素的信息都打印出来 */
    	list_print_head(&list_head);
    
    	/* 找到链表尾部 */
    	list_tail = find_list_tail(&list_head);
    
    	/* 从尾部遍历链表，把链表中每个元素的信息都打印出来 */
    	list_print_tail(&list_tail);
    
    	return 0;
    }

[Center]: /images/20220617/4968081ff3c0409c853d7c12fcc7d529.png