双向循环链表

1. 基本概念

双向链表是在单向链表的每个结点中，再设置一个指向其前驱结点的指针域。

由于这是一个双向链表，所以对于链表中的某一个结点 p ，它后继的前驱以及前驱的后继都是它自己。

p->next->prev = p = p->prev->next;

2. 双向循环链表

• 双向循环链表的带头结点空链表为

• 非空的双向循环链表

3. 双向链表结点的创建

typedef int DataType;

//双向循环链表结点结构体声明
typedef struct Node
{
	DataType data; 		//数据域
	struct Node *prev;	//前驱指针域
	struct Node *next;	//后继指针域
}double_link_list;

4. 初始化

//初始化一条链表
double_link_list *list_init(void)
{
	double_link_list *head = malloc(sizeof(double_link_list));
	if(head != NULL)
	{
		//自循环：自己指向自己
		head->next = head;
		head->prev = head;
		
		// 返回头结点地址
		return head;
	}
	return NULL;
}

5. 结点的创建

//创建一个新结点
double_link_list *create_node(datatype data)
{
	linknode *new = malloc(sizeof(double_link_list));
	if(new != NULL)
	{
		//自循环：自己指向自己
		new->data = data;	//把数据保存到结点数据域
		new->next = new;
		new->prev = new;
		
		// 返回头结点地址
		return new;
	}
	return NULL;
}

6. 插入结点

• 在两个结点之间插入结点：

//新节点插入到任意两个相邻结点之间
// new：新结点
// prev：插入位置的前一个结点
// next：插入位置的后一个结点
void add_node(double_link_list *new, double_link_list *prev, double_link_list *next)
{
	// printf("%s\n", __FUNCTION__);
	prev->next = new;
	new->prev = prev;
	new->next = next;
	next->prev = new;
}

• 头插法和尾插法

//头插
// 在头结点后面添加一个结点
void inster_head(double_link_list *head, double_link_list *new)
{
	//把新节点指向要插入位置的头结点和头结点的下一个
	new->prev = head;
	new->next = head->next;
	
	// 把插入位置的后一个结点的prev从指向头改成指向new
	head->next->prev = new;
	
	// 把头的next指向新的节点new
	head->next = new;
}
//尾插
// 在链表的尾巴之后添加一个结点， 实际上就是头的前面
void inster_tail(double_link_list *head, double_link_list *new)
{
	//把新节点指向要插入位置的前一个结点和头结点
	new->next = head;
	new->prev = head->prev;
	
	//把插入位置的前一个结点的next从指向head改成指向new
	head->prev->next = new;
	
	//把头结点的prev从原来的值改为指向new
	head->prev = new;
}

// 尾插
void inster_tail(double_link_list *head, double_link_list *new)
{
	add_node(new, head->prev, head);
}

// 头插
void inster_head(double_link_list *head, double_link_list *new)
{
	add_node(new, head, head->next);
}

6. 遍历链表

// 向后遍历
void display_next_list(double_link_list *head)
{
	display_prev_list *tmp = head;
	for(; tmp->next != head; tmp = tmp->next)
	{
		printf("%d->", tmp->next->data);
	}
	printf("\n");
}

// 向前遍历
void display_prev_list(double_link_list *head)
{
	display_prev_list *tmp = head;
	for(; tmp->prev != head; tmp = tmp->prev)
	{
		printf("%d->", tmp->prev->data);
	}
	printf("\n");
}

7. 查找结点

// 查找某个结点
// 在哪条链表中查找
// 查找什么数据？
double_link_list *find_node(double_link_list *head, datatype data)
{
	linknode *tmp = head;
	for(; tmp->next != head; tmp = tmp->next)
	{
		if(tmp->next->data == data)
			return tmp->next;
	}
	return NULL;	//没找到
}

8. 删除结点

//从链表中删除一个结点
//把链表中的一个结点脱离出来，并未释放
double_link_list *remove_node(double_link_list *head, datatype data)
{
	//查找要删除的结点，找到返回结点
	double_link_list *f_node = NULL;
	if( ( f_node = find_node(head, data) ) == NULL)
		return NULL;
	
	//把结点的前一个结点的next指向被删除节点的后一个结点
	f_node->prev->next = f_node->next;
	
	//把节点的后一个结点的prev指向被删除节点的前一个结点
	f_node->next->prev = f_node->prev;
	
	//返回删除的结点
	return f_node;
}

9. 销毁结点

// 直接删除结点（会释放结点空间）
bool destory_node(double_link_list *head, datatype data)
{
	double_link_list *d_node = NULL;
	if( (d_node = remove_node(head, data)) == NULL )
		return false;	//没有这个节点
	
	//把这个结点的前后指针，都指向空，并且释放空间
	d_node->prev = NULL;
	d_node->next = NULL;
	free(d_node);
	
	return true;
}

10. 更新结点

//更新结点
// 更新是哪一条链表
// 更新的是哪一个数据
// 更新的新数据是什么
bool updata_node(double_link_list *head, datatype old_data, datatype new_data)
{
	double_link_list *f_node = NULL;
	if( ( f_node = find_node(head, old_data) ) == NULL)
		return false;
	
	f_node->data = new_data;
	return true;
}

11. 移动结点

//移动一个结点
//移动哪一条链表的结点
//移动的是哪一个数据的结点
//要移到那个数据之后
bool move_node(double_link_list *head, datatype src_data, datatype dest_data)
{
	double_link_list *src_node = NULL;
	double_link_list *dest_node	= NULL;

	//找到要移动到哪里
	if( ( dest_node = find_node(head, dest_data) ) == NULL)
		return false;
	
	//找到要移动数据结点
	if( ( src_node = find_node(head, src_data) ) == NULL)
		return false;
	
	//把节点的前一个节点的next指向被删除节点的后一个结点
	src_node->prev->next = src_node->next;
	
	//把节点的后一个节点的prev指向被删除节点的前一个结点
	src_node->next->prev = src_node->prev;
	
	//把这个src_node添加到dest_node之后
	inster_head(dest_node, src_node);
	return true;
}

12. main函数调用

int main(int argc, char *argv[])
{
	//1. 创建一条链表
	linknode *head = list_init();
	if(head == NULL){
		printf("链表初始化失败\n");
		exit(0);
	}
	
	// 2. 初始化一些自然数
	int i, n;
	
	printf("请输入需要多少个自然数\n");
	scanf("%d", &n);
	
	for(i=1; i<=n; i++)
	{
		// 2.1 创建新结点
		linknode *new = create_node(i);
		if(new == NULL) {
			printf("%d创建失败\n", i);
			continue;	//跳到条件判断，继续下一次循环
		}

		// 2.2 插入新结点
		// inster_tail(head, new);
		inster_head(head, new);
	}
	
	//3. 向后遍历链表
	display_next_list(head);
	
	//4. 查找4这个数据结点
	linknode *f_node = find_node(head, 4);
	if(f_node == NULL) {
		printf("链表中没有数据4的这个节点\n");
	}
	else
		printf("找到这个%d在链表中的节点地址:%p\n", f_node->data, f_node);
	
	// 5. 删除链表中的某个节点
	if( !destory_node(head, 4) )
		printf("删除失败");
	else{
		printf("删除成功\n");
		display_next_list(head);
	}
	
	// 6. 移动结点
	move_node(head, 10, 2);
	display_next_list(head);
	
	// 7. 更新结点
	updata_node(head, 6, 66);
	display_next_list(head);
  
	return 0;
}