关于数据结构的一些想法

前言

写这篇文章的动机呢，其实是洗澡的时候突然想到，并结合平时中的一些感受所产生的：大多数学数据结构的人，总是给我一种为了学数据结构而学的感觉。

问题

数据结构和算法，这两个好兄弟不论是在本科的课程里还是在面试中，都是最基础的考察项目。但是大多数人，在刚刚入门的时候，比如刚学习完一门语言的语法，准备深入学习的时候，就会有人告诉说：该学数据结构了。然后从天而降一个链表让你学，学会了用就完事了，迷迷糊糊学完之后，又塞来一个二叉树…

关系

一般在教材中，每个不同的结构都是分成不同的章节进行讲解的，通常是列表、树、图…这样的顺序展开。从分类和学习进度上，这样并没有问题，但是在学习的时候，由于每个部分被分成不同的章节，而在表面上看起来没有关联。
这就是问题所在，每一种数据结构都是层层递进的。

开始

每一个数据结构和算法都是根据需要而被一个个发明创造出来的。链表、栈、树、图…这些东西不是一开始就存在，而是根据需要而被前辈发明出来，并且经过抽象和提炼后，总结出最基础、最常用的这几种结构作为入门。但是我们在学习的时候，不是为了学习掌握这种结构，而是需要掌握如何创造结构。
数组不够灵活，所以有了能够灵活分配空间的单链表；单链表只能向后不能往前，所以就有了前后指针的双向链表；数组和链表的操作太多了，我只需要排队或者做一个桶的功能，所以屏蔽了多余的功能，有了以数组或链表为基础的栈和队列；链表是一维的线性结构，查找只能从头或尾巴依次遍历，效率太低怎么办？把一维的线性结构转换为非线性的，把单链表的next指针拆分成两个(left和right)并规定比我小的在左边，大的在右边，于是便有了二叉排序树；排序树依赖插入顺序，最差情况(左斜树或右斜树)还是退化成一个链表，那就规定左右子树的高度差不能超过1，不平衡的时候需要通过左右旋的操作保持平衡，这就成了AVL平衡树。在此基础上，对条件、性能的不同要求，从而不断的改造出了B树、红黑树等等亚种。
那图呢？一样的，链表和数组既然只能存储一维的信息，那用两个链表或者数组套起来，不就是二维的吗？链表的每个节点保存每个子链表的头结点，每个一级数组保存子数组的起点，不就是二维的吗？此上结合数论，将图拆分成点和边分别存储，于是就有了以数组为基础的邻接表，以链表为基础的十字链两种存储图的方式，甚至还有结合数组和链表的多重邻接表。

结论

说了这么多，其实总结就一些。学数据结构学的不是结构本身，而是研究结构是如何被创造出来的，如何根据需要 去创造新的高效的方案。换句话说，就是无招胜有招，在掌握本质之后，就可以根据需要直接创造出需要的结构。