# 【数据结构与算法】双向链表

1. 单向、双向
2. 带头单链表、不带头链表
3. 循环、非循环

1. 无头单向非循环链表

2. 带头双向循环链表

### 创建结构体

##### 创建结构体代码
``````typedef int LTDataType;

typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}ListNode;
``````

### 链表初始化

##### 初始化函数代码(方法一)
``````//初始化链表
{

}
``````

``````ListNode* phead = ListInit();
``````
##### 初始化函数代码(方法二)
``````//初始化链表
ListNode* ListInit()
{

}
``````

### 清理数据结点

1. 指针cur指向当前要清理的结点，next用于保存下一个待清理结点的地址

``````phead->next = phead;
``````
##### 清理数据结点代码
``````void ListClear(ListNode* phead)
{

//清理所有数据结点，保留头结点，可以继续使用
{
ListNode* next = cur->next;
free(cur);
cur = next;
}

}
``````

### 销毁链表

##### 销毁链表代码
``````//销毁链表
{

}
``````

### 创建新结点

``````ListNode* BuyListNode(LTDataType x)
{
ListNode*node = (ListNode*)malloc(sizeof(ListNode));
//初始化
node->next = NULL;
node->prev = NULL;
node->data = x;

return node;
}
``````

### 链表的打印

​ 思路：

##### 链表的打印代码
``````assert(phead);

{
print("%d ", cur->data);
cur = cur->next;
}
``````

### 尾插

1. 进行尾插，首先要找到尾结点，由上图可知双链表头结点的prev指针指向的就是尾结点

``````ListNode* tail = phead->prev;
``````
2. 尾结点找到后，我们来插入新的结点，首先我们将新结点和尾结点进行链接，如下图红色箭头

``````tail->next = newnode;
newnode->prev = tail;
``````
3. 头结点与新结点链接

``````newnode->next = phead;
``````
##### 尾插代码
``````//尾插
{

//进行结点的链接
tail->next = newnode;
newnode->prev = tail;

}
``````

### 尾删

1. 确定尾结点

``````ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
``````

2. tailPrev指向的结点与头结点进行链接

``````phead->prev = tailPrev;
``````

3. 删除尾结点

##### 尾删代码
``````
//尾删
{
{
}
else
{
ListNode* tailPrev = tail->prev;

free(tail);

}
}
``````

### 头插

``````phead->next = newnode;
``````
3. 新结点与first链接,头插结束

``````newnode->next = first;
first->prev = newnode;
``````
##### 头插代码
``````//头插
{

newnode->next = first;
first->prev = newnode;
}
``````

### 头删

1. 创建两个指针first和second

``````ListNode* first = phead->next;
ListNode* second = first->next;
``````

``````phead->next = second;
free(first);
``````

##### 头删代码
``````//头删
{

ListNode* second = first->next;

free(first);
}
``````

### 链表的查找

##### 链表的查找代码
``````//查找
{

{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}

return NULL;
}
``````

### 插入（任意结点）

##### 插入（任意结点）代码
``````//插入（任意位置）
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* posPrev = pos->prev;

posPrev->next = newnode;
newnode->prev = posPrev;

newnode->next = pos;
pos->prev = newnode;
}
``````

### 删除（任意结点）

##### 删除（任意结点）代码
``````//删除（任意位置）
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;

free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
``````

#### 双链表完整代码

List.h文件

``````#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int LTDataType;

typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}ListNode;

ListNode* ListInit();

void ListInsert(ListNode* pos, LTDataType x);
void ListErase(ListNode* pos);
``````

List.c文件

``````#include "List.h"

//初始化链表
ListNode* ListInit()
{

}

//创建新结点
{
ListNode*node = (ListNode*)malloc(sizeof(ListNode));
node->next = NULL;
node->prev = NULL;
node->data = x;

return node;
}

//清理数据结点
{

//清理所有数据结点，保留头结点，可以继续使用
{
ListNode* next = cur->next;
free(cur);
cur = next;
}

}

//销毁链表
{

}

//打印
{

{
printf("%d ", cur->data);
cur = cur->next;
}
printf("n");
}

//尾插
{

//进行结点的链接
tail->next = newnode;
newnode->prev = tail;

}

//尾删
{
{
}
else
{
ListNode* tailPrev = tail->prev;

free(tail);

}
}

//头插
{

newnode->next = first;
first->prev = newnode;
}

//头删
{

ListNode* second = first->next;

free(first);
}

//查找
{

{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}

return NULL;
}

//插入（任意位置）
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* posPrev = pos->prev;

posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}

//删除（任意位置）
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;

free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
``````

test.c

``````#include "List.h"

void TestList1()
{

}

void TestList2()
{

ListInsert(pos, 30);

ListErase(pos);

}
void main()
{
//TestList1();
TestList2();
}

``````

THE END