java面试重点-java基础 数据类型

链表

链表是一种物理上非连续,非顺序的存储结构,数据元素之间的顺序是通过每个元素的指针关联的

链表有一系列节点组成,每个节点一般至少会包含两部分的信息:

1. 元素数据
2. 指向下一个元素的指针

链表分类:

1. 单向链表和双向链表

2. 静态链表(数组实现),动态链表(指针)

链表的操作:创建,插入,删除,输出

链表的特点:

1. 物理 空间不连续,空间开销更大
2. 在运行时可以动态添加
3. 查找元素需要顺序查找

数组

数组分为一维数组和二维数组

数组的语法:

数据类型[] 数组名= new 数据类型[数组长度]; 

数组类型 数组名[] = new 数组类型[数组长度];

数组元素分配的初始值

数组元素的表示与赋值:

由于定义数组时,内存分配的是连续空间,所以数组元素在数组里顺序排列编号,该编号即元素下标,它标明了 元素在数组中的位置

Java 支持多维数组,但从内存分配原理的角度讲,Java 中只有一维数组,没有多维数组

总结:

数组是可以在内存中连续存储多个元素的结构,数组中的所有元素必须属于相同的数据类型

数组中的元素通过数组的下标进行访问,数组的下标从0开始

二维数组实际上是一个一维数组,它的每个元素有事一个一维数组

使用Array类提供的方法可以方便地对数组中的元素进行排序,查询等操作

二叉树

二叉树是每个节点最多有两个子树的树结构,通常子树被称作"左子树"和"右子树",左子树和右子树同时也是 二叉树,二叉树的子树有左右之分,并且次序不能任意颠倒.二叉树是递归定义的

斜树: 所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)

满二叉树: 所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树.就是完美圆满 的意思,关键在于树的平衡.

特点为: 叶子只能出现在最下一层 非叶子节点度一定是 在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多 

完全二叉树: 对一颗具有 n 个结点的二叉树按层序排号,如果编号为 i 的结点与同样深度的满二叉树编号为 i 结点在二叉树 中位置完全相同,就是完全二叉树,满二叉树必须是完全二叉树,反过来不一定成立

特点:

叶子结点只能出现在最下一层(满二叉树继承而来) 最下层叶子结点一定集中在左部连续位置 倒数第二层,如有叶子结点,一定出现在右部连续位置 同样结点树的二叉树,完全二叉树的深度最小(满二叉树也是对的)

二叉树的遍历

前序遍历:

基本思想: 先访问根结点,再先序遍历左子树,最后再先序遍历右子树即根一左一右

中序遍历:

基本思想:
先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树即左一根一右

后序遍历:

基本思想:
先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左一右一根

二叉树的作用:

二叉排序树是一种比较有用的折衷方案

数组的搜索比较方便,可以直接用下标,但删除或者插入某些元素就比较麻烦

链表与之相反,删除和插入元素很快,但查找很慢

二叉排序树就既有链表的好处,也有数组的好处

在处理大批量的动态的数据是比较有用 

用的最多的应该是平衡二叉树,有种特殊的平衡二叉树红黑树,查找,插入,删除的时间复杂度最坏为 O(log n) 

平衡二叉树/红黑树就是为了将查找的时间复杂度保证在 O(logN)范围内 

二叉树之所以重要,是因为它支持或拥有的操作,包括增删改查重要的操作,复杂度比完成同样功能的其他结构 更低