常用数据结构

js基本类型与引用类型的区别

基本类型有:undefined,boolean,number,string,null
引用类型有:Object,Array,Date等

基本类型的变量是存放在栈区的(栈区指内存里的栈内存),栈区包括了 变量的标识符和变量的值。
image

引用类型的值是同时保存在栈内存和堆内存中的对象,栈区内存保存变量标识符和指向堆内存中该对象的指针
image

常见的数据结构

常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等
image

1、数组

数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问

2、栈

栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
image

3、队列

队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队。
使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
所谓的双向链表,只是加了一个向前的线索的链表而已。

5、树

由n(n>=1)个有限节点组成一个具有层次关系的集合,特点:

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树;

二叉树

image
二叉树是树的特殊一种,具有如下特点:

1、每个结点最多有两颗子树,结点的度最大为2。
2、左子树和右子树是有顺序的,次序不能颠倒。
3、即使某结点只有一个子树,也要区分左右子树。

6、散列表/哈希表

关键码和值 (key和value) 直接进行访问的数据结构

7、堆

堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

8、图

图是由结点的有穷集合V和边的集合E组成。