当前位置:   article > 正文

Java常用类库之集合概念_java常用类库概念

java常用类库概念

集合Collection

1. 类集设置的目的

对象数组有那些问题?普通的对象数组的最大问题在于数组中的元素个数是固定的,不能动态的扩充大小,所以最早的时候可以通过链表实现一个动态对象数组。但是这样做毕竟太复杂了,所以在 Java 中为了方便用户操作各个数据结构,所以引入了类集的概念,有时候就可以把类集称为 java 对数据结构的实现

在整个类集中的, 这个概念是从 JDK 1.2(Java 2) 之后才正式引入的, 最早也提供了很多的操作类, 但是并没有完整的提出类集的完整概念。

类集中最大的几个操作接口:Collection、 Map、 Iterator,这三个接口为以后要使用的最重点的接口。所有的类集操作的接口或类都在 java.util 包中。

2. 常见的数据结构

2.1 栈(stack)

栈:又称堆栈,栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈。栈又称为先进后出的线性表

采用栈结构的集合,对元素的存取有如下的特点:

  • 先进后出(即,存进去的元素,要在后它后面的元素依次取出后,才能取出该元素)。例如,子弹压进弹夹,先压进去的子弹在下面,后压进去的子弹在上面,当开枪时,先弹出上面的子弹,然后才能弹出下面的子弹。
  • 栈的入口、出口的都是栈的顶端位置。

这里两个名词需要注意:

  • 压栈:存元素。
  • 弹栈:取元素。

2.2 队列(queue)

队列:队,队列是一种特殊的线性表,是运算受到限制的一种线性表,只允许在表的一端进行插入,而在另一端进行删除元素的线性表。队尾(rear)是允许插入的一端。队头(front)是允许删除的一端。空队列是不含元素的空表。

采用队列结构的集合,对元素的存取有如下的特点:

  • 先进先出(即,存进去的元素,要在后它前面的元素依次取出后,才能取出该元素)。例如,小火车过山洞,车头先进去,车尾后进去;车头先出来,车尾后出来。
  • 队列的入口、出口各占一侧。

2.3 链表

链表 [Linked List]:链表是由一组不必相连(内存不必相连:可以连续也可以不连续) 的内存结构(节点) ,按特定的顺序链接在一起的抽象数据类型。

2.3.1 链表节点
class Node{
    Object data;
    Node next;
}
  • 1
  • 2
  • 3
  • 4
2.3.2 数组和链表的区别和优缺点:

数组是一种连续存储线性结构,元素类型相同,大小相等

  • 数组的优点:
    • 存取速度快
  • 数组的缺点:
    • 事先必须知道数组的长度
    • 插入删除元素很慢
    • 空间通常是有限制的
    • 需要大块连续的内存块
    • 插入删除元素的效率很低

链表是离散存储线性结构
n 个节点离散分配,彼此通过指针相连,每个节点只有一个前驱节点,每个节点只有一个后续节点,首节点没有前驱节点,尾节点没有后续节点。

  • 链表优点:
    • 空间没有限制
    • 插入删除元素很快
  • 链表缺点:
    • 查找元素很慢
    • 存取速度很慢

链表常用的有 3 类: 单链表、双向链表、循环链表。

2.3 二叉树(binary tree)

简单的理解,就是一种类似于我们生活中树的结构,只不过每个结点上都最多只能有两个子结点。二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点,两边被称作“左子树”和“右子树”。

class Node{
    Object data;
    Node left;
    Node right;
}
  • 1
  • 2
  • 3
  • 4
  • 5

3. Collection接口

Collection接口是在整个 Java 类集中保存单值的最大操作父接口,里面每次操作的时候都只能保存一个对象的数据。此接口定义在 java.util 包中。

public interface Collection<E> extends Iterable<E>
  • 1

但是,在开发中不会直接使用 Collection 接口。而使用其操作的子接口:List、Set。

3.1 List接口

  • ArrayList 采用数组结构存储,增加删除慢,查找快
  • Vector 与ArrayList类相似,但是是同步的
  • LinkedList 使用的是双向链表,增加删除更快,查找慢,与ArrayList相反

3.2 Set接口

  • HashSet Set接口下的常用类,散列存放(HashMap)
  • TreeSet 采用有序的二叉树存储,内部也是基于TreeMap,方法与HashSet类似
  • LinkedHashset

4. Map接口

  • HashMap 线程不安全,效率高
  • Hashtable 线程安全,效率低
  • ConcurrentHashMap 采取分段锁机制,保证线程安全,效率比较高
  • TreeMap 使用二叉树自动排序存储,HashMap不保证存储顺序
  • LinkedHashMap 既在哈希表中,又在双向链表中
    在这里插入图片描述
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/77269
推荐阅读
相关标签
  

闽ICP备14008679号