容器底层

原创
2019/11/17 21:23
阅读数 82

1.1数据结构

Java提供了丰富的容器技术,这些容器技术在底层是通过各种各样的数据结构来实现。现实生活中的存储,我们使用的是工具和建模。每种数据结构都有自己的优点和缺点,为了方便查询等一系列操作,引进算法概念,来帮助我们在存储的数据中做到最快的插入,删除,查找等操作,常见的数据结构:堆栈、队列、数组、链表和红黑树等。

1.2常见的数据结构:

1.2.1 栈(stack)

  栈 是运算受限的线性表,其限制是仅允许在栈的一端进行插入和 删除操作,不允许在其它任何位置进行添加,查找,删除等操作。
  • 先进后出:存进去的元素,要在后它后面的元素依次取出后,才能取出该元素
  • 压栈:存元素,把元素存在栈的顶端位置
  • 弹栈:取元素,把栈顶端元素取出

1.2.2 队列(queue)

  队列: 同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在 队列的一端进行插入,而在队列的另一端进行删除
  • 先进先出:存进去的元素,它前面的元素依次取出后,才能取出该元素。
  • 队列的入口、出口各占一侧。

1.2.3数组(Array)

  数组:有序的元素序列,数组是在内存中开辟一段连续的空间,并在此空间存放元素。

  • 查找元素快,通过索引,可以快速访问指定位置上的元素
  • 增删元素慢:指定索引增加元素,需要创建一个新的数组,将指定的新元素存储在指定位置,把原数组中的元素根据索引,复制到数组对应的位置上,相当于从删除元素的索引开始,后一个索引内容覆盖前一个索引内容。

1.2.4 链表(Linked list)

链表:linked list 由一系列结点node(链表中的每一个元素成为节点)组成,节点可以在运行时动态生成。每个节点包括两部分:yige存储数据的数据域,另一个是存储下一节点地址的指针域,我们常说的链表结构有单向链表和双向链表,这里研究单向链表

  •  多个节点之间,通过地址进行连接。
  • 查找元素慢,想要查找某个元素,需要通过连接的节点,依次向后查找指定的元素
  • 增删元素快:增加时,只需要修改连接下个元素的地址;删除时,只需要修改连接下个元素的地址即可

1.2.5红黑树(二叉树binary tree)

   二叉树:每个节点不超过2的有序树,存放的数据必须是可排序的

  • 每个节点最多有两个子节点
  • 二叉树是每个节点最多有两个节点的树结构,顶上叫根节点,两边叫左右子树

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部