链表
文章目录
- 链表
- 前言
- 认识链表
- 单链表结构图
- 带头单循环链表结构图
- 双向循环链表结构图
- 带头双向循环链表结构图
- 链表特点
- 链表实现(带头双向循环链表实现)
- 链表结构体
- (1) 新建头节点
- (2) 建立新节点
- (3)尾部插入节点
- (4)删除节点
- (5)头部插入节点
- (6) 头删节点
- (7) 寻找节点
- (8) pos位置插入节点
- (9) 删除pos位置节点
- (10) 打印链表
- 测试用例
前言
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; //新节点的下一个节点就是pospos->prev = newnode; //pos位置节点prve就链接后面newnode->prev = prev;prev->next = newnode;
}
(9) 删除pos位置节点
void LTErase(LTNode* pos) //删除节点
{assert(pos);LTNode* prve = pos->prev;LTNode* next = pos->next;prve->next = next;next->prev = prve;free(pos);
}
(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);
}