Java基础-常见数据结构

发布于 2018-12-12  62 次阅读


java中的数据结构还有很多,如枚举(Enumeration),向量(Vector),字典(Dictionary)。。。等,这里我们只简单了解一下和集合相关的数据结构即可。

1.  栈 stack :它是运算受限的线性表,其限制是仅允许在标的一端进行插入和删除操作,不允许在其他任何位置进行添加、查找、删除等操作。

特点:先进后出

压栈就是存元素。即,把元素存储到栈的顶端位置,栈中已有元素依次向栈底方向移动一个位置。

弹栈:就是取元素。即,把栈的顶端位置元素取出,栈中已有元素依次向栈顶方向移动一个位置。。

它就像一个瓶子一样只能从上面开始取(弹栈)放入(压栈)也是最顶部

2.  队列 queue :它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。

特点:先进先出

这个就更好理解了,像个管子,一头进另一头出

3.  数组  Array :数组是有序的元素序列,数组是在内存中开辟一段连续的空间,并在此空间存放元素。就像是一排出
租屋,有100个房间,从001到100每个房间都有固定编号,通过编号就可以快速找到租房子的人。

优点:查询元素快,可以通过指定的索引徐速查到元素

缺点:增删元素慢,在增删元素时它需要创建一个新数组,并把原数组的元素根据索引复制到新数组位置

4.  链表 linked list:链表由一系列节点(node,就是一个元素)组成与数组不同的是 它没有索引,但是有一个指向下一个元素的指针(next)

节点(node)
链表(linked list)

缺点:查找元素慢,因为没有索引,只能从头通过节点依次查找

优点:增删元素快,不管是增加还是删除只需要修改节点指向下一个元素的地址即可

5. 红黑树 binary tree:先来理解一下二叉树,实际上二叉树很好理解,每一个元素在选择下一个元素都有两个选择如下图,这样大大缩短了查询的时间。因为红黑树也是二叉树,查找并不会破坏树的平衡,他的查询跟二叉树无异,不同的是二叉树不能插入和删除中间元素,这样会破坏树的平衡。红黑树则有自平衡和黑色平衡性质,这很难一句两句说的明白,以后单独出一片红黑树的文章;

红黑树(binary tree)

特点:CRUD快


Nothing is impossible