精华内容
下载资源
问答
  • 常见的数据结构有集合
    千次阅读
    2019-04-28 20:17:49

    常见的和集合相关的数据结构有: 数组, 栈, 队列,链表,哈希表, 二叉树

    下面简单总结一下个数据结构特点:

    1. 数组

    • ArrayList(public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable)
      底层数据结构是数组,所以数组有的特点,ArrayList都有,主要具有以下特点:
      1.有序,有索引
      2.元素可以重复
      3.可以存储null值
      4.随机访问速度快,修改快,增加/插入或者移除/删除的效率慢
      5.线程不安全
    • 主要方法:
      add(E e); addAll(Collection<? extends E> c)clear() contains(Object o)isEmpty()remove(int index)size()toArray()

    2.栈

    • stack
      储存数据特点为"先进后出",即最先存入栈的数据会进入栈低,而最后存入的数据会被最先取出;
    • 主要方法:
      empty() :测试此堆栈是否为空
      peek():查看此堆栈顶部的对象,而不从堆栈中删除它。
      pop() :删除此堆栈顶部的对象,并将该对象作为此函数的值返回。
      push(E item);将项目推送到此堆栈的顶部。
      search(Object o):返回一个对象在此堆栈上的基于1的位置。

    3.队列

    • 1.Queue(public interface Queue extends Collection)
      队列通常但不一定是以FIFO(先进先出)方式排序元素;无论使用什么顺序,队列的头都是通过调用remove()或poll()删除的元素。 在一个FIFO队列,所有新元素插入到队列的尾部 。
    • 主要方法
      add(E e) :将指定的元素插入到此队列中,如果可以立即执行此操作,而不会违反容量限制, true在成功后返回 IllegalStateException如果当前没有可用空间,则抛出IllegalStateException。
      element() :检索,但不删除,这个队列的头。
      offer(E e) :如果在不违反容量限制的情况下立即执行,则将指定的元素插入到此队列中。
      peek() :检索但不删除此队列的头,如果此队列为空,则返回 null 。
      poll() :检索并删除此队列的头,如果此队列为空,则返回 null 。
      remove() :检索并删除此队列的头。
    • 2.Deque ( public interface Deque extends Queue)
      支持两端元素插入和移除的线性集合, 名称deque是“双端队列”的缩写。
    • 主要方法
      addFirst(E e)
      插入此双端队列的前面,如果它是立即可行且不会违反容量限制,抛出一个指定的元素 IllegalStateException如果当前没有空间可用。
      addLast(E e)
      在插入如果它是立即可行且不会违反容量限制,抛出此双端队列的末尾指定元素 IllegalStateException如果当前没有空间可用。
      getFirst()
      检索,但不删除,这个deque的第一个元素。
      getLast()
      检索,但不删除,这个deque的最后一个元素。
      peekFirst()
      检索,但不删除,此deque的第一个元素,或返回 null如果这个deque是空的。
      peekLast()
      检索但不删除此deque的最后一个元素,如果此deque为空,则返回 null 。
      pollFirst() :
      检索并删除此deque的第一个元素,如果此deque为空,则返回 null 。
      pollLast() :
      检索并删除此deque的最后一个元素,如果此deque为空,则返回 null 。
      removeFirst() :
      检索并删除此deque的第一个元素。
      removeLast() :
      检索并删除此deque的最后一个元素。

    4.链表

    • LinkedListpublic class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
      特点
      1.底层数据结构是链表
      2.链表的特点有序,查询和修改效率低,增加和删除效率高
      3.可以存储null值
      4.线程不安全
      5.允许重复
      6.不可排序
      7.双链表实现了List和Deque接口。
    • 主要方法:
      void addFirst(E e) :
      将指定的元素追加到此列表的末尾。
      void addLast(E e)
      将指定的元素追加到此列表的末尾。
      E getFirst()
      返回此列表中的第一个元素。
      E getLast()
      返回此列表中的最后一个元素。
      E removeFirst() ;
      从此列表中删除并返回第一个元素。
      E removeLast() :
      从此列表中删除并返回最后一个元素。

    5.哈希表

    • HashSetpublic class HashSet extends AbstractSet implements Set, Cloneable, Serializable
      此类实现Set接口,由哈希表(实际为HashMap实例)支持
      特点:
      不允许null键和null值
      线程安全,效率低

    6.二叉树

    • TreeMappublic class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
      特点:
      键可排序,唯一,
      值有序,可重复,类似于List
      底层数据结构是自平衡的二叉树,可排序
      排序方式类似于TreeSet,分为自然排序和比较器排序,具体取决于使用的构造方法
    更多相关内容
  • 数据结构分类及八种常见数据结构

    千次阅读 2020-05-09 11:04:00
    1.集合数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系; 2.线性结构:数据结构中的元素存在一对一的相互关系; 3.树形结构:数据结构中的元素存在一对多的相互关系; 4.图形结构:数据结构...

    一.数据结构分类
    数据的逻辑结构
    1.集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
    2.线性结构:数据结构中的元素存在一对一的相互关系;
    3.树形结构:数据结构中的元素存在一对多的相互关系;
    4.图形结构:数据结构中的元素存在多对多的相互关系。

    数据的存储结构:
    顺序存储结构:数据元素在内存中的物理存储顺序与他们的逻辑顺序相同
    链式存储结构:使用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,数据元素之间的关系需要采用附加信息特别指定。c语言采用指针,Java采用引用指定。

    线性结构和非线性结构两类
    线性结构:最多只有一个直接前趋结点(第一个没有)和一个直接后继结点。栈、队列和串等都属于线性结构
    非线性结构:可能有多个直接前趋结点和多个直接后继结点,数组、广义表、树结构和图

    数据结构分类
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    在这里插入图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    二.八种常见数据结构
    1、数组
    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0] = 1;
    1
    2
    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈
    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    在这里插入图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列
    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    在这里插入图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表
    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    在这里插入图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树
    树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    每个节点有零个或多个子节点;
    没有父节点的节点称为根节点;
    每一个非根节点有且只有一个父节点;
    除了根节点外,每个子节点可以分为多个不相交的子树;
    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树。
    在这里插入图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    红黑树,是在JDK1.8之后在HashMap中数据结构的升级
    一种树结构如 98(节点:存贮着key,value)
    78 125
    51 89 118 169

    右边值大于中间值,中间值大于左边值,当条件查询查询key为125的值时,如果不加索引那么将进行6次磁盘I/O,如果添加索引将只要进行2次磁盘I/O.
    查询流程: 直接从key为98的值根元素开始查询(1次磁盘I/O),发现125大于98向右边查询找到125(2次磁盘I/O).
    不足:但如果数据量太大树的高度还是很高

    BTree(mysql)
    与红黑树一样但是在其每个节点中存储着多个key,value,当查询某条数据时会将这个节点所有的key,value都读取到内存中RAM,在RAM在找出对应的key(RAM中处理的非常快,时间可以忽略不计)
    78 118
    51 89 98 125 169
    78和118为一个节点,51为一个节点,89和98为一个节点,125和169为一个节点.
    当查询169时只有2次磁盘I/O,第一次磁盘I/O找到78个118,第二次磁盘I/O找到125和169这个节点,然后将这个节点读取到内存中处理.

    B+Tree
    B+Tree是BTree的改进版在节点与节点之间多了一个指针,只在树叶(树末梢)有value但这个value将不再是地址指针而是直接存放数据,上一个节点的key将遗留到下一个节点中.目的为了便于范围查询,如查询>98的记录,没有这个指针,需要重新从根节点找,没有这个遗留的节点,因为一次磁盘I/O不能读取太多数据
    78 118 (只有key)
    51 ->78 89 98 ->118 125 169 (都有key,data)

    存储引擎针对与表,一个数据库可以有两个不同存储引擎的表
    MyISAM (BTree)
    数据库文件下,data下的表文件夹中
    frm文件:存储的是建表结构,即查看表对象中的内容,create… 主外键
    MYD(MyISAM Data)文件:存储的是表中的数据
    MYI(MyISAM Index)文件:存储的是表中的key和数据地址指针(即BTree)
    当在数据库中查询时,如果发现有磁盘中有MYI文件(即添加了索引),会在索引中找到对应的节点,根据value的值(地址指针),去MYD文件中找到对应的地址

    InnoDB (B+Tree)
    数据库文件下,data下的表文件夹中
    frm文件:存储的是建表结构,即查看表对象中的内容,create… 主外键
    idb文件(index data):存储的是key和数据(B+Tree)

    非聚集索引,将索引与数据分开,即用MYI和MYD分开(MyISAM)
    聚集索引,将索引与数据结合在一起,即使用idb文件把索引与数据结合(InnoDB)

    mysql读取数据流程:cpu->RAM>磁盘
    页/4K(4*1024B(字节)) 一次磁盘I/O只能读取正数页,一次性不能读取太多数据,所以一个节点不能存放太多数据
    查看mysql文件页大小:show global status like ‘Innodb_page_size’ (官方默认16K)

    6、散列表
    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    在这里插入图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆
    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    堆中某个节点的值总是不大于或不小于其父节点的值;

    堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    在这里插入图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图
    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    在这里插入图片描述
    在这里插入图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    原文链接:https://blog.csdn.net/yeyazhishang/article/details/82353846

    展开全文
  • Java集合——数据结构

    千次阅读 2022-03-27 22:38:42
    Java集合——数据结构 https://blog.csdn.net/bj_chengrong/article/details/108667887 https://binhao.blog.csdn.net/article/details/113279914 https://www.cnblogs.com/paddix/p/5539326.html 1.集合简介 ​ ...

    Java集合——数据结构

    https://blog.csdn.net/bj_chengrong/article/details/108667887

    https://binhao.blog.csdn.net/article/details/113279914

    https://www.cnblogs.com/paddix/p/5539326.html

    1.集合简介

    ​ Java中集合类是Java编程中使用最频繁、最方便的类。集合类作为容器类可以存储任何类型的数据,当然也可以结合泛型存储指定的类型(不过泛型仅仅在编译期有效,运行时是会被擦除的)。集合类中存储的仅仅是对象的引用(堆地址,而非实际对象本身),并不存储对象本身。集合类的容量可以在运行期间进行动态扩展,并且还提供很多很方便的方法,如求集合的并集、交集等。

    注意:集合中不能添加基本数据类型,只能包含引用类型;部分基恩数据类型在添加过程中会自动装箱包装成类,再添加到集合中。

    2.集合类结构

    Java中的集合包含多种数据结构,如链表、队列、哈希表等。从类的继承结构来说,可以分为两大类:

    • 一类是继承自Collection接口,这类集合包含List、Set和Queue等集合类。

    • 一类是继承自Map接口,这主要包含了哈希表相关的集合类。

    image-20220327153148410

    2.1 Collection接口

    img

    (图中的绿色的虚线代表实现,绿色实线代表接口之间的继承,蓝色实线代表类之间的继承。)

    • Collection是根接口(接口要通过具体的类来实现,不能new接口)——代表一组任意类型的对象
      • List接口:有序、有下标、元素可重复
      • Set接口:无序、无下标、元素不能重复

    2.2.1 List接口

    List接口继承了Collection,因此其包含Collection中的所有方法。

    **特点:**有序、有下标、元素可以重复

    方法:
    • void add (int index,Object o) //在index位置插入对象o
    • boolean addAll (int index, Collection c) //将另一个集合中的所有元素插入到该集合的index位置
    • Object get (int index) //返回该集合中指定位置的元素
    • List subList (int fromIndex, int toIndex) //返回fromIndex和toIndex之间的集合元素构成的子集合
    实现类:
    • ArrayList【重点】

      • 数组结构,查询快、增删慢;(底层通过数组实现)
      • JDK1.2版本,运行效率快、线程不安全
    • Vector

      • 数组结构,查询快、增删慢;
      • JDK1.0版本,运行效率较快、线程安全
      • Stack类是继承的Vector类
    • LinkdedList

      • 链表结构,增删快、查询慢(底层通过链表实现)

    对比:

    1. ArrayList是最常用的List实现类,内部是通过数组实现的,它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。
    2. Vector与ArrayList一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList慢
    3. LinkedList是用链表结构存储数据的,很适合数据的动态插入和删除,随机访问和遍历速度比较慢。另外,他还提供了List接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆栈、队列和双向队列使用。
    4. Vector是线程(Thread)同步(Synchronized)的,所以它也是线程安全的,而Arraylist是线程异步(ASynchronized)的,是不安全的。如果不考虑到线程的安全因素,一般用Arraylist效率比较高
    5. 如果集合中的元素的数目大于目前集合数组的长度时,vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度
      的50%。如过在集合中使用数据量比较大的数据,使用Vector有一定的优势;若集合中数据量不大,使用ArrayList就有利于节约内存空间。
    • 注意各类集合的初始大小、载入因子等

    不同结构的实现方式:

    • ArrayList:数组结构
      • 必须开辟连续的空间
      • 查询快,增删慢
    • LinkedList:双向链表
      • 无需开辟连续的空间
      • 查询慢,增删快

    image-20220327142835784

    (1)ArrayList

    ArrayList是List接口最常用的一个实现类,支持List接口的一些列操作。

    package com.song.demo02;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.ListIterator;
    
    //ArrayList的使用
    //存储结构:数组-->查找遍历速度快,增删慢
    public class Demo03 {
        public static void main(String[] args) {
            //创建集合
            /**size=0 初始创建,容量为0;
             * 向集合中添加任意一个元素后,容量变为10
             * 后续添加的元素超过10,添加第11个元素时会继续扩容,容量变为15
             * 每次扩容,都是原来的1.5倍
             */
            ArrayList arrayList = new ArrayList<>();
            //1.添加元素
            Student s1 = new Student("zhangsan", 20);
            Student s2 = new Student("lisi", 22);
            Student s3 = new Student("wangwu", 18);
            arrayList.add(s1);
            arrayList.add(s2);
            arrayList.add(s3);
            arrayList.add(s2);
            System.out.println("元素个数:" + arrayList.size());
            System.out.println(arrayList.toString());
    
            //2.删除元素
            /*arrayList.remove(s1);
            arrayList.remove(new Student("wangwu", 18));//正常情况下不能删除,是一个新的对象,实际集合中存储的是对象的地址
            //删除过程中会调用到的equals(this==obj)方法,比较的是地址;如果要比较值,则需要重写equals()方法
            //重写equals方法后,可以删除
            System.out.println("删除之后元素个数:" + arrayList.size());
            System.out.println(arrayList.toString());
            */
    
            //3.遍历元素【重点】
            //3.1增强for
            //3.2使用for
            //3.3迭代器
            Iterator it = arrayList.iterator();
            while (it.hasNext()) {
                Student s = (Student) it.next();
                System.out.println(s.toString());
            }
            //3.4使用列表迭代器
            System.out.println("------------从前往后------");
            ListIterator lit = arrayList.listIterator();
            while (lit.hasNext()) {
                Student s = (Student) lit.next();
                System.out.println(s.toString());
            }
            System.out.println("------------从后往前------");
            while (lit.hasPrevious()) {
                Student s = (Student) lit.previous();
                System.out.println(s.toString());
            }
    
            //4.判断
            System.out.println("元素是否存在:" + arrayList.contains(new Student("wangwu", 18)));//equals重写后可以根据对象值判断是否存在
            System.out.println("集合是否为空:" + arrayList.isEmpty());
    
            //5.查找元素位置
            System.out.println(arrayList.indexOf(new Student("wangwu", 18)));//equals重写后可以根据对象值查找位置
        }
    }
    
    
    (2)Vector
    package com.song.demo02;
    
    import java.util.Enumeration;
    import java.util.Vector;
    
    //Vector的使用
    //存储结构:数组
    public class Demo04 {
        public static void main(String[] args) {
            //创建集合
            Vector vector = new Vector<>();
            //1.添加元素
            vector.add("草莓");
            vector.add("芒果");
            vector.add("西瓜");
            System.out.println("元素个数:" + vector.size());
            System.out.println(vector.toString());
            //2.删除
            /*vector.remove(0);//根据下标删除
            vector.remove("芒果");
            vector.clear();//清空
            System.out.println("元素个数:" + vector.size());
            System.out.println(vector.toString());
    
             */
            //3.遍历
            //3.1for
            //3.2增强for
            //3.3迭代器
            //3.4枚举器
            Enumeration en = vector.elements();
            while (en.hasMoreElements()) {
                String o = (String) en.nextElement();
                System.out.println(o);
            }
    
            //4.判断
            System.out.println("判断是否包含元素:" + vector.contains("西瓜"));
            System.out.println("判断是否为空:" + vector.isEmpty());
    
            //其他方法
            System.out.println("第一个位置的元素" + vector.firstElement());
            System.out.println("最后一个位置的元素" + vector.lastElement());
            System.out.println("获取指定位置的元素" + vector.elementAt(1));
    
        }
    }
    
    (3)LinkList

    LinkedList由一个头节点,一个尾节点和一个默认为0的size构成,可见其是双向链表。

    ​ LinkedList中Node源码如下,由当前值item,和指向上一个节点prev和指向下个节点next的指针组成。并且只含有一个构造方法,按照(prev, item, next)这样的参数顺序构造。

    package com.song.demo02;
    
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.ListIterator;
    
    //LinkedList的使用
    //存储结构:双向链表
    public class Demo05 {
        public static void main(String[] args) {
            //创建集合
            LinkedList list = new LinkedList<>();
            //1.添加元素
            Student s1 = new Student("张三", 21);
            Student s2 = new Student("李四", 24);
            Student s3 = new Student("王五", 20);
            list.add(s1);
            list.add(s2);
            list.add(s3);
            list.add(s2);//可以重复
            System.out.println("元素个数:" + list.size());
            System.out.println(list.toString());
    
            //2.删除
            /*list.remove(0);//根据下标删除
            list.remove(new Student("李四", 24));//重写equals()方法后,可以根据对象值删除
            list.clear();//清空
            System.out.println("删除之后元素个数:" + list.size());
            System.out.println(list.toString());
    
             */
    
            //3.遍历
            //3.1for遍历
            System.out.println("-----------------for遍历-----------------");
            for (int i = 0; i < list.size(); i++) {
                Student stu = (Student) list.get(i);
                System.out.println(stu.toString());
            }
            //3.2增强for
            System.out.println("-----------------增强for-----------------");
            for (Object obj : list) {
                Student stu = (Student) obj;
                System.out.println(stu.toString());
            }
            //3.3迭代器Iterator
            System.out.println("-----------------迭代器Iterator-----------------");
            Iterator it = list.iterator();
            while (it.hasNext()) {
                Student stu = (Student) it.next();
                System.out.println(stu.toString());
            }
            //3.4列表迭代器ListIterator
            System.out.println("-----------------列表迭代器ListIterator-----------------");
            ListIterator lit = list.listIterator();
            while (lit.hasNext()) {
                Student stu = (Student) lit.next();
                System.out.println(stu.toString());
            }
    
            //4.判断
            System.out.println("判断元素是否存在" + list.contains(s1));
            System.out.println("判断是否为空" + list.isEmpty());
            //5.获取
            System.out.println(list.indexOf(s2));//获取元素位置
    
        }
    }
    
    (4)Stack

    img

    ​ Stack也是List接口的实现类之一,和Vector一样,因为性能原因,更主要在开发过程中很少用到栈这种数据结构,不过栈在计算机底层是一种非常重要的数据结构。

    ​ Stack继承于Vector,其也是List接口的实现类。之前提到过Vector是线程安全的,因为其方法都是synchronized修饰的,故此处Stack从父类Vector继承而来的操作也是线程安全的

    栈主要操作为push入栈和pop出栈,而栈最大的特点就是LIFO(Last In First Out,先入后出)。

    Stack<String> strings = new Stack<>();
    strings.push("aaa");
    strings.push("bbb");
    strings.push("ccc");
    System.err.println(strings.pop());
    

    2.2.2 Set接口

    Set与List的主要区别是Set是不允许元素重复的,而List则可以允许元素重复的。判断元素的重复需要根据对象的hash方法和equals方法来决定。这也是我们通常要为集合中的元素类重写hashCode方法和equals方法的原因。

    实现类:
    • HashSet【重点】

      • 存储结构:Hash表

      • 基于HashCode计算元素存放位置

      • 当存入元素的哈希码相同时,会调用equals()进行确认,如果认为值true,则拒绝后者存入;如果为false,则形成链表添加到该位置。

    • TreeSet

      • 存储结构:红黑树
      • 基于排列顺序实现元素不重复
      • 实现了SortedSet接口,对集合元素自动排序
      • 元素对象的类型必须实现Comparable接口,指定排序规则。
      • 通过CompareTo方法确定是否为重复元素。
    (1)HashSet

    存储过程:

    1. 根据hashCode计算保存的位置(数组),如果位置为空,则直接保存,如果不为空则执行第二步
    2. 再执行equals方法,如果equals方法位true,则认为是重复,无需再次增加;否则形成链表,添加到该位置。
    • 既有数组又有链表

    实例一:

    package com.song.demo04;
    
    import java.util.HashSet;
    import java.util.Iterator;
    
    //HashSet的使用
    //存储结构:哈希表(数组+链表+红黑树)
    public class Demo02 {
        public static void main(String[] args) {
            //新建集合
            HashSet<String> hashSet = new HashSet<String>();
            //1.添加元素
            hashSet.add("张三");
            hashSet.add("李四");
            hashSet.add("王五");
            hashSet.add("宋六");
            System.out.println("元素个数:" + hashSet.size());
            System.out.println(hashSet.toString());
    
            //2.删除元素
            /*hashSet.remove("王五");
            hashSet.clear();//清空
            System.out.println("删除后元素个数:" + hashSet.size());
            System.out.println(hashSet.toString());
             */
    
            //3.遍历
            //3.1增强for
            System.out.println("-------------------增强for------------");
            for (String str : hashSet) {
                System.out.println(str);
            }
            //3.2迭代器
            System.out.println("-------------------迭代器------------");
            Iterator it = hashSet.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
    
            //4.判断
            System.out.println("判断元素是否存在:" + hashSet.contains("李四"));
            System.out.println("判断集合是否为空:" + hashSet.isEmpty());
            
        }
    }
    

    实例二:

    package com.song.demo04;
    
    import java.util.Objects;
    
    public class Person {
        private String name;
        private int age;
    
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        /*@Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null) {
                return false;
            }
            if (o instanceof Person) {
                Person person = (Person) o;
                if (age == person.age && name.equals(person.getName()))
                    return true;
            }
            return false;
    
        }
    
        @Override
        public int hashCode() {
            //根据名字、年龄来计算hashCode,可以让相同值的的hashCode一致(既数组的同一位置)
            int n1 = this.name.hashCode();
            int n2 = this.age;//可以直接用年龄的数字,也可以对其做一定的加减等操作
            //int n2 = this.age+31;//
            //1)31是一个质数,减少散列冲突;2)31提高执行效率
            return n1 + n2;
        }
    
         */
        //Alt+Insert 中有快速重写equals和hashCode的方法
    
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return age == person.age && Objects.equals(name, person.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
    }
    
    package com.song.demo04;
    
    import java.util.HashSet;
    import java.util.Iterator;
    
    //HashSet的使用
    //存储结构:哈希表(数组+链表+红黑树)
    
    /**
     * 存储过程:
     * (1)根据hashCode计算保存的位置(数组),如果位置为空,则直接保存,如果不为空则执行第二步
     * (2)再执行equals方法,如果equals方法位true,则认为是重复,否则形成链表
     * (3)
     */
    public class Demo03 {
        public static void main(String[] args) {
            //创建集合
            HashSet<Person> person = new HashSet<>();
            //1.添加元素
            Person p1 = new Person("张三", 18);
            Person p2 = new Person("李四", 26);
            Person p3 = new Person("王五", 28);
            Person p4 = new Person("宋六", 20);
            person.add(p1);
            person.add(p2);
            person.add(p3);
            person.add(p4);
            //person.add(p4);//重复,不能再添加
            person.add(new Person("宋六", 20));//可以添加,new了一个新的对象,地址不同,计算出的hashCode不同,可以直接存储
            /**想根据值判断,则:
             * 1)首先需重写hashCode()方法,让值相同的计算出的hashCode一样(数组的相同位置)---此时用equals判断地址,会形成链表
             * 2)再重写equals方法,根据值判断是否一致,而非根据地址判断
             */
            System.out.println("元素个数:" + person.size());
            System.out.println(person.toString());
    
            //2.删除元素
            person.remove(p1);
            person.remove(new Person("宋六", 20));//重写hashCode和equals后可以删除
            System.out.println("删除之后元素个数:" + person.size());
            System.out.println(person.toString());
    
            //3.遍历元素
            //3.1增强for
            for (Person p : person) {
                System.out.println(p.toString());
            }
            System.out.println("-------------");
            //3.2迭代器
            Iterator it = person.iterator();
            while (it.hasNext()) {
                System.out.println(it.next().toString());
            }
    
            //4.判断
            System.out.println("元素是否存在" + person.contains(p2));
            System.out.println("元素是否存在" + person.contains(new Person("李四", 26)));//重写hashCode和equals后可以根据值判断
            System.out.println("集合是否为空" + person.isEmpty());
    
    
        }
    }
    
    (2)TreeSet
    • 存储结构:红黑树
    • 基于排列顺序实现元素不重复
    • 实现了SortedSet接口,对集合元素自动排序
    • 元素对象的类型必须实现Comparable接口,指定排序规则。
    • 通过CompareTo方法确定是否为重复元素。

    ​ 红黑树是一个二叉查找树(每个节点最多只有2个子节点,且左节点小于右节点,涉及到比较)+颜色(保证左右平衡)

    实例一:

    package com.song.demo04;
    //TreeSet的使用
    //存储结构:红黑树
    
    import java.util.Iterator;
    import java.util.TreeSet;
    
    public class Demo04 {
        public static void main(String[] args) {
            //创建集合
            TreeSet<String> treeset = new TreeSet<>();
            //1.添加元素
            treeset.add("xyz");
            treeset.add("abc");
            treeset.add("hello");
            treeset.add("song");
            treeset.add("xyz");//重复,未添加
            System.out.println("元素个数:" + treeset.size());
            System.out.println(treeset.toString());//打印出的是按照字母表顺序排列的
    
            //2.删除
            treeset.remove("xyz");
            System.out.println("元素个数:" + treeset.size());
            System.out.println(treeset.toString());
    
            //3.遍历
            //3.1增强for
            for (String str : treeset) {
                System.out.println(str);
            }
            System.out.println("-------------------------");
            //3.2迭代器
            Iterator it = treeset.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
    
            //4.判断
            System.out.println("元素是否存在:" + treeset.contains("abc"));
            System.out.println("集合是否为空:" + treeset.isEmpty());
    
    
        }
    }
    

    实例二:

    package com.song.demo04;
    
    import java.util.Iterator;
    import java.util.TreeSet;
    
    //TreeSet的使用
    //存储结构:红黑树
    
    /**
     * 要求:元素必须实现Comparable接口,compareTo()方法返回值为0,被认为是重复元素
     */
    
    public class Demo05 {
        public static void main(String[] args) {
            //1.创建集合
            TreeSet<Person> person = new TreeSet<>();
            //1.添加元素
            Person p1 = new Person("zhangsan", 18);
            Person p2 = new Person("lisi", 26);
            Person p3 = new Person("wangwu", 28);
            Person p4 = new Person("lisi", 20);
            //直接添加不成功,不知道如何把比较(二叉查找树要求左节点<右节点)
            //需要实现Comparable接口,重写compareTo方法,告知比较规则
            person.add(p1);
            person.add(p2);
            person.add(p3);
            person.add(p4);
            System.out.println("元素个数:" + person.size());
            System.out.println(person.toString());//按照排序输出,先姓名后年龄,可自定义
    
            //2.删除
            /*person.remove(p1);
            person.remove(new Person("lisi", 20));//实现Comparable接口之后,比较值,可以删除
            System.out.println("删除之后元素个数:" + person.size());
            System.out.println(person.toString());//按照排序输出,先姓名后年龄,可自定义
    */
            //3.遍历
            //3.1使用增强for
            for (Person p : person) {
                System.out.println(p.toString());
            }
            System.out.println("---------------------");
            //3.2使用迭代器
            Iterator it = person.iterator();
            while (it.hasNext()) {
                System.out.println(it.next().toString());
            }
    
            //4.判断
            System.out.println(person.contains(p2));
            System.out.println(person.contains(new Person("lisi", 20)));//可以判断
    
        }
    }
    

    实例三:

    package com.song.demo04;
    
    import java.util.Comparator;
    import java.util.TreeSet;
    
    //TreeSet集合的使用
    //Comparator接口:实现定制比较(比较器)
    //Comparable:可比较的
    public class Demo06 {
        public static void main(String[] args) {
            //创建集合,并指定比较规则——采用匿名内部类的方式
            TreeSet<Person> person = new TreeSet<>(new Comparator<Person>() {
                @Override
                public int compare(Person o1, Person o2) {//拿两个对象定制比较规则
                    int n1 = o1.getAge() - o2.getAge();
                    int n2 = o1.getName().compareTo(o2.getName());
                    return n1 == 0 ? n2 : n1;//先比较年龄再比较性别
                }
            });
            //1.添加元素
            Person p1 = new Person("zhangsan", 18);
            Person p2 = new Person("lisi", 26);
            Person p3 = new Person("wangwu", 28);
            Person p4 = new Person("lisi", 20);
            person.add(p1);
            person.add(p2);
            person.add(p3);
            person.add(p4);
            System.out.println("元素个数:" + person.size());
            System.out.println(person.toString());//按照排序输出,先姓名后年龄,可自定义
    
    
        }
    }
    

    实例四:

    package com.song.demo04;
    
    import java.util.Comparator;
    import java.util.TreeSet;
    
    //要求:使用TreeSet集合实现字符串按照长度进行排序(最短的在前面,长度一样再根据字母顺序比较)
    //使用Comparatar接口定制比较
    public class Demo07 {
        public static void main(String[] args) {
            //创建集合
            TreeSet<String> treeSet = new TreeSet<>(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    int n1 = o1.length() - o2.length();
                    int n2 = o1.compareTo(o2);
                    return n1 == 0 ? n2 : n1;
                }
            });
            //1.添加元素
            treeSet.add("hello world");
            treeSet.add("abc");
            treeSet.add("xyz");
            treeSet.add("Beijing");
            treeSet.add("zhangsang");
            treeSet.add("lisi");
            System.out.println(treeSet.size());
            System.out.println(treeSet.toString());
    
        }
    }
    

    2.2.3 Queue接口

    Queue接口

    正如数据结构中描述,queue是一种先进先出的数据结构,也就是first in first out。可以将queue看作一个只可以从某一段放元素进去的一个容器,取元素只能从另一端取,整个机制如下图所示,不过需要注意的是,队列并没有规定是从哪一端插入,从哪一段取出。

    队列工作机制

    一般可以直接使用LinkedList完成,从上述类图也可以看出,LinkedList继承自Deque,所以LinkedList具有双端队列的功能。PriorityQueue的特点是为每个元素提供一个优先级,优先级高的元素会优先出队列。

    注意:Java中的队列明确有从尾部插入,头部取出,所以Java中queue的实现都是从头部取出

    Deque接口

    ​ Deque英文全称是Double ended queue,也就是俗称的双端队列。就是说对于这个队列容器,既可以从头部插入也可以从尾部插入,既可以从头部获取,也可以从尾部获取,其机制如下图所示。
    Deque工作原理

    Queue,Deque的实现类:

    ​ Java中关于Queue的实现主要用的是双端队列,毕竟操作更加方便自由,Queue的实现有PriorityQueueDeque在java.util中主要有ArrayDeque和LinkedList两个实现类,两者一个是基于数组的实现,一个是基于链表的实现。在之前LinkedList文章中也提到过其是一个双向链表,在此基础之上实现了Deque接口。

    (1)PriorityQueue

    ​ PriorityQueue是Java中唯一一个Queue接口的直接实现,如其名字所示,优先队列,其内部支持按照一定的规则对内部元素进行排序。

    img

    ​ 先看下PriorityQueue的继承实现关系,可知其是Queue的实现类,主要使用方式是队列的基本操作,而之前讲到过Queue的基本原理,其核心是FIFO(First In First Out)原理。
    ​ Java中的PriorityQueue的实现也是符合队列的方式,不过又略有不同,区别就在于PriorityQueue的priority上,其是一个支持优先级的队列,当使用了其priority的特性的时候,则并非FIFO。

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    queue.add(20);queue.add(14);queue.add(21);queue.add(8);queue.add(9);
    queue.add(11);queue.add(13);queue.add(10);queue.add(12);queue.add(15);
    while (queue.size()>0){
        Integer poll = queue.poll();
        System.err.print(poll+"->");
    }
    
    

    上述代码做的事为往队列中放入10个int值,然后使用Queue的poll()方法依次取出,最后结果为每次取出来都是队列中最小的值,说明了PriorityQueue内部确实是有一定顺序规则的。

    PriorityQueue的组成很简单,主要记住一个存放元素的数组,和一个Comparator比较器即可。

    (2)ArrayDeque

    ArrayDeque是Java中基于数组实现的双端队列.

    img

    ArrayDeque<String> deque = new ArrayDeque<>();
    deque.offer("aaa");
    deque.offer("bbb");
    deque.offer("ccc");
    deque.offer("ddd");
    //peek方法只获取不移除
    System.err.println(deque.peekFirst());
    System.err.println(deque.peekLast());
    
    
    ArrayDeque<String> deque = new ArrayDeque<>();
    deque.offerFirst("aaa");
    deque.offerLast("bbb");
    deque.offerFirst("ccc");
    deque.offerLast("ddd");
    String a;
    while((a = deque.pollLast())!=null){
        System.err.print(a+"->");
    }
    
    

    2.2 Map接口

    121212

    **特点:**存储一对数据(Key-Value),无序、无下标,键不可重复,值可以重复。

    • 键不允许重复(唯一),无序,无下标,不允许重复
    • 值允许重复,无序,无下标

    实现类

    • HashMap【重点】

      • JDK1.2版本,线程不安全(只能单线程下使用),运行效率快;允许用null作为key或者value。
    • HashTable

      • JDK1.0版本,线程安全,运行效率慢;不允许null作为key或者value
    • Properties:

      • HashTable的子类,要求key和value都是String。通常用于配置文件的读取。
    • TreeMap

      • 实现了SortedMap接口(是Map的子接口),可以对key自动排序
    (1)HashMap

    HashSet与HashMap的区别:

    HashSet里面本质用的就是HashMap

    实例:

    package com.song.demo05;
    
    import java.util.Objects;
    
    public class Student {
        private String name;
        private int stuNo;
    
        public Student() {
        }
    
        public Student(String name, int stuNo) {
            this.name = name;
            this.stuNo = stuNo;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getStuNo() {
            return stuNo;
        }
    
        public void setStuNo(int stuNo) {
            this.stuNo = stuNo;
        }
    
        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", stuNo=" + stuNo +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return stuNo == student.stuNo && Objects.equals(name, student.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, stuNo);
        }
    }
    
    
    package com.song.demo05;
    
    
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * HashMap的使用:
     * 存储结构:哈希表(数组+链表+红黑树)
     * <p>
     * 元素增加时重复的判断依据:
     * 使用key的hashcode和equals作为重复依据(默认用得是地址比较)
     * 要想根据值比较,需要重写hashcode和equals
     */
    public class Demo02 {
        public static void main(String[] args) {
            //创建集合
            HashMap<Student, String> hashmap = new HashMap<Student, String>();
    
            //1.增加元素
            Student s1 = new Student("张三", 213);
            Student s2 = new Student("李四", 104);
            Student s3 = new Student("王五", 890);
            Student s4 = new Student("六六", 432);
            hashmap.put(s1, "北京");
            hashmap.put(s2, "上海");
            hashmap.put(s3, "南京");
            hashmap.put(s4, "青岛");
            //hashmap.put(s4, "大同");//不允许key重复,不能添加新的键值对,只会覆盖原来的value
            hashmap.put(new Student("李四", 104), "杭州");//可以添加新的键值对,比较的是地址,认为key不同,故新增
            //当重写hashcode和equals 方法后,比较的是值认为key重复,不能新增键值对,会覆盖原来的value
            System.out.println("元素个数:" + hashmap.size());
            System.out.println(hashmap.toString());
    
            //2.删除元素
            hashmap.remove(s1);
            System.out.println("删除之后元素个数:" + hashmap.size());
            System.out.println(hashmap.toString());
    
            //3.遍历
            //3.1使用keySet
            for (Student stu : hashmap.keySet()) {
                System.out.println(stu.toString() + "----->" + hashmap.get(stu));
            }
            System.out.println("------------------------");
            //3.2使用entrySet
            for (Map.Entry<Student, String> entry : hashmap.entrySet()) {
                System.out.println(entry.getKey() + "------" + entry.getValue());
            }
    
            //4.判断
            System.out.println("Key是否存在:" + hashmap.containsKey(s2));
            System.out.println("value是否存在:" + hashmap.containsValue("杭州"));
        }
    }
    
    (2)TreeMap

    TreeSet与TreeMap的区别:

    TreeSet本质就是通过TreeMap实现的。

    实例:

    package com.song.demo05;
    
    import java.util.Objects;
    
    public class Student implements Comparable<Student> {
    
        private String name;
        private int stuNo;
    
        public Student() {
        }
    
        public Student(String name, int stuNo) {
            this.name = name;
            this.stuNo = stuNo;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getStuNo() {
            return stuNo;
        }
    
        public void setStuNo(int stuNo) {
            this.stuNo = stuNo;
        }
    
        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", stuNo=" + stuNo +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return stuNo == student.stuNo && Objects.equals(name, student.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, stuNo);
        }
    
        @Override
        public int compareTo(Student o) {
            int n2 = this.stuNo - o.stuNo;
            return n2;//直接比较学号
        }
    }
    
    

    1)实现Comparable接口实现比较

    package com.song.demo05;
    
    import java.util.Map;
    import java.util.TreeMap;
    
    /**
     * TreeMap的使用
     * 存储结构:红黑树(左节点<右节点)
     * 两种比较方式:
     * 1)实现Comparable接口
     * 2)定制比较Comparator
     */
    public class Demo03 {
        public static void main(String[] args) {
            //新建集合
            TreeMap<Student, String> treemap = new TreeMap<>();
            //1.增加元素
            Student s1 = new Student("张三", 213);
            Student s2 = new Student("李四", 104);
            Student s3 = new Student("王五", 890);
            Student s4 = new Student("六六", 432);
            treemap.put(s1, "北京");
            treemap.put(s2, "上海");
            treemap.put(s3, "南京");
            treemap.put(s4, "青岛");
            //直接添加出现类型转换异常,不能Comparable,不能比较左右节点
            //要求Student实现一个Comparable接口,指定比较规则,实现可比较,才能添加
            treemap.put(new Student("六六", 432), "深圳");//不能添加,实现Comparable接口后制定了按照学号比较,此时学号一样,则认为key重复,故value会覆盖原来的值
            System.out.println("元素个数:" + treemap.size());
            System.out.println(treemap.toString());
    
            //2.删除
            treemap.remove(s3);
            treemap.remove(new Student("六六", 432));//按照学号比较,可以删除
            System.out.println("元素个数:" + treemap.size());
            System.out.println(treemap.toString());
    
            //3.遍历
            //3.1使用keySet
            for (Student stu : treemap.keySet()) {
                System.out.println(stu.toString() + "----" + treemap.get(stu));
            }
            System.out.println("----------------------------------");
            //3.2使用entrySet
            for (Map.Entry<Student, String> entry : treemap.entrySet()) {
                System.out.println(entry.getKey() + "-----" + entry.getKey());
            }
    
            //4.判断
            System.out.println(treemap.containsKey(s2));
            System.out.println(treemap.containsValue(213));
    
    
        }
    }
    

    2)通过Comparator实现定制比较

            //新建集合
            TreeMap<Student, String> treemap = new TreeMap<Student, String>(new Comparator<Student>() {
                @Override
                public int compare(Student o1, Student o2) {
                    int n1 = o1.getStuNo() - o2.getStuNo();
                    return n1;//只根据学号比较
                }
            });
    

    3.Collections工具类

    • 概念:集合工具类,定义除了存取以外的集合常用方法。
    • (相比Collection,多了一个s)
    • 方法:

    image-20220114154513708

    实例:

    package com.song.demo05;
    
    import java.util.*;
    
    /**
     * Collection工具类的使用
     */
    public class Demo05 {
        public static void main(String[] args) {
            List<Integer> list = new ArrayList<>();
            list.add(20);
            list.add(25);
            list.add(39);
            list.add(11);
            list.add(22);
            list.add(40);
            list.add(18);
            System.out.println("排序之前" + list.toString());
            //sort排序方法
            Collections.sort(list);//从小到大
            System.out.println("排序之后" + list.toString());
    
            //binarySearch二分查找
            int i = Collections.binarySearch(list, 39);//返回值是int类型,能找到则返回位置,未找到则返回值小于0
            System.out.println(i);
    
            //copy复制
            List<Integer> dest = new ArrayList<>();
            //Collections.copy(dest, list);//直接copy有问题,要求dest的大小与list相同
            for (int i1 = 0; i1 < list.size(); i1++) {
                dest.add(0);
            }
            Collections.copy(dest, list);//可以先给dest赋值0,使两个列表size一致,再赋值
            System.out.println(dest.toString());
    
            //reverse反转
            Collections.reverse(list);
            System.out.println(list.toString());
    
            //shuffle打乱
            Collections.shuffle(list);
            System.out.println(list.toString());
    
            //补充:list转成数组
            System.out.println("list转成数组");
            Integer[] array = list.toArray(new Integer[0]);//返回值是数组;构造时new的Interger长度无所谓,只是为了指明一种类型
            System.out.println(array.length);
            System.out.println(Arrays.toString(array));
    
            //补充:数组转成集合
            System.out.println("数组转成集合");
            String[] name = {"张三", "李四", "王五", "刘六"};
            List<String> list2 = Arrays.asList(name);
            //数组转出来的集合是受限集合,不能添加和删除元素,不能add和remove
            System.out.println(list2.size());
            System.out.println(list2.toString());
    
            //把基本类型的数组转成集合是,需要修改为包装类型(引用类型)
            Integer[] nums = {12, 4, 2, 1, 44, 456, 34};
            List<Integer> list3 = Arrays.asList(nums);
            System.out.println(list3.size());
    
        }
    }
    
    

    4.泛型和工具类

    • Java泛型是JKD1.5中引入的新特性,其本质是参数化类型,把类型作为参数传递

    • 常见形式有:

      • 泛型类、
      • 泛型接口、
      • 泛型方法。
    • 语法:

      • <T,…>T称为类型占位符,表示一种引用类型
    • 好处:

      • 提高代码的重用性—一个方法可以传递任何类型的数据
      • 防止类型转换异常,提高代码的安全性

    4.1泛型类

    package com.song.demo03;
    
    public class TestGeneric {
        public static void main(String[] args) {
            //使用泛型类创建对象---
            /* 注意:
            1)T只能是引用类型
            2)不同的泛型对象之间不能相互复制
             */
            //String类型
            MyGeneric<String> myGeneric = new MyGeneric<String>();
            myGeneric.t = "hello";
            myGeneric.show("大家好!");
            String str = myGeneric.getT();
            System.out.println(str);
    
            //Integer
            MyGeneric<Integer> myGeneric1 = new MyGeneric<>();
            myGeneric1.t = 108;
            myGeneric1.show(200);
            Integer integer = myGeneric1.getT();
            System.out.println(integer);
    
    
        }
    }
    

    4.2泛型接口

    接口:

    package com.song.demo03;
    //泛型接口
    //语法:接口名<T>
    //注意:不能使用泛型创建静态常量
    public interface MyInterface<T> {
        String name="张三";
    
        T server(T t);
    }
    

    实现类一(实现接口时确定类型):

    package com.song.demo03;
    
    //接口的实现类,指明了泛型的类型
    public class MyInterfaceImpl implements MyInterface<String> {
        @Override
        public String server(String s) {
            System.out.println(s);
            return s;
        }
    }
    

    实现类二(实现接口时不确定类型):

    package com.song.demo03;
    
    //实现类实现接口时不确定类型,实现类的泛型就是接口的泛型
    public class MyInterfaceImpl2<T> implements MyInterface<T> {
        @Override
        public T server(T t) {
            System.out.println(t);
            return t;
        }
    }
    

    测试:

    package com.song.demo03;
    
    public class TestGeneric {
        public static void main(String[] args) {
            //泛型接口的两种实现方式
            //1.实现类中指定类型
            MyInterfaceImpl myInterface = new MyInterfaceImpl();
            myInterface.server("songsong");
    
            //2.把实现类变为泛型类,实例化时指定类型
            MyInterfaceImpl2<Integer> myInterfaceImpl2 = new MyInterfaceImpl2<Integer>();
            myInterfaceImpl2.server(1000);
    
    
        }
    }
    
    

    4.3泛型方法

    package com.song.demo03;
    
    //泛型方法
    //语法:<T> 返回值类型 方法名(){}
    public class MyGenericMethod {
        //泛型方法,该T只能在此方法中使用
        public <T> void show(T t) {
            T t2;//可以创建变量,但不能实例化(new)
            t2 = t;
            System.out.println("泛型方法:" + t);
        }
    
    }
    
    package com.song.demo03;
    
    public class TestGeneric {
        public static void main(String[] args) {
            //泛型方法
            MyGenericMethod myGenericMethod = new MyGenericMethod();
            myGenericMethod.show("中国加油");//不需要指明类型,直接传递想要的参数,根据参数类型决定
            myGenericMethod.show(200);
            myGenericMethod.show(3.1415926);
    
        }
    }
    

    4.4泛型集合

    • 概念:参数化类型、类型安全的集合,强制集合元素的类型必须一致。
    • 特点:
      • 编译时即可检查,而非运行时抛出异常
      • 访问时,不必类型转换(拆箱)
      • 不同泛型之间不能相互赋值,泛型不存在多态。
    package com.song.demo03;
    
    import com.song.demo02.Student;
    import com.sun.org.apache.xerces.internal.impl.xpath.XPath;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    
    public class Demo01 {
        public static void main(String[] args) {
            /*ArrayList arrayList=new ArrayList<>();
            arrayList.add("wangwu");
            arrayList.add("zhangsan");
            arrayList.add(0);
            arrayList.add(20);
    
            for (Object obj:arrayList             ) {
                System.out.println(obj);//没问题
                String str=(String)obj;
                //System.out.println(str);//有问题,类型转换异常
            }*
    
             */
    
            //使用泛型集合可以避免类型转换异常
            ArrayList<String> arrayList = new ArrayList<String>();
            arrayList.add("wangwu");
            arrayList.add("zhangsan");
            //arrayList.add(20);//直接不能添加,报错,避免后面再出问题
    
            for (String str : arrayList) {
                System.out.println(str);
            }
    
            ArrayList<Student> arrayList1 = new ArrayList<Student>();
            Student s1 = new Student("张三", 21);
            Student s2 = new Student("李四", 24);
            Student s3 = new Student("王五", 20);
            arrayList1.add(s1);
            arrayList1.add(s2);
            arrayList1.add(s3);
            //arrayList1.add("zhangsan");//直接不能添加,报错,避免后面再出问题
            Iterator<Student> it = arrayList1.iterator();
            while (it.hasNext()) {
                Student stu = it.next();//少了一步强制类型转换
                System.out.println(stu.toString());
            }
        }
    }
    
    展开全文
  • 【数据结构】八种常见数据结构介绍

    万次阅读 多人点赞 2021-02-05 13:59:44
    数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见数据结构

    相似文章推荐:


    零. 总览

    数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构。
    在这里插入图片描述

    一. 数组

    数组是一种线性结构,而且在物理内存中也占据着一块连续空间。

    • 优点:访问数据简单。
    • 缺点:添加和删除数据比较耗时间。
    • 使用场景:频繁查询,对存储空间要求不大,很少增加和删除的情况。

    数据访问:由于数据是存储在连续空间内,所以每个数据的内存地址都是通过数据小标算出,所以可以直接访问目标数据。(这叫做“随机访问”)。比如下方,可以直接使用a[2]访问Red。
    在这里插入图片描述
    数据添加:数据添加需要移动其他数据。首先增加足够的空间,然后把已有的数据一个个移开。
    在这里插入图片描述
    在这里插入图片描述
    数据删除:反过来,如果想要输出数据Green,也是一样挨个把数据往反方向移动。
    在这里插入图片描述
    在这里插入图片描述

    二. 链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。

    • 优点:数据添加和删除方便
    • 缺点:访问比较耗费时间
    • 适用场景:数据量较小,需要频繁增加,删除操作的场景

    数组和链表数据结构对比列表如下:
    在这里插入图片描述

    数据访问:因为数据都是分散存储的,所以想要访问数据,只能从第一个数据开始,顺着指针的指向逐一往下访问。
    在这里插入图片描述

    数据添加:将Blue的指针指向的位置变成Green,然后再把Green的指针指向Yellow。
    在这里插入图片描述
    数据删除:只要改变指针的指向就可以了,比如删除Yellow,只需把Green指针指向的位置从Yellow编程Red即可。

    虽然Yellow本身还存储在内存中,但是不管从哪里都无法访问这个数据,所以也就没有特意去删除它的必要了。今后需要用到Yellow所在的存储空间时,只要用新数据覆盖掉就可以了。
    在这里插入图片描述

    三. 栈

    栈也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新添加的数
    据。从栈顶放入元素的操作叫入栈,取出元素叫出栈。

    特点:后进先出(Last In First Out,简称LIFO)

    在这里插入图片描述
    在这里插入图片描述

    四. 队列

    队列中的添加和删除数据的操作分别是在两端进行的。队列可以在一端添加元素,在另一端取出元素,也就是:先进先出(First In First Out,简称FIFO)
    在这里插入图片描述
    在这里插入图片描述

    五. 哈希表

    哈希表,也叫散列表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。例如,下列键(key)为人名,value为性别。

    一般来说,我们可以把键当作数据的标识符,把值当作数据的内容。
    在这里插入图片描述

    • 数据存储

    假设我们需要存储5个元素,首先使用哈希函数(Hash)计算Joe的键,也就是字符串"Joe"的哈希值,得到4928,然后将哈希值除以数组长度5(mod运算),求得其余数。因此,我们将Joe的数据存进数组的3号箱子中。
    在这里插入图片描述

    • 冲突

    如果两个哈希值取余的结果相同,我们称这种情况为“冲突”。假设Nell键的哈希值为6276,mod 5的结果为1。但此时1号箱已经存储了Sue的数据,可使用链表在已有的数据的后面继续存储新的数据。
    在这里插入图片描述

    • 查询

    假设最终的哈希表为:
    在这里插入图片描述
    如果要查找Ally的性别,首先算出Alley键的哈希值,然后对它进行mod运算。最终结果为3。
    在这里插入图片描述
    然而3号箱中数据的键是Joe而不是Ally。此时便需要对Joe所在的链表进行线性查找。找到了键为Ally的数据。取出其对应的值,便知道了Ally的性别为女(F)。
    在这里插入图片描述

    • 特点

    可以利用哈希函数快速访问到数组的目标数据。如果发生哈希冲突,就使用链表进行存储。

    如果数组的空间太小,使用哈希表的时候就容易发生冲突,线性查找的使用频率也会更高;反过来,如果数组的空间太大,就会出现很多空箱子,造成内存的浪费。因此,给数组设定合适的空间非常重要。

    在存储数据的过程中,如果发生冲突,可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。除了链地址法以外,还有几种解决冲突的方法。其中,应用较为广泛的是“开放地址法”。

    六. 堆

    堆是一种图的树形结构,被用于实现“优先队列”(priority queues)。优先队列是一种数据结构,可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点”(node),数据就存储在这些结点中。堆有下列特点:

    • 每个节点最多有两个子节点
    • 排列顺序必须从上到下,同一行从左到右
    • 堆中某个节点的值总是不大于或不小于其父节点的值;
    • 存放数据时,一般会把新数据放在最下面一行靠左的位置。如果最下面一行没有多余空间时,就再往下另起一行,并把数据添加到这一行的最左端。

    堆的性质:

    • 堆是一个完全二叉树
    • 堆中某个结点的值总是不大于或不小于其父结点的值;
    • 将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
    • 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树
    • 一棵深度为 k k k且有 2 k − 1 2^k - 1 2k1个结点的二叉树称为满二叉树。也就是说除了叶子节点都有2个子节点,且所有的叶子节点都在同一层。

    在这里插入图片描述

    七. 树

    它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树。二叉树是树的特殊一种,具有如下特点:

    • 每个结点最多有两颗子结点
    • 左子树和右子树是有顺序的,次序不能颠倒
    • 即使某结点只有一个子树,也要区分左右子树

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构在二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    八. 图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。按照顶点指向的方向可分为无向图和有向图

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述


    参考:《我的第一本算法书》

    展开全文
  • 数据结构可以从两个方面分析:逻辑结构与物理结构...数据结构是指相互之间存在一种或多种特定关系的数据元素的集合数据结构与算法的关系: 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一.
  • 九大常见数据结构

    千次阅读 多人点赞 2020-10-16 14:44:54
    数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。 常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的...
  • 数据结构:八大常见数据结构

    千次阅读 2019-11-26 14:42:39
    数据结构是指,相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。常用的数据结构有:数组、栈、队列、链表、树、散列表、堆、图。 一、结构分类: 数据结构大多是以三种分类...
  • golang常见数据结构实现 链表,可变数组,栈和队列,字典Map和集合Set
  • 最近在学习数据结构必要对自己这两天的学习做一个总结,今天就来总结下,数据结构的逻辑结构 按照分类标准的不同,我们把数据结构分为逻辑机构和存储结构,今天主要讲解逻辑结构 逻辑结构:是指数据对象中的...
  • 常见数据结构有哪些?

    千次阅读 2020-06-09 19:01:16
    1.一共八大数据结构分类 1.数组 2.队列 3.链表 i.单链表 ii.双向链表 iii.循环链表 4.树 5.散列表 6.堆 7.栈 8.图 辅助理解 1、详细说下几个数据结构 数组 简单 栈 先进后出 队列 先进先出 链表 ...
  • 这份代码用 C++ 的模板类实现了一个集合类 Set,其 API 参考借鉴了 STL 中的 vector 类,采用动态内存及链表进行元素管理,并实现了一些常见集合算法:并集、交集,也实现了随机下标的存取。
  • JavaScript中的常见数据结构

    千次阅读 2021-09-27 12:31:30
    JavaScript中的常见数据结构 队列 栈 链表 集合 树 堆
  • 数据结构面试常见问题

    千次阅读 多人点赞 2021-01-04 16:00:05
    目录一、绪论二、线性表三、栈和队列四、串、数组和广义表五、树和二叉树六、图七...1.最小生成树的算法哪些?说明一下它们的时间复杂度以及各自的特点。 普里姆(Prim)算法 克鲁斯卡尔(Kruskal)算法 原理 Pr
  • 数据结构有什么用? 常见数据结构 栈 队列 数组 链表 红黑树
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据...
  • java常用数据结构有哪些

    千次阅读 2022-03-31 14:04:18
    Java常见数据结构 这 8 种数据结构什么区别呢? ①、数组 优点: 按照索引查询元素的速度很快; 按照索引遍历数组也很方便。 缺点: 数组的大小在创建后就确定了,无法扩容; 数组只能存储一.
  • 图解!24张图彻底弄懂九大常见数据结构

    万次阅读 多人点赞 2020-05-24 22:23:36
    数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。 常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的...
  • 数据结构:八种数据结构大全

    万次阅读 多人点赞 2021-07-29 12:36:10
    常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等; 1.2 数据结构的分类 1.2.1 排列方式 1)集合 集合数据结构中的...
  • Java的数据结构有那些?

    千次阅读 2022-03-29 23:58:26
    顺序储存结构是用数组来保存数据的, 线性表也就是数组的一种特殊储存方式:从头到尾依次储存数据。 下面这种情况就不是线性表 java中以ArrayList为例 数组扩容:ArrayList的底层是Object类的数组,默认
  • 数据结构-JS实现集合

    千次阅读 2021-03-08 17:20:16
    文章目录一、什么是集合?1.1 集合常见方法 一、什么是集合? 1.1 集合常见方法
  • 数据结构面试常见问题总结

    千次阅读 2021-09-18 08:52:09
    数据结构面试常见问题总结 写在前面 本文记录了一些数据结构面试常见问题,本意用于考研复试,以下面试题为网上整理的问题以及自己加入的一些问题,答案仅供参考! Q:数据结构三要素 A:逻辑结构、物理结构、数据...
  • 常见数据结构 单链表结构和顺序存储结构的区别 线性链表 数组和链表的区别 判断疫个链表是否环,如何找到这个环 单链表和双链表的区别 头指针和头结点的区别 简述KMP算法 栈和队列的区别 栈和队列的相同之处和...
  • 常见数据结构与算法整理总结(上)

    万次阅读 多人点赞 2018-08-06 18:23:14
    数据结构是以某种形式将数据...为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,需要的...
  • 八大数据结构常见面试题

    千次阅读 多人点赞 2020-12-01 21:39:16
    几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业),还是拥有几十年经验的职场老鸟。 即便是对于一些非常基础的工作来说,学习数据结构也是必须的。那么,...
  • 上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据...
  • redis的五种数据结构

    千次阅读 2022-01-26 19:04:21
    redis是一种远程内存数据库,其内部提供了五种不同类型的数据结构。简而言之,redis就是一个速度非常快的非关系型数据库(Nosql),可以存储键(key)与五种不同类型的值(value)之间的映射,就像散列表一样。 ...
  • 常见数据结构及应用场景

    千次阅读 2021-10-07 23:32:09
    数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 一、数组 有序排列的同类数据元素的集合称为数组。 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。 组成数组的各个变量称为数组的...
  • Java常见的8种数据结构

    千次阅读 2022-01-25 14:48:57
    数据结构是指数据在计算机内存空间中或磁盘中的组织形式 算法是完成特定任务的过程 二分法查找 r=2^s s:查找步数 r查找范围 幂函数 s=log2® 已知范围获取需要的次数 对数 算法复杂度使用O(N)函数进行标示 主要是...
  • Javascript中的8种常见数据结构(建议收藏)

    千次阅读 多人点赞 2020-08-04 16:17:59
    Stack具有以下常见方法: push:输入一个新元素 pop:删除顶部元素,返回删除的元素 peek:返回顶部元素 length:返回堆栈中元素的数量 Javascript中的数组具有Stack的属性,但是我们使用 function Stack() 从头...
  • java数据结构了解与集合学习

    千次阅读 2020-08-04 20:36:23
    学习集合前需要了解数据结构基础。 数据结构 数据结构是指逻辑意义上的数据组织方式及其相应的处理方式。 逻辑意义:数据结构的抽象表达非常丰富,而实际物理存储方式相对单一。比如:二叉树结构,在物理上可能也...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 301,055
精华内容 120,422
热门标签
关键字:

常见的数据结构有集合

数据结构 订阅