多种链表
根据不同的需求，实践应用中衍生出了多种不同的链表结构，有单向和双向链表、带头结点和不带
头结点的链表、循环和非循环的链表
注意:循环链表遍历的终点是头节点
双向链表的实现
单链表的结点中保存了指向后继结点的地址，所以单链表中找当前结点的后继结点很容易，但要获取当前结点的前驱结点就很麻烦，就只能从头开始往后遍历获取，时间复杂度为 O(n)；所以单链表中只有当前结点的指针 pos 时 (没有头指针)，想要在 pos 之前插入结点和删除 pos 位置结点都是无法实现的。
双向链表相比单链表最大的特征是每个结点中多了一个前驱指针，一些场景需要获取当前结点前驱结点的场景中就需要用双链表实现，如：倒着遍历、删除当前结点、在当前结点前插入结点等。
双向链表的一些不足是找尾结点依旧不是很方便，另外呢，头尾插入删除考虑的边界依旧比较多。 后面的带头双向循环链表可以很好的解决这个问题
节点的结构
要有一个数据域,前驱指针和后驱指针
typedef int DCLDataType;
typedef struct DCLListNode {
DCLDataType data; // 存储数据元素的值
struct DCLListNode* prev; // 存放前驱结点的指针
struct DCLListNode* next; // 存放后继结点的指针
}DCLListNode;
初始化
和之前的单链表相似,多了prev指针的指向问题
// 创建一个新结点
DCLListNode* BuyListNode(DCLDataType data)
{
DCLListNode* newNode = (DCLListNode*)malloc(sizeof(DCLListNode));
if (newNode == NULL)
{
printf("申请空间失败\\n");
return NULL;
}
newNode->data = data;
newNode->next = newNode;
newNode->prev = newNode;
return newNode;
}
// 链表初始化
DCLListNode* DCLListInit()
{
DCLListNode* head = BuyListNode(-1);
return head;
}
销毁
和单链表比较相似,遍历,删除,一定要记录下一个指针
// 销毁链表
void DCLListDestroy(DCLListNode* L)
{
assert(L);
DCLListNode* cur = L->next;
while (cur != L)
{
DCLListNode* next = cur->next;
free(cur);
cur = next;
}
}
插入
直接告诉你pos的指针,直接修改指针走向即可,和单链表那里类似,如果不引入新节点一定要注意修改的顺序,避免断链
// 在pos位置后插入值为x的结点,pos为下标值
void DCLListInsert(DCLListNode* pos, DCLDataType x)
{
assert(pos);
DCLListNode* newnode = BuyListNode(x);
DCLListNode* next = pos->next;
//pos next
// newnode
newnode->next = next;
newnode->prev = pos;
pos->next = newnode;
next->prev = newnode;
}
删除
直接告诉你pos的指针,直接修改指针走向即可
// 删除pos位置的结点
void DCLListDelete(DCLListNode* pos)
{
assert(pos);
DCLListNode* prev = pos->prev;
DCLListNode* next = pos->next;
//prev pos next
prev->next = next;
next->prev = prev;
free(pos);
}
获取下标位置的值
遍历,注意边界i的处理
// 获取链表的位序i的结点
DCLListNode* DCLListGetElem(DCLListNode* L, int i)
{
DCLListNode* cur = L->next;
int j = 0;
while (cur!=L && j < i)
{
cur = cur->next;
j++;
}
if (j == i)
return cur;
else
return NULL;
}
头插尾插,头删尾删,打印
可以复用插入和删除的代码,打印就是遍历一遍,都比较简单这里不多做赘述
// 头插
void DCLListPushFront(DCLListNode* L, DCLDataType x)
{
assert(L);
DCLListInsert(L, x);
}
// 尾插
void DCLListPushBack(DCLListNode* L, DCLDataType x)
{
assert(L);
DCLListInsert(L->prev, x);
}
// 头删
void DCLListPopFront(DCLListNode* L)
{
assert(L);
DCLListDelete(L->next);
}
// 尾删
void DCLListPopBack(DCLListNode* L)
{
assert(L);
DCLListDelete(L->prev);
}
// 打印链表中的元素
void DCLListPrint(DCLListNode* L)
{
assert(L);
DCLListNode* cur = L->next;
while (cur!=L)
{
printf("%d-> ", cur->data);
cur = cur->next;
}
}
