数据结构与算法分析——链表

链表

链表是一种常见的数据结构,是一组有序的数据,每个链表中的数据项称为元素。

它跟数组很像,二者对比学习会更容易理解和记忆。数组是内存中连续的一块,不会间断。链表在内存中不一定是连续的一块。如果内存只剩 10M,且不是连续的,定义数组就会失败,定义链表就是成功的。数组为了保证内存地址的连续性,当做删除和插入时,需要做大量迁移工作,而链表是不需要迁移操作的。所以数组更适合快速查找,链表更适合插入、删除操作。

链表中会有一些常见属性或方法,比如链表中的元素个数,链表当前的位置,向链表增加一个元素,从链表中删除一个元素,清空链表等一系列操作。

最常见的链表结构

链表结构有很多种,其中三种比较常见:单链表、双向链表、循环链表以及双向循环链表。

单链表

链表是一组节点组成的集合,为了将不连续的内存串联起来,每个节点除了存储数据外,还需要记录下一个节点的地址。

数据结构与算法分析——链表

数据结构与算法分析——链表

如图:data 中保存着数据,next 保存着下一个节点的地址。
链表中,二个节点比较特殊,分别是第一个节点和最后一个节点。第一个节点被叫做头结点,用来记录链表的基地址,由此我们可以轻松找到该链表了。最后一个节点叫做尾节点,它是最后一个节点,没有下一个节点,所以它的指针指向一个空地址。实现LRU就可以用单链表实现。

数据结构与算法分析——链表

数据结构与算法分析——链表
图上,演示了链表的插入和删除操作。也说明了,链表的删除和插入操作不需要移动其他节点。

循环链表

循环链表和和单链表的区别就是尾节点,单链表最后一个节点指向null,而循环链表指向链表的头结点。

数据结构与算法分析——链表

相比单链表,循环链表在找首节点时有着很大的优势,很方便就可以找到首节点。这使得它更适合处理有环形结构的数据,比如约瑟夫问题。

双向链表

数据结构与算法分析——链表

双向链表也叫双链表,它的每个结点都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

相比单链表,在删除或插入特定指针指向的节点时,双链表在删除或插入更具优势。删除操作的时间复杂度都是 O(1) ,但是删除时需要知道前驱指针,双向链表存储了前驱指针,所以可以直接获取到。双链表消耗了更多的空间,但是执行时间少了,是空间换时间的设计思路。

双向循环链表

双向循环链表就是循环链表个双链表的结合,感兴趣可以自己看看,本质差不多。

建议

以上内容很好理解,难点在于实际编码过程。大家可以试试编写,插入和删除操作、单链表的反转、二个链表合并、删除倒数第 n 个节点、找链表的中间节点。以上操作是常见的操作,但真正动手可能没有想象中那么简单。

  1. 理解指针和引用的含义, 初学者在 p->next 、q->next处就会开始犯错,导致链表断裂或者指针丢失( 我就是 )。
  2. 特殊情况要格外小心,bug多出现在这里 。例如链表为空时,链表只有一个节点时。
  3. 可以画图辅助。
  4. 多练习,刷刷题。
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 2
Dennis_Ritchie

把你的php实现,贴出来,瞅瞅 :+1:

1周前 评论

@Dennis_Ritchie 之后会有一篇全是代码的。
我的见习版主可以去掉吗?我这初学,比较担心见习版主的标签会误人子弟。

1周前 评论

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!