前言

从数据结构说起，面试了很多人，对于数据结构总是说不清楚，有的说数组、链表，有的混进来堆、栈，甚至有的说不清队列和堆的区别。这里写一篇博客，总结下常见的数据结构认识误区，就先从数组、链表开始吧。

区分

数组、链表是最基础的数据结构之一，是一维的数据结构，他们的区别是：

数组中元素地址连续的，链表中两个元素地址不一定连续，而是由专门的一个指针指明该元素的后一个（前一个）元素的地址。

在此之上再衍生出来的其他一维数据结构包括：队列、栈、堆。他们都是满足一定规则、或者说一定特性的数组、链表的拓展。这些拓展数据结构，底层都可以使用数组或链表（基础一维结构）来实现。

PS：堆比较特殊，是指用数组实现的二叉树。

堆区、栈区

对于操作系统为程序运行区分的堆区、栈区，也有很多的和堆、栈数据结构搞混，这里介绍下什么是堆区、栈区。

堆区

由程序员调用malloc()函数来主动申请的，需使用free()函数来释放内存，若申请了堆区内存，之后忘记释放内存，很容易造成内存泄漏

栈区

栈区由编译器自动分配释放，存放函数的参数值、返回值和局部变量，在程序运行过程中实时分配和释放，栈区由操作系统自动管理，无须手动管理。栈区是先进后出原则，即先进去的被堵在屋里的最里面，后进去的在门口，释放的时候门口的先出去。

程序内存分布

补充：
代码区：存放程序的代码，即CPU执行的机器指令，并且是只读的。
常量区：存放常量(程序在运行的期间不能够被改变的量，例如: 10，字符串常量”abcde”， 数组的名字等)
静态区（全局区）：静态变量和全局变量的存储区域是一起的，一旦静态区的内存被分配, 静态区的内存直到程序全部结束之后才会被释放

小结

这期介绍了一些一维数据结构，哪些是基础存在的，哪些是衍生的。后续会将其中每一个拎出来讲，侧重点是实现方法和其中的优化点。不要小看了数据结构，很多巧妙的思想都是可以在这些数据结构的实现中找到。

参考

https://www.jianshu.com/p/afbfc784238a
https://blog.csdn.net/u014470361/article/details/79297601