链表补充及链表和数组的区别
2018-06-18 03:57:03来源：未知 阅读 ()
初稿：2017-11-19 13:05:57
4种链表
- 不循环单链表：加头结点，使得插入删除操作相同，不必特别处理插入或删除的是第一个位置的情况。
- 循环单链表：引用参数是最后一个结点的指针pTail，这样既能迅速找到首结点pHead = pTail->next，也能迅速获取表尾。
- 不循环双向链表：p所指结点后插入结点q. q->next = p->next; p->next->pre = q; p->next = q; q->pre = p;
- 循环双向链表：引用参数首或尾都可。
链表和数组的区别
数组初始容量一旦确定，不能再改变，适合要处理的数据量已知的情况。
未知要处理的数据量使用数组，可能造成空间浪费或容量不足，虽然有动态数组可扩容，但是频繁扩容会使系统产生很大的开销。
链表容量不限，长度与元素个数相同，但是需要额外的空间存放下一元素的地址，空间使用率不如数组。
按index查找，数组存取元素时间复杂度是O（1），链表是O（n）
链表插入和删除时间复杂度是O（1），数组是O（n）
查找值是value的某个元素，速度则相同。
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：转移Blog
下一篇：Leetcode刷题
- leetcode 反转链表 2020-06-06
- 数据结构—链表 2020-05-29
- STL之list 2020-04-30
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
- STL之deque 2020-04-29
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
