数据结构（基础）

什么是数据结构

数据结构就是按照一定的逻辑把元素按照一定关系进行存储的数据

数据结构分类

可以分为逻辑机构和物理结构两大类

• 逻辑结构

  1.集合机构，指的是一堆没有任何关系的数据存储在一个集合中，它们是平级的

  2.线性结构，所有的的数据都存在1对1的关系、

  3.树形结构，树状机构中存在着1对多的关系

  4.图形结构，图形结构中存储着多对多的复杂关系

• 物理结构

  1.顺序结构，所有的数据都是存储在一个连续内存当中的，它的逻辑关系和物理关系是一致的。

  2.链式存储结构，在链式存储结构中，存储单元可以是连续的也可以是不连续的，元素之间不能反映元素的逻辑关系，只存储元素的引用地址。根据指针来确定彼此的逻辑关系

线性表

• 线性表是最基本，最简单的数据结构，一个线性表是一组拥有相同特征的元素的有限序列
• 线性表特征
  • 表中第一个元素没有前驱，它是线性表的头结点。
  • 表中最后一个元素没有后继，它是线性表的尾结点。
  • 除了第一个和最后一个元素外，其他元素都拥有前驱和后续结点。

线性表的分类

根据不同的存储方式分类，线性表可以分为顺序表和链表

顺序表

• 顺序表是一种以数组方式进行表示的线性表，顺序表中元素间的逻辑与物理存储的逻辑一致，表中的元素是存储在一个连续内存当中的。

链表

• 之前我们已经使用顺序存储结构实现了线性表，我们会发现虽然顺序表的查询很快，时间复杂度为O(1),但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以使用另外一种存储结构实现线性表，链式存储结构。
• 链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

单向链表

• 单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。单向链表查找或者插入数据都要从头部开始查找。