一、链表的概念及结构

1.链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2.链表的结构

一般讲的链表包括数据域和指针域：

二、链表的种类

实际中链表的结构非常多样，由以下三组类型自由组合可得8种链表结构：

1.单向、双向：

2.带头、不带头：

3.循环、非循环：

虽然有这么多类型，但我们最长使用的就是以下两种：

在此我们只实现这两种链表

三、单链表的实现

1.自定义链表结点struct SListNode

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;

2.链表打印数据SListPrint

//打印
void SListPrint(SListNode* plist)
{if (plist == NULL)return;while (plist){printf("%d->", plist->data);plist = plist->next;}
}

3.链表创建结点BuyListNode

//创建节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* new_node = (SListNode*)malloc(sizeof(SListNode));if (new_node == NULL){perror("malloc fail");return NULL;}new_node->data = x;new_node->next = NULL;return new_node;
}

4.链表尾部插入数据SListPushBack

//尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{//无节点if (*pplist == NULL){(*pplist) = BuySListNode(x);}//有节点SListNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = BuySListNode(x);
}

5.链表头部插入数据SListPushFront

//头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* new_node = BuySListNode(x);new_node->next = *pplist;*pplist = new_node;
}

6.链表尾部删除数据SListPopBack

//尾删
void SListPopBack(SListNode** pplist)
{//空链表if ((*pplist) == NULL)return;//一个节点if ((*pplist)->next == NULL){SListNode* tmp = *pplist;free(tmp);tmp = NULL;}//多个节点else{SListNode* cur = *pplist;SListNode* next = cur->next;//找尾while (cur->next->next){cur = next;next = next->next;}free(next);cur->next = NULL;}}

7.链表头部删除数据SListPopFront

//头删
void SLPopFront(SListNode** pplist)
{//没有节点if ((*pplist) == NULL)return;//一个节点//多个节点SListNode* tmp = *pplist;*pplist = (*pplist)->next;free(tmp);tmp = NULL;
}

8.链表查找数据

//查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

9.链表在pos位置之后插入数据

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{SListNode* newnode = BuySListNode(x);//在非尾节点插入if (pos->next != NULL){newnode->next = pos->next;pos->next = newnode;}else{SListPushBack(&pos, x);}
}

10.删除pos位置之后的值

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{if (pos->next == NULL){printf("erroe");return;}SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

11.销毁链表

//销毁链表
void SLTDestroy(SListNode** pphead)
{if (*pphead == NULL)return;SListNode* next = (*(pphead))->next;while (*pphead){//销毁SListNode* del = *pphead;free(del);del = NULL;//迭代*pphead = next;if(next)next = next->next;}
}

四.带头双向循环链表的实现

1.自定义链表结点 ListNode

typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;

2.创建新节点

//创建新节点
ListNode* BuyLTNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->_data = x;newnode->_next = NULL;newnode->_prev = NULL;return newnode;
}

3.创建一个新链表，返回头结点

// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* Phead = BuyLTNode(-1);Phead->_next = Phead;Phead->_prev = Phead;return Phead;
}

4.打印链表

//打印链表
void ListPrint(ListNode* pHead)
{if (pHead == NULL)return;ListNode* cur = pHead->_next;printf("pHead <=> ");while (cur!=pHead){printf("%d <=> ", cur->_data);cur = cur->_next;}
}

5.在pos之前插入值为x节点

//在pos前插入
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* pre = pos->_prev;ListNode* newnode = BuyLTNode(x);newnode->_next = pos;pos->_prev = newnode;pre->_next = newnode;newnode->_prev = pre;
}

6.尾插

//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListInsert(pHead,  x);
}

7.头插

//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListInsert(pHead->_next, x);
}

8.删除pos位置节点

//删除pos位置的节点
void ListErase(ListNode* pos)
{ListNode* pre = pos->_prev;ListNode* next = pos->_next;free(pos);pos = NULL;pre->_next = next;next->_prev = pre;
}

9.双向链表头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{ListErase(pHead->_next);
}

10.双向链表尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{ListErase(pHead->_prev);
}

11.查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_data == x)return cur;cur = cur->_next;}return NULL;
}

12.销毁链表

//销毁链表
void ListDestory(ListNode* pHead)
{ListNode* cur = pHead->_next;while (cur){ListNode* next = cur->_next;free(cur);pHead->_next = next;cur = next;}
}

注：带头双向循环链表的头插头删，尾插尾删直接复用了插入删除代码。