常见数据结构

阅读:224

目录结构

  • 1.常用数据有哪些
  • 2.数据的说明
  • 3.集合数据结构介绍
  • 4.集合{List,Set,Map}的特点
  • 5.Queue队列

1.常用数据有哪些?

  • 1.1 如下图所示: 

1.png

2.png

  • 1.2 常见的集合数据 

1.png

2.数据的说明

  • 2.1 数组

    • 无序数组
      • 优点:查询快,如果知道索引可以快速地存取
      • 缺点:删除慢,大小固定
    • 有序数组
      • 优点:比无序数组查找快
      • 缺点:删除和插入慢,大小固定
  • 1.png

  • 2.2 栈

    • 优点:提供后进先出的存取方式
    • 缺点:存取其他项很慢
    • 比如,Android中管理activity进出就是使用栈
  • 2.3 队列

    • 优点:提供先进先出的存取方式
    • 缺点:存取其他项都很慢
  • 2.4 链表

    • 优点:插入快,删除快
    • 缺点:查找慢(一个个节点查)
  • 2.5 二叉树

    • 优点:查找,插入,删除都快(平衡二叉树)
    • 缺点:删除算法复杂
  • 2.6 红-黑树

    • 优点:查找,插入,删除都快,树总是平衡的(局部调整)
    • 缺点:算法复杂
  • 2.7 哈希表

    • 优点:如果关键字已知则存取速度极快,插入快
    • 缺点:删除慢,如果不知道关键字则存取很慢,对存储空间使用不充分
  • 2.8 堆

    • 优点:插入,删除快,对最大数据的项存取很快
    • 缺点:对其他数据项存取很慢
  • 2.9 图

    • 优点:对现实世界建模
    • 缺点:有些算法慢且复杂

3.集合数据结构介绍

  • 3.1 Set集合【一般使用的有TreeSet和HashSet】

  • 3.1.1 TreeSet

    • TreeSet是根据二叉树实现的,也就是TreeMap, 放入数据不能重复且不能为null,可以重写compareTo()方法来确定元素大小,从而进行升序排序。
  • 3.1.2 HashSet

    • HashSet是根据hashCode来决定存储位置的,是通过HashMap实现的,所以对象必须实现hashCode()方法,存储的数据无序不能重复,可以存储null,但是只能存一个。
  • 3.2 List集合【List比较常用的有ArrayList和LinkedList,还有一个比较类似的Vector】

  • 3.2.1 ArrayList

    • 是使用动态数组来实现的,对于数据的随机get和set或是少量数据的插入或删除,效率会比较高。ArrayList是线程不安全的,在不考虑线程安全的情况下速度也比较快的。ArrayList插入数据可以重复,也是有序的,按照插入的顺序来排序。
    • 根据序号读取数据只需直接获取数组对应脚表的数据
  • 3.2.2 LinkedList

    • 内部是使用链表的形式来实现的,在插入大量数据的时候效率比较快。
    • LinkedList根据序号获取数据,是二分进行遍历,如果序号小于总长度的一半,就从链表头部开始往后遍历,直到找到对应的序号。如果序号大于总长度的一半,就从链表尾部往前进行遍历,直到找到对应的序号。拿到数据。
  • 3.2.3 Vector

    • Vector的使用方法和内部实现基本和ArrayList相同,只不过它在add(), remove(), get()等方法中都加了同步。所以它是线程安全的。但是使用效率上就不如ArrayList了。

4.Map集合【HashMap,TreeMap,HashTable】

  • 4.1 HashMap

    • HashMap是基于散列链表来实现的,简单的来说,根据key算出一个hash值,确定一个存放index,但是hash值有可能会冲突重复,所以如果冲突的hash值就需要以链表的形式在同一个index存放了。
  • 4.2 TreeMap

    • TreeMap的使用大致跟HashMap类似,但是内部实现是根据红黑树来实现的。红黑树是一种平衡有序的二叉树,TreeMap的插入删除查询都是依据红黑树的规则来进行的。
  • 4.3 HashTable

    • HashMap和TreeMap都是线程不安全的,多线程操作的时候可能会造成数据错误。Hashtable是线程安全的。其他内部实现,与HashMap都是一样的。

5.Queue队列

5.1 什么是队列

  • 队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。

5.2 队列的种类

  • 单队列(单队列就是常见的队列, 每次添加元素时,都是添加到队尾,存在“假溢出”的问题也就是明明有位置却不能添加的情况)
  • 循环队列(避免了“假溢出”的问题)

5.3 Java 集合框架中的队列 Queue

  • Java 集合中的 Queue 继承自 Collection 接口 ,Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。Queue 用来存放 等待处理元素 的集合,这种场景一般用于缓冲、并发访问。除了继承 Collection 接口的一些方法,Queue 还添加了额外的 添加、删除、查询操作。

赞赏支持


精彩留言

发表评论