【数据结构原理与应用(Golang描述)】② 链表

vouv · · 653 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

                      _ _       _            _   _ _     _   
                     | (_)     | |          | | | (_)   | |  
                     | |_ _ __ | | _____  __| | | |_ ___| |_ 
                     | | | '_ \| |/ / _ \/ _` | | | / __| __|
                     | | | | | |   <  __/ (_| | | | \__ \ |_ 
                     |_|_|_| |_|_|\_\___|\__,_| |_|_|___/\__|

1.1 原理

链表与数组都非常基础也非常常用,从底层数据结构上看,数组需要一块连续的内存空间来存储数据,而链表则不需要,链表通过指针将一组零散的内存块串联起来使用。

日常中有三种常见的链表结构:

  • 单向链表
  • 双向链表
  • 循环链表

1.2 分析

对于单链表来说,插入和删除操作的时间复杂度为 $O(1)$。
双向链表可以支持 $O(1)$ 时间复杂度下找到前驱节点。

1.3 思考

  1. 如何用链表来实现LRU缓存淘汰策略?
  2. 了解Java中的LinkedHashMap的实现原理,其中用到的是什么链表?
  3. 在实践中什么时候选择数组?什么时候选择链表?

1.4 LeetCode练习

  1. 合并两个有序链表
  2. 反转链表
  3. K个一组翻转链表

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:vouv

查看原文:【数据结构原理与应用(Golang描述)】② 链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

653 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传