目录
一. 链表的概念
二. 单链表的增删查改
1.单链表的定义
2.单链表的头插与头删
3.单链表的尾插与尾删
4.单链表的中间插入删除
5.单链表的查找
三. 带头循环双向链表的增删查改
1.带头循环双向链表的定义
2.带头循环双向链表的头插与头删
3.带头循环双向链表的尾插与尾删
4.带头循环双向链表的中间插入删除
5.带头循环双向链表的查找
一. 链表的概念
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。
在这里介绍链表中的两种结构
无头单向非循环列表：结构简单，一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构，比如说哈希桶等等。
带头双向循环链表：结构最复杂，一般单独存储数据。实际中经常使用的链表数据结构，都是带头双向循环链表。这个结构虽然复杂，但是使用代码实现后会发现这个结构会带来很多优势，实现反而简单了。
二. 单链表的增删查改
1.单链表的定义
在C语言中我们一般创建一个结构体来作为链表的结点
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SListNode;创建初始化一个节点：
void SListInitNode(SListNode** plist, SLDataType x)
{assert(plist);*plist = (SListNode*)malloc(sizeof(SListNode));assert(*plist);(*plist)->data = x;(*plist)->next = NULL;
}2.单链表的头插与头删
1.头插
void SListPushFront(SListNode** plist, SLDataType x)
{assert(plist);SListNode* ptr = *plist;SListInitNode(plist, x);(*plist)->next = ptr;
}2.头删
void SListPopFront(SListNode** plist)
{assert(*plist);assert(plist);SListNode* ptr = (*plist)->next;free(*plist);*plist = ptr;
}3.单链表的尾插与尾删
1.尾插
void SListPushBack(SListNode** plist, SLDataType x)
{assert(plist);if (*plist == NULL){SListInitNode(plist, x);}else{SListNode* ptr = *plist;while (ptr->next){ptr = ptr->next;}SListInitNode(&(ptr->next), x);}
}2.尾删
void SListPopBack(SListNode** plist)
{assert(plist);assert(*plist);if ((*plist)->next == NULL){free(*plist);*plist = NULL;}else{SListNode* ptr = *plist;while (ptr->next->next){ptr = ptr->next;}free(ptr->next);ptr->next = NULL;}
}4.单链表的中间插入删除
1.在pos位置之后插入
为什么不在pos位置之前插入？
在pos位置之前插入需要传单链表的二级指针，
1.用来解决pos指向单链表的头部出现的头插情况
2.用来寻找插入位置的前一个位置，以改变其指向
void SListInsertAfter(SListNode* pos, SLDataType x)
{assert(pos);SListNode* ptr = NULL;ptr = (SListNode*)malloc(sizeof(SListNode));assert(ptr);ptr->data = x;ptr->next = pos->next;pos->next = ptr;
}2.在pos位置之后删除
为什么不删除pos位置？
删除pos位置同样需要传入单链表的二级指针，1.用来解决pos指向单链表的头部出现的单链表指针指向的改变
2.用来寻找pos位置的前一个位置，以改变其指向
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos->next);SListNode* ptr = pos->next;pos->next = pos->next->next;free(ptr);ptr = NULL;
}5.单链表的查找
SListNode* SListFind(SListNode* plist, SLDataType x)
{assert(plist);while (plist){if (plist->data == x)return plist;plist = plist->next;}return NULL;
}三. 带头循环双向链表的增删查改
1.带头循环双向链表的定义
在C语言中我们一般创建一个结构体来作为链表的结点
typedef int LDataType;
typedef struct ListNode
{LDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;创建一个节点：
ListNode* BuyListNode()
{ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));if (tmp == NULL){perror("malloc");}return tmp;
}2.带头循环双向链表的头插与头删
1.头插
void ListPushfront(ListNode* phead, LDataType x)
{assert(phead);ListNode* newnode = BuyListNode();ListNode* tail = phead->next;phead->next = newnode;newnode->next = tail;newnode->prev = phead;tail->prev = newnode;newnode->data = x;//ListInsert(phead->next, x);
}2.头删
void ListPopFront(ListNode* phead)
{assert(phead);ListNode* tail = phead->next;tail->next->prev = phead;phead->next = tail->next;free(tail);//ListErase(phead->next);
}3.带头循环双向链表的尾插与尾删
1.尾插
void ListPushBack(ListNode* phead, LDataType x)
{ListNode* plist = BuyListNode();ListNode* tail = phead->prev;tail->next = plist;plist->prev = tail;plist->next = phead;phead->prev = plist;plist->data = x;//ListInsert(phead, x);
}2.尾删
void ListPopBack(ListNode* phead)
{assert(phead);ListNode* tail = phead->prev;tail->prev->next = phead;phead->prev = tail->prev;free(tail);//ListErase(phead->prev);
}4.带头循环双向链表的中间插入删除
1.插入
void ListInsert(ListNode* pos, LDataType x)
{assert(pos);ListNode* newnode = BuyListNode();pos->prev->next = newnode;newnode->prev = pos->prev;newnode->next = pos;pos->prev = newnode;newnode->data = x;
}2.删除
void ListErase(ListNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}5.带头循环双向链表的查找
ListNode* ListFind(ListNode* phead, LDataType x)
{assert(phead);ListNode* cur = phead->next;while (phead != cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
