数据结构

定义：

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

逻辑结构

数据元素之间的逻辑关系（抽象的）

集合结构

线性结构

树形结构

图形结构

存储结构

数据结构在计算机中的表示，分为顺序存储、链式存储、索引存储、散列存储，在根本上讲分为顺序存储、链式存储。

顺序存储

顺序存储是指在内存中开辟连续的存储空间来存放数据，比较有代表性的就是数组的存储方式是使用的顺序存储来存储元素对象的；所以我们可以通过数组来观察顺序存储的优缺点。

优点：查询、遍历效率高、可以实现随机存取，每个元素占用最少空间。

缺点：增删改效率低，只能使用整块的存储单元，会产生较多的碎片。

链式存储

链式存储的存储空间不是连续的，它是通过指针来指向下一个元素或者上一个元素的地址来定位到该元素的，链式存储的由数据域（data域）与指针域（也叫做地址域，单向链表只有尾指针，双向链表有头指针和尾指针）两部分构成，通过指针指向下一元素，将所有的元素穿插起来，从而形成了一个链表。

优点：增删改效率高，充分利用所用的存储单元，不会出现碎片现象。

缺点：查询、遍历效率低，需要额外的存储空间来存放下一结点的指针，只能实现顺序存取。

常用的数据结构

数组（Array）
队列（Queue）
链表（Linked List）
栈（Stack）
树（Tree）
散列表（Hash）
堆（Heap）
图（Graph）

线性表

定义：

由n（n>=0）个相同类型新元素组成的有序集合。线性表中元素个数n,称为线性表的长度。当n=0时，为空表。

特点：

表中元素个数是有限的
表中元素的数据类型都相同，每一个元素占用相同的空间大小
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序

常见的线性表：

数组（Array）
队列（Queue）
链表（Linked List）
栈（Stack）

数据结构基础知识