Java基础 - 数据结构

数据结构

把多个数据按照一定的存储方式,存储起来,这种存储方式称之为数据结构.

数据的存储方式有很多,数组,队列,链表,栈,哈希表等等.

不同的数据结构,性能是不一样的,比如有的查询比较快,但是增加和删除比较慢；有的增加和删除比较快,但是查询比较慢.

实际开发中如何选择,要看你的需求,是查比较多还是增删比较多,根据你的需求选择合适的即可

1.数组结构

数组是最简单的数据结构，就是用来存储多个相同类型数据的容器

面向对象

    一般的,操作数组比较麻烦,但是如String类,提供了很多方法,把操作数组的算法给封装起来,

    咱们就直接调用某方法即可完成相同的功能.

性能分析:

    增加(Create)、读取(Retrieve)、更新(Update)和删除(Delete) CRUD

1. 增加：

    扩容:性能不好,需要复制数组,扩容次数越多性能越低
   
    不扩容:性能高,只需要操作1次,效率极高
   
    小结:性能不错,效率还是比较高的
   

2. 读取：

    索引查询:操作1次,效率极高
   
    元素查询:元素查询使用的是线性查找,可能是1次找到,也有可能是多次找到,性能一般
   
    小结:性能不错,效率还是比较高的
   

3. 更新：

    通过索引:操作1次,效率极高
   
    小结:性能不错,效率极高
   

4. 删除：

    删除是带有补位的,分情况:删除第一个,性能低,删除最后一个性能高
   
    小结:性能一般,但是出现删除频繁的需求,不应该选择这个数据结构,
   
    一般要删除的内容处于后一半的概率是不高的,不适合删除操作
   

总结:

擅长做增(不扩容)/查/改

2.链表结构

结构跟火车类似

• 单向链表

  从头开始访问,只能访问到相邻的下一元素,不能回头

    class Node{
        Object item;
        Node next;
    }
  

• 双向链表

  从头或者尾部开始访问元素,只能访问相邻的元素,可以来回访问

    class Node{
        Object item;
        Node next;
        Node prov;
    }
  

链表结构的性能分析:

• C

    增加在头或者尾:一次搞定,操作2个节点,非常快,性能极高
  
    增加在中间:必须从头或者尾开始检索,找到了元素后才能进行增加操作,需要操作3个节点,效率不高
  

• R

    读取在头或者尾:一次找到,效率极高
  
    读取在中间:必须从头或者尾开始检索,效率不高
  

• U

    更新在头或者尾:一次找到,直接操作,效率极高
  
    更新在中间:必须从头或者尾开始检索,找到后才能进行修改,效率不高
  

• D

    删除在头或者尾:一次搞定,操作2个节点,直接操作,效率极高
  
    删除在中间:必须从头或者尾开始检索,找到后才能进行删除,操作3个的节点,效率不高
  

总结:

擅长**首尾元素**的CRUD操作

3.队列结构

• Queue：

  单向队列，先进先出。

  增加时只能加入到末尾，删除时只能从头开始删除

• Deque：

  双向队列，既可以先进先出，又可以先进后出

  增加时既能加入到首位也能加入到末尾，删除时既能删除首位也能删除末尾

总结:

擅长频繁的**首尾元素**增删操作

4.栈结构

先进后出,例如手枪的弹夹

压栈：push 压到栈顶

弹栈：pop 删除栈顶元素,并返回栈顶元素

查看：peek 查看栈顶元素