本文主要是介绍单向链表与双向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
当使用单向链表查看链表中某个节点的数据，可以使用快慢指针法
快慢指针：
快慢指针是一种在链表和数组中常用的算法技巧，主要用于解决链表或数组中的问题，如检测环
存在、找到环的入口、计算链表的中点等。快慢指针的核心思想是使用两个指针以不同的速度遍
链表或数组：
>慢指针（Slow Pointer）：每次移动一步。
>快指针（Fast Pointer）：每次移动两步。
使用场景
检测链表是否有环：
-
如果快指针最终追上慢指针，说明链表中有环。
-
如果快指针到达链表的末尾，说明链表中没有环。
bool HasCircle(Node *head)
{if(head == NULL)return false;Node *slow = head, *fast = head;while(fast != NULL && fast->next!=NULL){slow = slow->next; //慢指针每次前进一步fast = fast->next->next;//快指针每次前进两步if(slow == fast) //相遇，存在环return true;}return false;
}输出链表中的倒数第K个节点(即正数第K-1个节点)
Link_node_t * find_k_link(Link_t *plink,int key)
{Link_node_t *pfast = find_link(plink,key);if(NULL == pfast){return NULL;}pfast = pfast->pnext;Link_node_t *pslow = plink->phead;while(pfast != NULL){pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;
}单向链表倒置
int inver_link(Link_t *plink)
{int len = link_lenth(plink);if(len == 0){return -1;}Link_node_t *ptemp = plink->phead;plink->phead = NULL;Link_node_t *pinsert = NULL;while(ptemp != NULL){pinsert = ptemp;ptemp = ptemp->pnext;pinsert->pnext = plink->phead;plink->phead = pinsert;}return 0;
}
单向链表排序（插入法）
将待插入的数，插入到一个有序的序列中，使得到的序列仍然有序
void insert_sort(Link_t *plink)
{Link_node_t *ptemp = plink->phead->pnext;plink->phead->pnext = NULL;while(ptemp != NULL){Link_node_t *pinsert = ptemp;ptemp = ptemp->pnext;Link_node_t *p = NULL;if(plink->phead->data > pinsert->data){pinsert->pnext = plink->phead;plink->phead = pinsert;}else{p = plink->phead;while(p->pnext != NULL && p->pnext->data < pinsert->data){p = p->pnext;}pinsert->pnext = p->pnext;p->pnext = pinsert;}}
}valgrind
在使用和操作链表时，需注意内存泄漏的情况，可以使用Valgrind来检查内存泄漏的情况
Valgrind 是一个编程工具，主要用于内存调试、内存泄漏检测、以及性能分析。
使用场景
>内存泄漏检测：检查程序是否在不再需要时未能释放分配的内存。
>内存越界：检测数组越界、堆栈缓冲区溢出等错误。
>线程错误：检查多线程程序中的同步问题，如死锁、竞争条件等。
>性能分析：分析程序的性能瓶颈，如CPU周期使用、内存访问模式等。
安装valgrind
sudo apt-get update
sudo apt-get install valgrind
运行valgrind
valgrind [选项] 程序名 [程序参数]
使用示例：
双向链表
双向链表与单向链表的区别：
单向链表只有一个后继指针
对于单向链表的某一个节点，只能找到其后的节点，而不能找到之前的节点
基础操作
头插
int push_doulink_head(Dlink_t *plink,DataType data)
{Dlink_node_t *pdouble = malloc(sizeof(Dlink_node_t));if(NULL == pdouble){return -1;}pdouble->data = data;pdouble->pnext = NULL;pdouble->ppre = NULL;if(is_empty_link(plink)){plink->phead = pdouble;}else{pdouble->pnext = plink->phead;plink->phead->ppre = pdouble;plink->phead = pdouble;}plink->clen++;return 0;
}尾插
int push_doulink_end(Dlink_t *plink,DataType data)
{Dlink_node_t *pnode = malloc(sizeof(Dlink_node_t));if(NULL == pnode){return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if(is_empty_link(plink)){push_doulink_head(plink,data);}else{Dlink_node_t *p = plink->phead;while(p->pnext != NULL){p = p->pnext;}p->pnext = pnode;pnode->ppre = p;}plink->clen++;return 0;
}头删
int pop_link_head(Dlink_t *plink)
{Dlink_node_t *pnode = plink->phead;if(plink->phead ==NULL){return 0;}else{Dlink_node_t *pdel = pnode;plink->phead = pnode->pnext;pnode->pnext->ppre = NULL;free(pdel);}plink->clen--;return 0;
}尾删
int pop_link_end(Dlink_t *plink)
{Dlink_node_t *pnode = plink->phead;if(plink->phead == NULL){return 0;}else if(pnode->pnext == NULL){pop_link_head(plink);}else{while(pnode->pnext->pnext != NULL){pnode = pnode->pnext;}pnode->pnext = NULL;free(pnode->pnext);}return 0;
}这篇关于单向链表与双向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
