链表
前言
new一个奶黄包:没关系,这条路我陪你走到底
认识链表
单链表结构图
带头单循环链表结构图
双向循环链表结构图
带头双向循环链表结构图
链表特点
-
单链表在内存中,并不是连续存储的(逻辑上连续)。
-
不支持随机访问
-
插入时只需要改变指针指向
-
没有容量的概念
-
可以高效的在任意位置插入&&删除
-
缓存利用率低
链表实现(带头双向循环链表实现)
链表结构体
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
(1) 新建头节点
LTNode* ListInit()//建立头节点
{
LTNode* phead = buyListNode(-1); //建立一个带头节点
phead->next = phead;
phead->prev = phead;
return phead;
}
(2) 建立新节点
LTNode* buyListNode(LTDataType x)//创建内存初始化数据
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
// 初始化:注意所对的结构来初始化
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
(3)尾部插入节点
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = buyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
(4)删除节点
void LTPopBack(LTNode* phead)
{
assert(phead);
LTNode* tail = phead->prev; //记录上一个节点
LTNode* tailmove =tail->prev; //记录上一个节点的上一个节点
tailmove->next = phead;
phead->prev = tailmove;
free(tail);
}
(5)头部插入节点
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = buyListNode(x);
LTNode* first = phead->next;
newnode->next = first;
first->prev = newnode;
first->next = phead;
phead->prev = first;
}
(6) 头删节点
void LTPopFront(LTNode* phead)
{
assert(phead); //判断是否有头节点
assert(phead->next != NULL); //判断第一个节点是否存在
LTNode* tail = phead->next;
LTNode* tailmove = tail->next;
tailmove->prev = phead;
phead->next = tailmove;
tailmove->next = phead;
phead->prev = tailmove;
free(tail);
}
(7) 寻找节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
//printf("找到了");
return cur;//返回指针
}
cur=cur->next; //每次都走到下一个节点直到phead
}
//printf("找不到");
return NULL;
}
(8) pos位置插入节点
void LTInsert(LTNode* pos, LTDataType x)//头插尾插都可以调用这个函数
{
assert(pos);
LTNode* newnode = buyListNode(x); //新建一个节点
LTNode* prev = pos->prev; //记录pos位置的前一个节点
newnode->next = pos; //新节点的下一个节点就是pos
pos->prev = newnode; //pos位置节点prve就链接后面
newnode->prev = prev;
prev->next = newnode;
}
文章来源:https://www.toymoban.com/news/detail-655496.html
(9) 删除pos位置节点
void LTErase(LTNode* pos) //删除节点
{
assert(pos);
LTNode* prve = pos->prev;
LTNode* next = pos->next;
prve->next = next;
next->prev = prve;
free(pos);
}
文章来源地址https://www.toymoban.com/news/detail-655496.html
(10) 打印链表
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!= phead)
{
printf("-> %d ",cur->data );
cur = cur->next;
}
}
测试用例
void test1()
{
LTNode* ptail = ListInit();
LTPushBack(ptail, 1);
LTPushBack(ptail, 3);
LTPushBack(ptail, 2);
LTPushBack(ptail, 4);
LTPushBack(ptail, 5);
LTPopBack(ptail);
LTPrint(ptail);
}
到了这里,关于数据结构——链表详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!