iOS 数据结构之线性表基本介绍

基本介绍

由于顺序表插入，删除操作需要移动大量的元素（比如数组尾部的效率比头部插入删除的效率高，因为头部插入删除你需要移动n-1个元素），这样造成的效率低下，因为顺序表是内存连续不断的，所以如果插入删除必须移动元素。还好他的根据index获取元素效率比较高，得益于随机访问的特点，即通过首地址和元素序号O（1）的时间内找到。

而链表这样的结构并不是连续不断的在内存中，而是散落在内存中，通过结点的前驱后继指针链接。对于操作指定内存地址的节点链表效率还是比较高的。

再一个链表是动态根据创建结点增加内存，顺序表是先要创建一大块内存，所以提前知道元素count比较重要，如果不知道有可能浪费内存。

下图顺序表内存中的布局：

插入删除的动态图：

如下图链表的内存存储方式：

注意弯曲的由于工具没有弯曲的箭头所以没加上，这个单链表的。

比顺序表如数组多个存储指针的内存部分。

这样分散的方式造成查找某个元素需要从头指针指向的结点开始查找，时间复杂度主要费在这里。

操作的动态图：

复杂度

顺序表操作的复杂度 在表尾插入删除复杂度是O（1） 在表头需要O（n）,所以复杂度是O（n）。优点在于获取元素要比链表效率高，缺点是可能浪费内存。

链表的操作复杂度 费时在检索上，所以大部分都是O（n）。链表优点是节约内存，如果已知道结点指针操作效率高。

对于按值查找 如果顺序表无序则效率两者都是O（n）,如果顺序表有序则效率比链表高,O(log2N)。

Demo

Demo部分包含 双链表的头插法 和 尾插法 插入 删除 链表翻转操作

https://github.com/renmoqiqi/DSLinkedList

参考链接：

http://www.shawpo.me/post/reverse-linked-list/

https://github.com/billryan/algorithm-exercise/blob/master/zh-hans/basics_data_structure/linked_list.md

https://www.izixia.cn/swift-algorithm-club-cn/Linked%20List/

https://foofish.net/linklist-reverse.html