JAVA 合集 我就是我 2022-05-14 19:20 308阅读 0赞 ## 线性表、栈、队列、优先队列和集合 ## 数据结构是以某种形式将数据组织在一起的合集。数据结构不仅存储数据,还支持访问和处理数据的操作。 JAVA的合集框架如下图所示![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTM2Mzk0_size_27_color_FFFFFF_t_70] # 合集 # JAVA合集框架支持两种类型的容器: 一种是存储一个元素合集,简称合集。 另一种是为了存储键、值对,称为映射表。 * Set用于存储一组不重复的元素。 * List用于存储一个有序的元素合集。 * Stack用于存储采用后进先出方式处理的对象 * Queue用于存储采用后进先出方式处理的对象。 * Priority Queue 用与存储按照优先级顺序处理的对象。 # Collection接口 # Collection 接口为线性表、向量、栈、队列、优先队列以及合集定义了共同的操作。 ## 1.Collection接口通用方法 ## boolean add (Object obj):添加一个元素 boolean addAll (Collection c):将集合c中的所有元素添加到该集合中。 void clear();//清空集合中所有元素。 boolean contains (Object o):判断集合中是否包含指定的元素 boolean containsAll (Collection c):判断集合中是否包含指定的集合的所有元素。 boolean equals(Object o) 比较此集合 与指定对象是否相等。 boolean isEmpty() 如果此集合为空,则返回 true。 boolean remove(Object o) 从此集合中移除指定元素 boolean removeAll(Collection<?> c) 从集合从移除中的所有元素 boolean retainAll(Collection<?> c) 保留同时位于c和该集合中的元素。 int size() 返回此集合中的元素个数。 Object\[\] toArray() 返回包含此 集合中所有元素的数组。 T\[\] toArray(T\[\] a) 返回包含此 集合中所有元素的数组;返回数组的运行时类型与指定数组的运行时类型相同。 public class MyDemo { public static void main(String[] args) { Collection<String> collection = new ArrayList<>(); //add() 往 集合中添加元素 collection.add("林黛玉"); collection.add("贾宝玉"); collection.add("史湘云"); collection.add("薛宝钗"); System.out.println(collection);//[林黛玉, 贾宝玉, 史湘云, 薛宝钗] Collection<String> list = new ArrayList<String>(); list.add("周瑜"); list.add("小乔"); list.add("大乔"); list.add("孙尚香"); list.add("史湘云"); list.add("薛宝钗"); //A集合addAll(B集合) 把B集合中的元素放到A集合当中 boolean b = collection.addAll(list); System.out.println(b);//true System.out.println(collection);//[林黛玉, 贾宝玉, 史湘云, 薛宝钗, 周瑜, 小乔, 大乔, 孙尚香, 史湘云, 薛宝钗] //clear(); list.clear();//清空集合中所有元素 System.out.println(list);//[] //remove(); collection.remove("薛宝钗");//移除某一个元素 System.out.println( collection);//[林黛玉, 贾宝玉, 史湘云, 周瑜, 小乔, 大乔, 孙尚香, 史湘云, 薛宝钗] //removeAll(); list.add("周瑜"); list.add("小乔"); list.add("大乔"); list.add("孙尚香"); list.add("史湘云"); list.add("薛宝钗"); collection.removeAll(list); System.out.println(collection);//[林黛玉, 贾宝玉] //containsAll(B集合) //contains (Object o) collection.add("林黛玉"); collection.add("贾宝玉"); collection.add("周瑜"); collection.add("小乔"); collection.add("大乔"); collection.add("孙尚香"); list.clear(); list.add("周瑜"); list.add("小乔"); list.add("大乔"); list.add("孙尚香"); b = list.contains("周瑜"); System.out.println(b);//true boolean b1 = collection.containsAll(list); System.out.println(b1);//true //size(); System.out.println(list.size());//4 //isEmpty(); System.out.println(list.isEmpty());//false System.out.println(list.size()==0);//flase } } ## 2.迭代器 ## 每种合集都是可迭代的(Iterable)。 可以获得集合的Iterator 对象来遍历合集中的所有元素。 terator是一种经典的设计模式,用于在不需要暴露数据是如何保存在数据结构的细节的情况下,来遍历一个数据结构。 Collection接口继承自Iterable接口。 使用集合的terator()方法来返回一个迭代器。 boolean hasNext () 如果仍有元素可以迭代,则返回 true。 E next () 返回迭代的下一个元素。 void remove() 移除使用next方法获取的上一个元素。 public class MyIteratorDemo { public static void main(String[] args) { Collection<String> list = new ArrayList<>(); list.add("令狐冲"); list.add("岳灵珊"); list.add("岳不群"); list.add("任盈盈"); list.add("任我行"); list.add("田伯光"); //遍历集合中的元素 Iterator iterator = list.iterator(); while (iterator.hasNext()){ Object o = iterator.next(); System.out.println(o);//令狐冲 岳灵珊 岳不群 任盈盈 任我行 田伯光 } } } ## 3.List接口 ## List接口继承自Collection接口,定义了一个用于顺序存储元素的合集。 List集合特点:元素有序,每个元素都有索引,允许存储重复元素. ### 1).List接口 ### boolean add(:int index,Object element) 在指定索引位置加入一个指定元素 boolean addAll(:int index ,Collection<?extends E> c) 在指定位置处添加c的所有元素。 int indexOf(Object element) 返回第一个匹配元素的索引 int lastIndexOf(Object element) 返回最后一个匹配元素的索引 E get(int index) 返回指定索引处的元素 Object set(int index,Object elements) 设置指定索引处的元素 E remove(int index)移除指定索引处元素 list subList(int fromIndex,int toIndex) 返回从fromIndex到toIndex-1的子线性表。 public class ListDemo { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); //add() list.add(200); list.add(300); list.add(0,100); System.out.println(list);//[100, 200, 300] //addAll() List<Integer> list2 = new ArrayList<Integer>(); list2.add(100); list2.add(500); list.addAll(2,list2); System.out.println(list);//[100, 200, 100, 500, 300] //indexOf() lastIndexOf() System.out.println(list.indexOf(100));//0 System.out.println(list.lastIndexOf(100));//2 //get() System.out.println(list.get(2));//100 //set list.set(1,500); System.out.println(list);//[100, 500, 100, 500, 300] //remove() list.remove(0); System.out.println(list);//[500, 100, 500, 300] //subList List list3= list.subList(1,3); System.out.println(list3);//[100, 500] } } ### 2).list迭代器ListIterator ### ListIterator接口继承了Iterator接口 void add(E element) 添加一个指定对象到线性表中。 boolean hasPrevious()当往回遍历时,如果还有更多元素,则返回true int nextIndex()返回下一个元素的索引 E previous()返回线性表遍历器的前一个元素。 int previousIndex() 返回前一个元素索引 void set(E element)使用指定元素替换previous或者next方法返回的最后一个元素 可以使用List的listIterator(int star)方法获得从star开始的元素迭代器 public class listIteratorDemo { public static void main(String[] args) { List<Character> list = new ArrayList<>(); list.add('a'); list.add('c'); list.add('e'); ListIterator<Character> ite = list.listIterator(list.size()); while(ite.hasPrevious()){ System.out.println(ite.previousIndex());//依次2 1 0 System.out.println(ite.previous());//依次 e c a } ite.set('o');//注意添加到上一次遍历的地方 list.add('p'); System.out.println(list);//[o, c, e, p] } } ### 3.)ArrayList 类 ### ArrayList使用大小可变的数组实现List接口 每个Arraylist实例都有它的容量,这个容量是指存储线性表中元素的数组的大小。它–定不小于所存储的线性表的大小。向ArrayList中添加元素时,其容量会自动增大。ArrayList 不能自动减小。可以使用方法trimToSizeO将数组容量减小到线性表的大小。 构造方法: ArrayList() 创建一个空的线性表 ArrayList(Collection<? extends > c)从已经存在的合集中创建线性表 ArrayList(int initialCapacity ) 创建一个指定容量的容器。 public class ArrayListDemo { public static void main(String[] args) { ArrayList arrayList = new ArrayList(); arrayList.add(400); arrayList.add(500); arrayList.add(600); arrayList.add(100); arrayList.add(200); arrayList.add(100); arrayList.add(200); arrayList.add(300); int i = arrayList.indexOf(100); i=arrayList.lastIndexOf(100); System.out.println(i);//5 //排序集合中的元素 arrayList.sort(new Comparator() { @Override public int compare(Object s1, Object s2) { Integer a= (Integer) s1; Integer b= (Integer) s2; return -(a-b); } }); System.out.println(arrayList);//[600, 500, 400, 300, 200, 200, 100, 100] //根据索引截取集合中的元素 List list = arrayList.subList(0, 3); System.out.println(list);//[600, 500, 400] System.out.println(arrayList);//[600, 500, 400, 300, 200, 200, 100, 100] } } ### 4).LinkedList类 ### linkedList类使用链表实现List接口。除了实现List接口外,这个类还提供了从线性表两端提取、插入和删除元素的方法。 void addFirst (E e)在此列表的开始处插入指定的元素。 void addLast (E e)将指定的元素列表的结束。 E getFirst ()返回此列表中的第一个元素。 E getLast ()返回此列表中的最后一个元素。 E pollFirst ()检索并移除此列表的第一个元素, E pollLast ()检索并移除此列表的最后一个元素, public class LinkedListDemo { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(100); linkedList.add(800); linkedList.addLast(500); linkedList.addFirst(600); for (int i = 0; i < linkedList.size(); i++) { Object o = linkedList.get(i); System.out.println(o);//依次600 100 800 500 } System.out.println("---------------------------"); System.out.println(linkedList.getFirst());//600 System.out.println(linkedList.pollFirst());//600 System.out.println(linkedList);//[100, 800, 500] } } 链表可以使用get(i)方法,但非常耗时。 ### 5)Vector与Stack ### void addElement (E obj)添加指定的组件到这个向量的结束,增加其大小由一个。 E elementAt ( int index)返回指定索引处的组件。 Enumeration elements ()返回此向量的组件的枚举。 boolean equals (Object o)将指定的对象与此向量进行比较,以进行相等性。 E firstElement ()返回第一个组件(在指数 0 项目)这个载体。 E lastElement ()返回向量的最后一个组件。 void removeElementAt ( int index) 在指定的索引中删除组件 public class VectorDemo { public static void main(String[] args) { Vector vector = new Vector(); vector.addElement(100); vector.addElement(200); vector.addElement(300); Vector vector2 = new Vector(); vector2.addElement(100); vector2.addElement(200); vector2.addElement(300); vector2.addElement(500); //返回一个迭代器 Enumeration elements = vector.elements(); while (elements.hasMoreElements()){ Object o = elements.nextElement(); System.out.println(o);//依次 100 200 300 } //对比两个集合当中元素是否一模一样 boolean equals = vector.equals(vector2); System.out.println(equals);//flase Object o = vector2.firstElement(); System.out.println(o);//100 vector2.removeElementAt(vector2.size()-1); System.out.println(vector2);//[100, 200, 300] } } stack是作为Vector类的扩展来实现的。 Stack()创建一个空栈 boolean empty() 判断栈空 E peek() 返回栈顶元素 E pop()返回并移除栈顶元素 E push(E o)增加新元素到栈顶 int search(Object:o)返回栈中指定元素的位置 ## 3.Queue接口 ## Queue接口继承自Collection、加入了插入、提取和检验等操作。 ### 1).Queue接口方法 ### boolean offer(E elements)插入一个元素到队列中 E poll()返回并移除队列头元素 若空返回null E remove()返回并移除队列头元素 若空抛出异常 E peek()获取但不移除队列头元素若空返回null E element() 获取但不移除队列头元素若空抛出异常 public class QueueDemo{ public static void main(String[] args){ Queue<String> queue = new Queue<>(); queue.offer("aaa"); queue.offer("bbb"); queue.offer("ccc"); queue.offer("ddd"); while(queue.size()>0){ System.out.println(queue.remove()); } } } ### 2).双端队列Deque和链表LinkedList ### Deque支持在两端插人和删除元素。deque是(double-endedqueue),双端队列的简称。Deque接口继承自Queue,增加了从队列两端插人和删除元素的方法。方法addFirst(e)、removeFirstO、addLast(e)、 removeLastO、 getFirst() 和getLastO都在Deque接口中定义。 LinkedList也实现了Deque。 ### 3).Priorityqueue优先队列 ### PriorityQueue类实现了一个优先队列。默认情况下,优先队列使用Comparable以元素的自然顺序进行排序。拥有最小数值的元素被赋予最高优先级,因此最先从队列中删除。如果几个元素具有相同的最高优先级,则任意选择一个。也可以使用构造方法PriorityQueue(initialCapacity , comparator)中的Comparator来指定一个顺序。 PriorityQueue() 创建一个初始容量为11的默认优先队列 PriorityQueue(int initialCapacity)创建一个初始容量为指定值的默认优先队列 PriorityQueue(Collection <? extends E> c)创建一个具有指定集合的优先队列 PriorityQueue(int initialCapacity,Comparator<? super E>comparator) 创建一个初始容量为指定值并且具有比较器的优先队列。 public class Priori tyQueueDemo{ public static void main(String[] args){ PriorityQueue<String> queuel = new PriorityQueue<>() queuel.offer("oklahoma"); queuel.offer("Indiana"); queuel.offer("Georgia"); queue1.offer("Texas"); while(queue1.size() > 0){ System. out .println(queuel.remove()); PriorityQueue<String> queue2 = new PriorityQueue(4,Collections.reverseOrder()); queue2.offer("Okl ahoma"); queue2.offer("Indiana"); queue2.offer("Georgia"); queue2.offer("Texas"); while (queue2.sizeO> 0){ System.out.println(queue2.remove()); } } } # 集合 # ## Set接口 ## Set 接口扩展了Collection接口,他没有引入引入新的方法或常量,只是规定Set的实例不包括重复的元素。实现Set的具体类必须确保不能向这个集合添加重复的元素。 Set接口的三个具体的实例是:散列类HashSet、链式散列集LinkedHashSet和树形集TreeSet。 ## HashSet ## Hashset 类是一个实现了Set接口的具体类。 Hashet类有负载系数和初始容量。默认初始容量16负载系数为0.75.当元素个数超过容量与负载系数的乘积,容量就会自动翻倍。可以在构造方法中指定初始容量和负载系数。 HashSet的特点是 元素无序且不重复, 他的底层数据结构是哈希表,线程不安全效率高。 哈希表:是元素为链表的数组 (具有数组和链表的特点)。 HashSet要求必须重写hashCode方法和equals()方法,否则无法保证元素的唯一性。 当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值,然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。当该对象通过 hashCode() 方法得到的位置已有元素,则通过 equals() 方法来判断该对象与该位置使用链表存储的所有元素是否相同,若相同则不存,若不同将该元素放在该位置链表的最后。 **补充:** 1.7 如果发生了冲突,新元素会放在链表头 1.8 如果发生了冲突,新元素会放在链表尾 a -> 97 -> 1 (a).equals(a) 初始大小是 16 , 当元素超过了初始大小的 3/4, 就会发生扩容 1.7 扩容后链表的顺序会颠倒 1.8 扩容后链表的顺序会保持 1.8 后对链表长度控制有新的优化 当链表长度过长时,会首先执行扩容 当扩容的大小超过64时,就不会使用扩容减少链表长度了 在链表长度大于等于8时,会把链表变为一个搜索二叉树(红黑树) ### 构造方法: ### HashSet() HashSet(Collection<? extends E>:c)//已有集合 HashSer(int InitialCapacity)//初始容量 HashSer(int InitialCapacity,float loadFactor)//初始容量与负载系数。 public class Student { private String name; private int age; public Student(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 "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override //重写equals方法。 public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } //重写了hashCode()方法。 @Override public int hashCode() { return Objects.hash(name, age); } } public class HashSetDemo { public static void main(String[] args) { //HashSet 底层数据结构是哈希表,元素无序,且唯一 //元素的唯一性:是靠元素重写hashCode()方法和equals()方法来保证的 //哈希表:是元素为链表的数组 (具有数组和链表的特点) (JDK1.7) Student s1 = new Student("小龙女", 23); Student s2 = new Student("任盈盈", 24); Student s3 = new Student("小龙女", 23); Student s4 = new Student("东方不败", 25); Student s5 = new Student("伊琳", 29); Student s6 = new Student("周芷若", 30); HashSet<Student> hashSet = new HashSet<>(); hashSet.add(s1); hashSet.add(s2); hashSet.add(s3); hashSet.add(s4); hashSet.add(s5); hashSet.add(s6); for (Student student : hashSet) { System.out.println(student.getName()+"=="+student.getAge()); }//周芷若==30 //东方不败==25 //伊琳==29 //小龙女==23 //任盈盈==24 } } # LinkedHashSet # LinkedHashSet继承自HashSet,他的底层数据结构是链表和哈希表, 链表保证了元素有序,哈希表保证了元素唯一。即每个元素会按照插入顺序存储且不能重复。 \#\#构造方法: LinkedHashSet() LinkedHashSet(Collection<? extends E>:c)//已有集合 LinkedHashSet(int InitialCapacity)//初始容量 LinkedHashSet(int InitialCapacity,float loadFactor)//初始容量与负载系数。 public class public class SetDemo2 { public static void main(String[] args) { LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.add(10); linkedHashSet.add(20); linkedHashSet.add(30); linkedHashSet.add(40); linkedHashSet.add(10); for (Integer integer : linkedHashSet) { System.out.println(integer);//10 存储有序且不重复。 //20 //30 //40 } } } ## TreeSet ## TreeSet的底层数据结构是二叉树(比根节点大的元素放右边,比根节点小的元素放左边),此集合最大的特点是能够对元素进行排序(插入时就按照顺序排好)。 TreeSet继承自navigableSet接口,而navigableSet继承自SortedSet接口,SortedSet继承自Set接口。 ### SortedSet接口方法 ### E first() //返回第一个元素 E last() //返回最后一个元素 SortedSet headSet(E toElement)//返回一个小于该元素的所有元素组成的集合 SortedSet tailSet(E fromElement)//返回一个大于等于该元素的所有元素组成的集合 ### NavigableSet接口方法 ### E pollFirst()//删除并返回首元素 E pollLast()//删除并返回尾元素 E lower(E e)//返回一个小于该元素的元素 E higher(E e)//返回一个大于该元素的元素 E floor(E e)//返回一个小于等于该元素的元素 E ceiling(E e)//返回一个大于等于该元素的元素 ### 构造方法 ### TreeSet()//空参构造 TreeSet(Collection<? extends E> e)//使用已有集合构造 TreeSet(Comparator<? super E> comparator)//使用比较器 TreeSet(SortSet s)//使用已有SortSet构造 TreeSet集合的排序方式 分为自然排序和比较器排序。 自然排序就是元素的类型必须继承实现Compareble接口,重写此接口中的 compareTo() 方法。 比较排序是通过TreeSet(Comparator < ? super E > comparator)构造方法,其中参数是给定的比较器。 ### 自然排序 ### public class Student implements Comparable<Student>{ private String name; private int age; public Student() { } public Student(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 "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override //重写类compareTo方法 按照年龄由大到小排序 public int compareTo(Student s) { int flag=0; int num=this.age-s.getAge(); int num2=num==0?this.name.compareTo(s.name):num; return -num2; } } public class TreeSetDemo { public static void main(String[] args) { Student s1 = new Student("穆念慈aa", 20); Student s2 = new Student("阿紫cccc", 21); Student s3 = new Student("阿朱aaaaa", 23); Student s4 = new Student("秦红棉ddd", 19); Student s5 = new Student("黄蓉ddddd", 27); Student s6 = new Student("郭芙ddd", 23); Student s7 = new Student("郭襄", 20); Student s8 = new Student("李莫愁aaa", 20); Student s9 = new Student("小龙女cccccccccc", 20); Student s10 = new Student("小龙女3ffff", 20); Student s11 = new Student("穆念慈", 22); Student s12 = new Student("穆念慈", 22); TreeSet<Student> treeSet = new TreeSet<>(); treeSet.add(s1); treeSet.add(s2); treeSet.add(s3); treeSet.add(s4); treeSet.add(s5); treeSet.add(s6); treeSet.add(s7); treeSet.add(s8); treeSet.add(s9); treeSet.add(s10); treeSet.add(s11); treeSet.add(s12); for (Student student : treeSet) { System.out.println(student.getName()+"=="+student.getAge()); }// 黄蓉ddddd==27 根据重写的compareTo比较方法进行排序 // 阿朱aaaaa==23 // 郭芙ddd==23 // 穆念慈==22 // 阿紫cccc==21 // 郭襄==20 // 穆念慈aa==20 // 李莫愁aaa==20 // 小龙女cccccccccc==20 // 小龙女3ffff==20 // 秦红棉ddd==19 } } ### 比较排序 ### public class Student { private String name; private int age; public Student() { } public Student(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 "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } } //自定义了比较器 //也可以使用匿名内部类 public class MyComparetor implements Comparator<Student> { @Override public int compare(Student s1, Student s2) { //年龄由小到大 int num = s1.getAge() - s2.getAge(); int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num; return num2; } } public class TreeSetDemo { public static void main(String[] args) { //使用比较器的构造方法 TreeSet<Student> treeSet = new TreeSet<>(new MyComparetor()); Student s1 = new Student("穆念慈aa", 20); Student s2 = new Student("阿紫cccc", 21); Student s3 = new Student("阿朱aaaaa", 23); Student s4 = new Student("秦红棉ddd", 19); Student s5 = new Student("黄蓉ddddd", 27); Student s6 = new Student("郭芙ddd", 23); Student s7 = new Student("郭襄", 20); Student s8 = new Student("李莫愁aaa", 20); Student s9 = new Student("小龙女cccccccccc", 20); Student s10 = new Student("小龙女3ffff", 20); Student s11 = new Student("穆念慈", 22); Student s12 = new Student("穆念慈", 23); treeSet.add(s1); treeSet.add(s2); treeSet.add(s3); treeSet.add(s4); treeSet.add(s5); treeSet.add(s6); treeSet.add(s7); treeSet.add(s8); treeSet.add(s9); treeSet.add(s10); treeSet.add(s11); treeSet.add(s12); for (Student student : treeSet) { System.out.println(student.getName()+"=="+student.getAge()); }秦红棉ddd==19 //小龙女3ffff==20 //小龙女cccccccccc==20 //李莫愁aaa==20 //穆念慈aa==20 //郭襄==20 //阿紫cccc==21 //穆念慈==22 //穆念慈==23 //郭芙ddd==23 //阿朱aaaaa==23 //黄蓉ddddd==27 } } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTM2Mzk0_size_27_color_FFFFFF_t_70]: /images/20220503/8133f048ba9343e8b391d857b9ccfd4b.png
还没有评论,来说两句吧...