双向链表代码

在介绍双向链表之前，先介绍一下链表的分类：
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或者双向：

带头或者不带头：

循环或者非循环：

看到有这么多的结构，你是不是以为链表链表会很难学呢，其实在实际当中最经常用的还是两种结构：

此行用于过渡

1.无头单向非循环链表：也就是我们做题中常见的单链表：
2.带头双向循环链表：也就是接下来我们要讲到的双链表：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
   构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向
   循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而
   简单了，后面我们代码实现了就知道了。

双向链表的代码实现和增删查改功能：

我们以带头双向循环链表为例来进行实现：
双向链表和单链表结构上的区别就在于双向链表多了一个指向上一个节点的指针。知道这个我们很快就能将双向链表的结构写出来：

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

这里我们用三个文件来分别实现双向链表的声明，定义和测试功能——DSList.h，DSList.c，text.c

DSList.h:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DLTDateType;
typedef struct ListNode
{
	DLTDateType _data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;


//动态开辟一个节点：
ListNode* BuySListNode(DLTDateType x);
//链表的初始化——创建头节点
ListNode* DSLInit();
//尾插：
void DSLPushBack(ListNode* plist, DLTDateType x);
//尾删：
void DSLPopBack(ListNode* plist);
//头插：
void DSLPushFront(ListNode* plist, DLTDateType x);
//头删：
void DSLPopFront(ListNode* plist);
//查找：
ListNode* DSLFind(ListNode* plist, DLTDateType x);
//在任意位置后面插入：
void DSLInsert(ListNode* pos, DLTDateType x);
//在任意位置删除：
void DSLtErase(ListNode* pos);
//打印链表：
void DSLPrint(ListNode* plist);

DSList.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"DSList.h"


//动态开辟一个节点：
ListNode* BuySListNode(DLTDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc error");
	}
	newnode->_data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//链表的初始化——创建头节点
ListNode* DSLInit()
{
	ListNode* head = BuySListNode(-1);
	head->prev = head;
	head->next = head;
	return head;
}

//尾插：
void DSLPushBack(ListNode* plist, DLTDateType x)
{
	//如果没有节点：检查
	assert(plist);
	//找尾
	ListNode* tail = plist->prev;
	ListNode* newnode = BuySListNode(x);
	newnode->next = plist;
	tail->next = newnode;
	newnode->prev = tail;
	plist->prev = newnode;
}

//尾删：
void DSLPopBack(ListNode* plist)
{
	assert(plist);
	//找尾：
	ListNode* tail = plist->prev;
	plist->prev = tail->prev;
	tail->prev->next = plist;
	free(tail);
}

//头插：
void DSLPushFront(ListNode* plist, DLTDateType x)
{
	assert(plist);
	ListNode* newnode = BuySListNode(x);
	newnode->prev = plist;
	newnode->next = plist->next;
	plist->next = newnode;
	newnode->next->prev = newnode;
}

//头删：
void DSLPopFront(ListNode* plist)
{
	assert(plist);
	ListNode* node = plist->next;
	plist->next->next->prev = plist;
	plist->next = plist->next->next;
	free(node);
}

//查找：
ListNode* DSLFind(ListNode* plist, DLTDateType x)
{
	ListNode* find = plist->next;
	while (find != plist)
	{
		if (find->_data == x)
			return find;
		find = find->next;
	}
	return NULL;
}


// 在任意位置后面插入：
void DSLInsert(ListNode * pos, DLTDateType x)
{
	assert(pos);
	ListNode* newnode = BuySListNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next = newnode;
}

//在任意位置删除：
void DSLtErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

//打印链表：
void DSLPrint(ListNode* plist)
{
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d<->", cur->_data);
		cur = cur->next;
	}
	printf("\n");
}

然后这里呢还有个小小的问题，为什么BuySListNode()和DSLInit()有返回值就可以修改实参的地址呢，我们不是说函数调用完就会被销毁，那么在函数里面创建的空间也会被销毁，但为什么还是可以这样写呢。因为我们在函数内部创建的空间是动态开辟的空间，这些空间会在程序运行时一直存在。
text.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"DSList.h"


void DSListText()
{
	//初始化：
	ListNode* phead = NULL;
	phead = DSLInit();
	//测试尾插和尾删：
	DSLPushBack(phead, 1);
	DSLPushBack(phead, 2);
	DSLPushBack(phead, 3);
	DSLPushBack(phead, 4);
	DSLPushBack(phead, 5);
	DSLPrint(phead);
	DSLPopBack(phead);
	DSLPopBack(phead);
	DSLPopBack(phead);
	DSLPrint(phead);
}
void DSListText1()
{
	//初始化：
	ListNode* phead = NULL;
	phead = DSLInit();
	//测试头插和头删：
	 DSLPushFront(phead,1);
	 DSLPushFront(phead, 2);
	 DSLPushFront(phead, 3);
	 DSLPushFront(phead, 4);
	 DSLPushFront(phead, 5);
	 DSLPrint(phead);
	 DSLPopFront(phead);
	 DSLPopFront(phead);
	 DSLPopFront(phead);
	 DSLPrint(phead);
}


void DSListText2()
{
	//初始化：
	ListNode* phead = NULL;
	phead = DSLInit();
	//尾插5个节点：
	DSLPushBack(phead, 1);
	DSLPushBack(phead, 2);
	DSLPushBack(phead, 3);
	DSLPushBack(phead, 4);
	DSLPushBack(phead, 5);
	DSLPrint(phead);
	//测试在任意位置后面插入和在任意位置删除：
	// 插入：
	//找位置：
	ListNode* pos = DSLFind(phead, 1);
	DSLInsert(pos, 10);
	DSLPrint(phead);
	//删除：
	//找位置：
	ListNode* pos1 = DSLFind(phead, 4);
	DSLtErase(pos1);
	DSLPrint(phead);
}

int main()
{
	DSListText();
	printf("\n");
	DSListText1();
	printf("\n");
	DSListText2();
	return 0;
}

以上代码均为自己手搓，如果有错误还请大佬指点改正。

接下来有一道经典题：
1.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。OJ链接
这道题是什么意思呢，就是有一个链表，每个节点包含一个数据和两个指针，一个指针指向下一个节点，另外一个指针指向NULL或者任意节点。要求将这个链表拷贝一份。
解题思路：在每个节点复制然后添加到对应节点的后面，这样每个新节点的random的指向就是原节点random指向的节点的下一个节点。
图解：

因为我们复制的节点在原节点的后面，所以原节点random指针指向的那个节点后面也存在一个该节点的复制节点，所以我们新节点的random指针指向原节点random指针指向的节点的下一个节点。例如：原节点13的random指针指向原节点7，那么我们新节点13的random指针指向原节点13random指针指向的节点的下一个节点。以此内推就可以将链表拷贝一份。
代码

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur=head;
    struct Node*node[1000];
    int count=0;
    while(cur)
    {
        struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        node[count++]=newnode;
        newnode->val=cur->val;
        newnode->next=cur->next;
        cur->next=newnode;
        cur=newnode->next;
    }
    struct Node* cur1=head;
    while(cur1)
    {
        if(cur1->random==NULL)
        cur1->next->random=NULL;
        else
        {
            cur1->next->random=cur1->random->next;
        }
        cur1=cur1->next->next;
    }
    for(int i=0;i<count-1;i++)
    node[i]->next=node[i+1];
    return node[0];
}