常见的数据结构

数据存储常用结构：栈、队列、数组、链表、红黑树

栈（stack、堆栈）

• 是运算受限的线性表，仅允许在表的一端插入和删除，不允许在其他位置进行添加、查找、删除等

• 特点：先进后出（原理类似于枪的弹夹添加、发射子弹的原理）

• 关键名词：

  ​ 压栈：存元素

  ​ 弹栈：取元素

队列（queue、队）

• 和栈一样，是运算受限的线性表，但是它仅允许表的一端插入，另一端删除元素

• 特点：先进先出（类似于火车进出隧道）

数组（Array）

• 是有序的元素列表，它会在内存中开辟一段连续的空间，并且存放元素。就像是⼀排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房
  ⼦的⼈。

• 特点：

  1. 查找数据快，可以快速访问指定位置的元素

     

  2. 增加、删除元素慢

     • 指定索引位置添加元素：

       需要创建一个新数组（不是原数组），将新元素添加到指定索引位置上（新数组），再把原数组元素根据索引复制到新数组对应索引的位置。

       

     • 指定索引位置删除元素：

       需要创建新数组，将原数组的数据根据索引复制到新数组对应的位置上，原数组中指定索引位置元素不复制到新数组中

       

链表（linked list）

• 由一系列的结点node（链表中的每一个元素都称为结点），结点可以在运行时动态生成，每一个结点都分为两部分：一是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表有单向链表与双向链表。下面是单向链表

• 特点

  1. 多个结点之间，通过地址进⾏连接。例如，多个⼈⼿拉⼿，每个⼈使⽤⾃⼰的右⼿拉住下个⼈的左
     ⼿，依次类推，这样多个⼈就连在⼀起了。

     

  2. 查找元素慢：查找某个元素，需要通过连接的节点，依次向后查找指定元素，有一点像队列

  3. 增删元素快

     （1）增加元素：修改连接下一个元素的地址

     

     （2）删除元素：修改连接下一个元素的地址

     

红黑树（binary tree、二叉树）

• 每个结点不超过2的有序树（tree）

• 类似于我们⽣活中树的结构，只不过每个结点上都最多只能有两个⼦结点。⼆叉树是每个节点最多有两个⼦树的树结构。顶上的叫根结点，两边被称作“左⼦树”和“右⼦树”。

• ⼆叉树的⼀种⽐较有意思的叫做红⿊树，红⿊树本身就是⼀颗⼆叉查找树，将节点插⼊后，该树仍然是⼀颗⼆叉查找树。也就意味着，树的键值仍然是有序的。

• 红⿊树的约束:

1. 节点可以是红⾊的或者⿊⾊的
2. 根节点是⿊⾊的
3. 叶⼦节点(特指空节点)是⿊⾊的
4. 每个红⾊节点的⼦节点都是⿊⾊的
5. 任何⼀个节点到其每⼀个叶⼦节点的所有路径上⿊⾊节点数相同

• 红⿊树的特点:
  速度特别快,趋近平衡树,查找叶⼦元素最少和最多次数不多于⼆倍

的⼦节点都是⿊⾊的
5. 任何⼀个节点到其每⼀个叶⼦节点的所有路径上⿊⾊节点数相同

• 红⿊树的特点:
  速度特别快,趋近平衡树,查找叶⼦元素最少和最多次数不多于⼆倍