目录

一，链表与单链表的比较

二，创建链表节点

三，接口实现

1，基本接口

2，处理数据接口

 3，处理数据接口的复用

写在最后的话

注意这里的链表指的是

带哨兵位的，双向的，循环的链表

一，链表与单链表的比较

链表与单链表都是通过一个个的节点链接形成，两者的不同在于：

1，节点的结构，单链表节点除数据外，还存储下一个节点的地址；链表的节点则在此基础之上，额外存储上一个节点的地址。这样做的目的是为了方便寻找某一节点的前后节点

2，哨兵位的有无，哨兵位是不存储有效数据的节点，它的存在是为了更加方便地实现某些接口，比如：单链表在实现PushBack（尾插）时，需要判断当前链表是否为空，如果为空是则让指针指向新节点；不为空则找尾后链接。哨兵位的存在则省去此种判断，直接使新节点连接在尾节点之后即可。

 3，是否循环（节点的结构决定了两者的不同），单链表只有一个方向，从头指向尾，而链表则是两个方向，即从头指向尾和从尾指向头（循环）

二，创建链表节点

typedef int LTDataType;typedef struct LTNode
{struct LTNode* prev;struct LTNode* next;LTDataType data;
}LTNode;

同单链表一样，通过struct创建结构体，其成员val用于存储数据；next用于存储下一个结点的地址，即指向下一个节点；prev用于存储上一个结点的地址，即指向上一个节点。

注意这里我们通过typedef将int重命名为SLDataType，这样当我们在顺序表中存放int之外类型的数据时，我们只需将int修改即可，例如float

三，接口实现

1，基本接口

LTNode* ListCreate(void)

：链表的创建，当调用该函数时，创建哨兵位，并返回哨兵位。（哨兵位prev，next均指向自身）

void ListDestory(LTNode* phead)
void ListPrint(LTNode* phead)
LTNode* ListFind(LTNode* phead, LTDataType x)

：遍历链表，free()动态开辟的节点即为销毁链表；打印每个数据即为打印链表；判断某个数据在链表的位置即为Find。

注意：链表没有NULL，所以在遍历时应当从哨兵位的下一个节点开始，到哨兵位结束。

LTNode* ListCreate(void)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->prev = newnode;newnode->next = newnode;return newnode;
}void ListDestory(LTNode* phead)
{assert(phead != NULL);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}void ListPrint(LTNode* phead)
{assert(phead != NULL);printf("<=>head");LTNode* cur = phead->next;while (cur != phead){printf("<=>%d", cur->data);cur = cur->next;}printf("\n");
}LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead != NULL);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}

2，处理数据接口

void ListInsert(LTNode* pos, LTDataType x)

：在pos节点之前插入新节点，首先创捷新节点储存数据，然后找到pos节点上一个节点prev，改变三者之间的关系

LTNode* BuyNewNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}void ListInsert(LTNode* pos, LTDataType x)
{assert(pos != NULL);LTNode* newnode = BuyNewNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

void ListErase(LTNode* pos)

：找到pos节点并释放，改变pos上一个节点prev，下一个节点next以及pos三者之间的关系即可

void ListErase(LTNode* pos)
{assert(pos != NULL);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);
}

 3，处理数据接口的复用

void ListPushBack(LTNode* phead, LTDataType x)，尾插，即在哨兵位之前插入

void ListPushBack(LTNode* phead, LTDataType x)
{ListInsert(phead, x);
}

void ListPushFront(LTNode* phead, LTDataType x)，前插，即在哨兵位下一个节点之前插入

void ListPushFront(LTNode* phead, LTDataType x)
{ListInsert(phead->next, x);
}

void ListPopBack(LTNode* phead)，尾删，即删除哨兵位上一个节点

void ListPopBack(LTNode* phead)
{assert(phead->prev != phead);ListErase(phead->prev);
}

void ListPopFront(LTNode* phead)，前删，即删除哨兵位下一个节点

void ListPopFront(LTNode* phead)
{assert(phead->next != phead);ListErase(phead->next);
}

写在最后的话

数据结构的实现不是单一的或者统一的，思想是关键，代码实现的细节的差异因人而异，使用数据结构应当对代码进行了解，不是想怎么用就怎么用的