ArrayList-vs-LinkList

[TOC]

线性表和非线性表

线性表:顺序表/链表/栈/队列

非线性表:二叉树/图

线性表和非线性表的划分,是根据其逻辑来划分的,而不是根据其存储结构来划分的。每个线性表上的数据最多只有前后两个方向。

顺序表与链表的区别

最本质的区别:顺序表在内存是连续存储的,而链表在内存中是离散存储的。

其他所有的区别,都源于这个最本质的区别,由于顺序表是连续存储的,所以可以根据索引快速的进行查找,但是如果想要插入和删除,为了保持顺序表的连续性,部分元素就需要移位,而这正是链表所擅长的,链表的离散存储特性决定了其无法快速的查找,但是可以快速的进行插入/删除操作。

链表由于其需要另外开辟空间存储下一个节点的指针,所以其比顺序表要耗费更多的内存。并且由于链表的空间是离散分配的,在内存回收后,会产生更多的内存碎片,不方便利用。

线性表的使用场景更多一些,其相较于链表,更节省内存,而且可以借助 CPU 的缓存机制,加速线性表的访问速度。但是其缺点也很明显,其需要占用连续的存储空间,一旦申请的空间很大,就会导致申请失败;另外,如果申请的空间不够用,那么就得向操作系统申请一个更大的连续空间,然后将顺序表中的内容 copy 过去,而 copy 的操作是非常耗时的。

例题分析

palindrome-linked-list

  • 解法一:将链表的数据 copy 到数组中解决

  • 解法二:头插法(逆序)新建一个链表,然后等值匹配

两者的时间复杂度相同,都是 O(n),但是空间复杂度,差距特别大,采用新建链表的方式,其耗费了 12.6M 的内存,比解法一多用 1MB 的内存,这说明,链表的指针,是比较耗费内存的,同样的需求,还是优先考虑用顺序表实现。

该题的最佳空间复杂度是 O(1),以上的两个解法,实际上是在拿空间复杂度换取时间复杂度。