数据结构
计算机中的数据有多种类，如何处理数据就成为了一门学问。而数据结构就是关于数据组织和处理的一门学问。
数据结构包括下面三方面内容：
数据逻辑结构
描述数据元素之间的逻辑关系。
数据的物理结构
描述数据元素是在具体计算机设备中如何保存的。
数据的操作方法
也常被称为算法，是一种说明如何操作数据的方法。
常见数据逻辑结构
顺序表
就是内存中一块连续的区域,紧密排列了一些相同类型的数据.也就是我们常说的数组.
特点:需要事先知道同样的元素最多有多少个,不然就无法开辟出合适的内存区域(要么太多而浪费,要么太小而不足).
思考:能不能有一种数据结构,能够灵活地按需而分配空间呢?
答:动态数组或链表
动态数组,按需要可进行连续空间的增加或减少.完全按需分配.
链表
链表的基本单是节点,每个节点拥有一个数据区和next指针，其中数据区用于存放数据，next指针指向下一个节点。
与顺序表相比，链表可以根据需要*选择节点的数据，从而解决了内存分配不合适的问题。且对内存空间连续块要很低，只要能满足节点的大小即可。
两者的使用比较
查找某一位置元素的速度
顺序表，可以通过下标，直接询问任一元素。即时间复杂度为O(1)
链表，只能通过第一个节点开始，一个一个的沿着next指针数过去。即时间复杂度为O(N)
插入和删除的速度
顺序表在插入和删除元素时，需要找到特定位置的元素，然后将其后面的全部元素都向前移动或向后移动，以填补或腾出空位因此顺序表的插入和删除的时间复杂度都是O(N)
链表只需要摘去或者挂上一个节点就行了，因此链表的插入和删除的时间复杂度都是O(1);
插入元素的方式
顺序表，只能一个一个从前向后装数据，也就是尾插法
链表有头插头和尾插尝两种。头插法就是把新节点直接插在节点链的头部，比较适合构造栈；尾插尝就是把新节点插在链表末尾，比较适合构造队列，而且需要额外的指针指向尾节点。
插入过程如下：
1.将new_node的next指向要插入位置的后一个节点，即new_node->next = p->next
2.将插入位置的前一个节点的next指针指向new_node，即p->next = new_node