数据结构——双向链表

双向链表实质上是在单向链表的基础上加上了一个指针指向后面地址

单向链表请参考http://t.csdn.cn/3Gxk9

物理结构
首先我们看一下两种链表的物理结构
在这里插入图片描述
我们可以看到：双向在单向基础上加入了一个指向上一个地址的指针，如此操作我们便可以向数组一样操作了，而且尾插也更加方便，复杂度从原来的O(n)变为O(1)，并且查找也可以运用二分查找。

一些基础操作

头插

在这里插入图片描述

头删

在这里插入图片描述

尾插

在这里插入图片描述

尾删

在这里插入图片描述

接下来我们来进行代码实现

头文件以及要实现的函数声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int LTDataType;
typedef struct Slist
{
	LTDataType val;
	struct Slist* next;
	struct Slist* random;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 扩容
ListNode* my_malloc(LTDataType x);

函数实现

#include "dslist.h"

ListNode* my_malloc(LTDataType x)//由于后续要频繁使用到扩容，所以我们直接创一个扩容函数
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->val = x;
	newnode->random = NULL;
	newnode->next = NULL;
	return newnode;
}

ListNode* ListCreate()  //创建一个双向链表
{
	ListNode* head = (ListNode * )malloc(sizeof(ListNode));
	head->val = -1;    
	head->next= NULL;
	head->random = NULL;
	return head;
}

void ListDestory(ListNode* pHead)  //销毁这个双线链表
{
	while (pHead)//将每个节点都free掉
	{
		ListNode* mid = pHead;
		pHead = pHead->next;
		mid->next = NULL;
		free(mid);
	}
}

void ListPrint(ListNode* pHead)   //打印双向链表
{
	ListNode* mid = pHead;
	while (mid)  //循环一个一个打印
	{
		printf("%d->", mid->val);
		mid = mid->next;
	}
	printf("NULL");
}

void ListPushBack(ListNode* pHead, LTDataType x)    //尾插
{
	ListNode* newnode = my_malloc(x);
	if (pHead->next == NULL)       //判断链表是否为空，如果为空则只需要插入一个。
	{
		newnode->random = pHead;    //由于循环链表，需要将头节点的random指向插入元素  
		newnode->next = NULL;
		pHead->next = newnode;
		pHead->random = newnode;
	}
	else             //如果不为空则正常尾插
	{
		ListNode* mid = pHead->random;    //由于双向  头节点的random指针直接指向尾部，所以不需要循环找尾
		mid->next = newnode;
		newnode->random = mid;
		pHead->random = newnode;
	}
}

void ListPopBack(ListNode* pHead)   //尾删
{
	if (pHead->next == NULL)   //判断是否为空
	{
		return;
	}
	else
	{
		ListNode* mid = pHead->random;   //正常尾删
		pHead->random = mid->random;
		mid->random->next = NULL;
		free(mid);
	}
}

void ListPushFront(ListNode* pHead, LTDataType x)    //头插
{
	if (pHead->next == NULL) //如果为空  则相当于尾插  调用尾插函数即可
	{
		ListPushBack(pHead, x);
	}
	else    //不为空正常头插
	{
		ListNode* nownode = my_malloc(x);   
		nownode->next = pHead->next;     //将nownode  的next指向  phead的next
		nownode->random = pHead;     //nownode的random指向  phead
		pHead->next = nownode;          //phead的next指向nownode
		nownode->next->random = nownode;
	}
}

void ListPopFront(ListNode* pHead)    //头删
{
	if (pHead->next == NULL)
	{
		return;
	}
	else
	{
		if (pHead->next == pHead->random)
		{
			ListPopBack(pHead);
		}
		else
		{
			ListNode* mid = pHead->next;
			pHead->next = mid->next;
			mid->next->random = pHead;
			free(mid);
		}

	}
}

ListNode* ListFind(ListNode* pHead, LTDataType x)   //寻找元素
{
	ListNode* left = pHead->next;
	ListNode* right = pHead->random;
	while (left && right)    //二分查找
	{
		if (left->val == x)
		{
			return left;
		}
		if (right->val == x)
		{
			return right;
		}
		left = left->next;
		right = right->random;
	}
	return NULL;
}

void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* newnode = my_malloc(x);
	ListNode* mid = pos->random;
	mid->next = newnode;
	pos->random = newnode;
	newnode->next = pos;
}

void ListErase(ListNode* pos)
{
	ListNode* next = pos->next;
	ListNode* last = pos->random;
	next->random = last;
	last->next = next;
	free(pos);
}