1.链表的分类

链表的种类非常多组合起来就有 2 × 2 = 8种

center;">c="https://img-blog.csdnimg.cn/direct/746b41c0534346fd96e2e4f6a7aea739.png" />

 链表说明：

center;">c="https://img-blog.csdnimg.cn/direct/3fb22fc52a75472e9aa425771ddbf0c7.png" />

2.双向链表的实现

List.h

<code>#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode {LTDataType Data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化链表
LTNode* LTInit();//打印链表
void LTPrintf(LTNode* phead);//申请节点
LTNode* LTBuyNode(LTDataType x);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPophBack(LTNode* phead, LTDataType x);//头删
void LTPopFront(LTNode* phead, LTDataType x);//用数据找到该节点
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的数据
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode* phead);code>

List .c

<code>#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"//初始化链表
LTNode* LTInit() {LTNode* sbw = LTBuyNode(-1);return sbw;
}//打印链表
void LTPrintf(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->Data);pcur = pcur->next;}printf("\n");
}//申请节点
LTNode* LTBuyNode(LTDataType x) {LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(1);}node->next = node->prev = node;node->Data = x;return node;
}//尾插
//不改变头节点(哨兵卫)࿰c;所以传一级指针,但是可以通过这个指针去改变这个地址下元素的值
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;  //新尾节点prev指向原尾节点newnode->next = phead;        //新尾节点next指向哨兵卫phead->prev->next = newnode;//原尾节点next指向新尾节点phead->prev = newnode;      //哨兵卫prev指向新尾节点
}//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;newnode->next = newnode;
}//尾删
void LTPophBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* del = phead->prev ;//原尾节点,相对新尾节点的下一个节点del->prev->next = phead;//新尾节点（原尾节点的上一个节点）的next指向哨兵卫phead->prev = del->prev;//哨兵卫的prev指向新尾节点free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* del = phead->next;//相对哨兵卫的下一个节点del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//用节点的Date数据࿰c;找到该节点
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* Find = phead->next;while (Find != phead){if (Find->Data == x){return Find;}Find = Find->next;}//没找到return NULL;
}//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;//一般来说都是先改后面的节点࿰c;避免数据的丢失pos->next->prev = newnode;pos->next = newnode;
}//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->next->prev = pos->prev;//处理pos下一个节点的prev指向pos->prev->next = pos->next;//处理pos上一个节点的next指向free(pos);pos = NULL;
}//销毁链表
void LTDestroy(LTNode* phead) {LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(pcur);pcur = NULL;}code>

3.顺序表和双向链表的优缺点分析