8大数据结构

  • 数组
    • 数组是可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始
    • 查询快，增删慢
  • 链表
    • 链表是物理存储单元上非连续的、非顺序的存储结构，逻辑顺序通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。
    • 查询慢，增删快
  • 队列
    • 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
    • 建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。
    • 队头读取，队尾插入，读取后即释放
  • 栈
    • 它是一种运算受限的线性表【一种先进后出的数据结构】。限制在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底
    • 由操作系统自动分配释放，存放函数的参数值，局部变量的值等（栈使用的是一级缓存，是操作系统为线程建立的存储区域，调用完毕立即释放）
  • 堆
    • 堆通常是一个可以被看做一棵完全二叉树的数组对象。
    • 子节点总是大于(小根堆)或小于(大根堆)父节点
    • 是应用程序在运行的时候请求操作系统分配给自己内存，一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收（堆是二级缓存，生命周期由虚拟机的垃圾回收算法来决定。）
  • 树
    • 树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合
    • 二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化
    • mysql的数据库索引结构用的是B+树
    • HashMap的底层源码中用到了红黑树
  • 图
    • 图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

进程和线程

  • 进程是资源分配的最小单位，线程是CPU调度的最小单位
  • 线程在进程中运行
  • 进程之间数据很难共享，线程之间数据可共享
  • 进程之间互相独立，线程之间相互影响
  • 进程比线程消耗更多的系统资源