# 链表的实现

``````typedef int LTDataType;//类型重命名
typedef struct ListNode
{
LTDataType _data;//数据
struct ListNode* _next;//指向下一个节点的指针
struct ListNode* _prev;//指向前一个节点的指针
}ListNode;
``````

## 新节点的创建

``````ListNode* BuyListNode(LTDataType x)
{
{
perror("malloc fail");
exit(-1);
}
}
``````

## 链表初始化

``````ListNode* InitListNode()
{
}
``````

## 尾插与尾删

``````void ListPushBack(ListNode* pHead, LTDataType x)
{
tail->_next = newnode;//尾节点连接新节点
newnode->_prev = tail;//新节点的prev与尾节点连接
}
``````

``````void ListPopBack(ListNode* pHead)
{
//找尾
//记录尾部前一个节点
ListNode* tailprev = tail->_prev;
//释放尾部
free(tail);
}
``````

``````//链表初始化+尾插尾删
void ListNodeTest1()
{
//初始化
//尾插
//尾删
}
``````

## 头插与头删

``````//头插
{
//找到头节点
//连接
newnode->_next = first;
first->_prev = newnode;
}
``````

``````void ListPopFront(ListNode* pHead)
{
//找到头节点以及头节点后面的节点
ListNode* second = first->_next;
//进行连接
free(first);//释放
}
``````

``````void ListNodeTest2()
{
//初始化
//头插
//头删
}
``````

## 查找数据

``````ListNode* ListFind(ListNode* pHead, LTDataType x)
{
//遍历
{
if (cur->_data == x)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
``````

## 在任意位置的插入与删除

pos位置插入

``````// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
//pos前面的节点
ListNode* posprev = pos->_prev;
//新节点
//连接即可
posprev->_next = newnode;
newnode->_prev = posprev;
newnode->_next = pos;
pos->_prev = newnode;
}
``````

pos位置删除

``````void ListErase(ListNode* pos)
{
assert(pos);
pos->_prev->_next = pos->_next;
pos->_next->_prev = pos->_prev;
free(pos);
}
``````

## 链表的销毁

``````void ListDestory(ListNode* pHead)
{
{
//找到cur后面的节点
ListNode* curnext = cur->_next;
free(cur);//释放
cur = curnext;
}
}

``````

``````//双向链表查找、任意位置插入、删除
ListNodeTest3()
{
//查找
//pos->_data = 50;
//ListPrint(phead);// 5 4 3 50 1
// 双向链表在pos的前面进行插入
ListInsert(pos, 0);
ListPrint(phead);// 5 4 3 0 2 1

//删除pos位置
ListErase(pos);
ListPrint(phead);// 5 4 3 0 1
//链表销毁