数据结构面经

一.链表和数组的区别：
不同：
1.链表是链式的存储结构；数组是顺序的存储结构。
2.链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
3.链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；
4.数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
5.数组从栈中分配空间, 对于程序员方便快速,但自由度小。
链表从堆中分配空间, 自由度大但申请管理比较麻烦.　
相同：
1.两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。
二.链表取元素的时间复杂度：o(n)
三.如何优化这个时间复杂度：
四.堆和栈的区别：
1、堆空间的内存是动态分配的，一般存放对象，并且需要手动释放内存。当然，iOS引入了ARC（自动引用计数管理技术）之后，程序员就不需要用代码管理对象的内存了，之前MRC（手动管理内存）的时候，程序员需要手动release对象。另外，ARC只是一种中间层的技术，虽然在ARC模式下，程序员不需要像之前那么麻烦管理内存，但是需要遵循ARC技术的规范操作，比如使用属性限定符weak、strong、assigen等。因此，如果程序员没有按ARC的规则并合理的使用这些属性限定符的话，同样是会造成内存泄漏的。
2、栈空间的内存是由系统自动分配，一般存放局部变量，比如对象的地址等值，不需要程序员对这块内存进行管理，比如，函数中的局部变量的作用范围（生命周期）就是在调完这个函数之后就结束了。这些在系统层面都已经限定住了，程序员只需要在这种约束下进行程序编程就好，根本就没有把这块内存的管理权给到程序员，肯定也就不存在让程序员管理一说。
从申请的大小方面讲：
栈空间比较小；
堆空间比较大。
从数据存储方面来说：
栈空间中一般存储基本数据类型，对象的地址；
堆空间一般存放对象本身，block的copy等。