List, set, data structure, collections
primary coverage
Learning objectives
Chapter I data structure
1.1 what is the use of data structures?
When you use the container class in Java, have you ever thought about how ArrayList is like an infinitely expanded array or a linked list. Does it work? Easy to use, this is the use of data structures, but you use them unknowingly.
For real-world storage, we use tools and modeling. Each data structure has its own advantages and disadvantages. Think about it. If Google's data is stored in arrays, can we easily query the required data? The algorithm, in so much data, how to do the fastest insertion, search and deletion, is also pursuing faster.
We Java is an object-oriented language, just like an automatic car, and C language is like a manual jeep. What about data structures? This is how the transmission works. You can drive an automatic car from point a to point B without knowing how the gearbox works, and it may not be slower than those who know it. Writing a program, like driving, experience can play a great role, but if you don't know how the bottom works, you can only drive forever, neither repair nor build a car. Of course, there are a lot of data structures. It takes a lot of effort to learn them carefully, and it is impossible to achieve them overnight. We will introduce the common data structures: stack, queue, array, linked list and red black tree. As an introduction to data structures, we can understand their characteristics.
1.2 common data structures
The common structures of data storage are stack, queue, array, linked list and red black tree. Let's take a look at:
Stack
To put it simply: the set with this structure has the following characteristics for accessing elements
Here are two nouns to note:
queue
In short, the set with this structure has the following characteristics for accessing elements:
array
In short, the set with this structure has the following characteristics for accessing elements:
Linked list
In short, the set with this structure has the following characteristics for accessing elements:
Red black tree
A simple understanding is a structure similar to a tree in our life, but each node can only have two child nodes at most.
A binary tree is a tree structure in which each node has at most two subtrees. The top is called the root node, and the two sides are called "left subtree" and "right subtree".
As shown in the figure:
What we want to say is an interesting kind of binary tree called red black tree. The red black tree itself is a binary search tree. After inserting nodes, the tree is still a binary search tree. That means that the key values of the tree are still ordered.
Red black tree constraints:
Characteristics of red black tree:
The speed is particularly fast, approaching the balanced tree, and the minimum and maximum times of finding leaf elements are no more than twice
Chapter 2 list set
After we have mastered the use of the collection interface, let's take a look at the subclasses in the collection interface. What features do they have?
Next, let's learn several common subclasses in collection (Java. Util. List set, Java. Util. Set set set).
2.1 introduction to list interface
java. util. The list interface inherits from the collection interface and is an important branch of a single column collection. It is customary to call the objects that implement the list interface a list collection. Duplicate elements are allowed in the list set. All elements are stored in a linear way. The specified elements in the set can be accessed by index in the program. In addition, a feature of the list set is that the elements are orderly, that is, the storage order of the elements is consistent with the extraction order.
After reading the API, let's summarize:
List interface features:
2.2 common methods in list interface
As a sub interface of the collection, list not only inherits all the methods in the collection interface, but also adds some special methods to operate the collection according to the element index, as follows:
The unique methods of the list set are related to the index. We have studied them before, so let's review them again:
public class ListDemo {
public static void main(String[] args) {
// 创建List集合对象
List<String> list = new ArrayList<String>();
// 往 尾部添加 指定元素
list.add("图图");
list.add("小美");
list.add("不高兴");
System.out.println(list);
// add(int index,String s) 往指定位置添加
list.add(1,"没头脑");
System.out.println(list);
// String remove(int index) 删除指定位置元素 返回被删除元素
// 删除索引位置为2的元素
System.out.println("删除索引位置为2的元素");
System.out.println(list.remove(2));
System.out.println(list);
// String set(int index,String s)
// 在指定位置 进行 元素替代（改）
// 修改指定位置元素
list.set(0,"三毛");
System.out.println(list);
// String get(int index) 获取指定位置元素
// 跟size() 方法一起用 来 遍历的
for(int i = 0;i<list.size();i++){
System.out.println(list.get(i));
}
//还可以使用增强for
for (String string : list) {
System.out.println(string);
}
}
}
Chapter 3 subclasses of list
3.1 ArrayList set
java. util. The structure of the ArrayList collection data store is an array structure. The addition and deletion of elements are slow and the search is fast. Because the functions most used in daily development are querying data and traversing data, ArrayList is the most commonly used collection.
Many programmers use ArrayList very casually to complete any requirements during development, which is not rigorous. This usage is not advocated.
3.2 LinkedList set
java. util. The structure of LinkedList set data storage is linked list structure. A collection that facilitates the addition and deletion of elements.
In the actual development, the addition and deletion of a collection element often involves head and tail operations, and LinkedList provides a large number of methods of head and tail operations. We can understand these methods as follows:
LinkedList is a subclass of list. The methods LinkedList in list can be used. We won't introduce them in detail here. We just need to understand the unique methods of LinkedList. During development, the LinkedList collection can also be used as a stack and queue structure. (just understand)
Method demonstration:
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
//添加元素
link.addFirst("abc1");
link.addFirst("abc2");
link.addFirst("abc3");
System.out.println(link);
// 获取元素
System.out.println(link.getFirst());
System.out.println(link.getLast());
// 删除元素
System.out.println(link.removeFirst());
System.out.println(link.removeLast());
while (!link.isEmpty()) { //判断集合是否为空
System.out.println(link.pop()); //弹出集合中的栈顶元素
}
System.out.println(link);
}
}
Chapter 4 set interface
java. util. Set interface and Java util. Like the list interface, it also inherits from the collection interface. It is basically the same as the methods in the collection interface. It does not expand the functions of the collection interface, but is more strict than the collection interface. Different from the list interface, the elements in the set interface are out of order, and some rules will be used to ensure that the stored elements are not repeated.
The set collection has several subclasses. Here we introduce Java util. HashSet、java. util. Linkedhashset these two sets.
4.1 introduction to HashSet set
java. util. HashSet is an implementation class of the set interface. The elements stored in it are non repeatable, and the elements are out of order (that is, the access order is inconsistent). java. util. The underlying implementation of HashSet is actually a Java util. HashMap support. Since we haven't learned yet, let's understand it first.
HashSet determines the storage location of elements in the set according to the hash value of objects, so it has good access and search performance. The way to ensure element uniqueness depends on the hashcode and equals methods.
Let's first use set storage, look at the phenomenon, and then explain the principle:
public class HashSetDemo {
public static void main(String[] args) {
//创建 Set集合
HashSet<String> set = new HashSet<String>();
//添加元素
set.add(new String("cba"));
set.add("abc");
set.add("bac");
set.add("cba");
//遍历
for (String name : set) {
System.out.println(name);
}
}
}
The output results are as follows, indicating that duplicate elements cannot be stored in the collection:
cba
abc
bac
4.2 data storage structure of HashSet set (hash table)
What is a hash table?
At jdk1 Before 8, the bottom layer of the hash table was realized by array + linked list, that is, the linked list was used to deal with conflicts, and the linked lists with the same hash value were stored in a linked list. However, when there are many elements in a bucket, that is, there are many elements with equal hash values, the efficiency of searching by key value in turn is low. And jdk1 In 8, the hash table storage is realized by array + linked list + red black tree. When the length of the linked list exceeds the threshold (8), the linked list is converted into a red black tree, which greatly reduces the search time.
In short, the hash table is implemented by array + linked list + red black tree (JDK1.8 adds the red black tree part), as shown in the following figure.
When you see this picture, someone wants to ask, how is this stored?
In order to facilitate your understanding, let's illustrate it with a storage flow chart:
In short, jdk1 8. The introduction of red black tree greatly optimizes the performance of HashMap. For us, ensuring the uniqueness of HashSet set elements is actually determined according to the hashcode and equals methods of the object. If we store custom objects in the collection, to ensure their uniqueness, we must duplicate the hashcode and equals methods to establish a comparison method belonging to the current object.
4.3 HashSet stores custom type elements
When storing custom type elements in the HashSet, you need to override the hashcode and equals methods in the object and establish your own comparison method to ensure the uniqueness of the objects in the HashSet set
Create a custom student class
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 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);
}
@Override
public int hashCode() {
return Objects.hash(name,age);
}
}
public class HashSetDemo2 {
public static void main(String[] args) {
//创建集合对象 该集合中存储 Student类型对象
HashSet<Student> stuSet = new HashSet<Student>();
//存储
Student stu = new Student("于谦",43);
stuSet.add(stu);
stuSet.add(new Student("郭德纲",44));
stuSet.add(new Student("于谦",43));
stuSet.add(new Student("郭麒麟",23));
stuSet.add(stu);
for (Student stu2 : stuSet) {
System.out.println(stu2);
}
}
}
执行结果：
Student [name=郭德纲,age=44]
Student [name=于谦,age=43]
Student [name=郭麒麟,age=23]
4.4 LinkedHashSet
We know that HashSet ensures the uniqueness of elements, but there is no order in which elements are stored. What should we do to ensure order?
Under HashSet, there is a subclass Java util. Linkedhashset is a data storage structure composed of linked list and hash table.
The demonstration code is as follows:
public class LinkedHashSetDemo {
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<String>();
set.add("bbb");
set.add("aaa");
set.add("abc");
set.add("bbc");
Iterator<String> it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
结果：
bbb
aaa
abc
bbc
4.5 variable parameters
At jdk1 After 5, if we define a method that needs to accept multiple parameters and multiple parameter types are consistent, we can simplify it into the following format:
修饰符 返回值类型 方法名(参数类型... 形参名){ }
In fact, this writing is completely equivalent to
修饰符 返回值类型 方法名(参数类型[] 形参名){ }
Only for the latter definition, the array must be passed when calling, and the former can directly pass data.
JDK1. After 5. Simplified operation appears When used on parameters, they are called variable parameters.
It also represents an array, but when calling this method with variable parameters, you don't need to create an array (that's the simplicity). You can directly pass the elements in the array as actual parameters. In fact, the compiled class file encapsulates these elements into a data group for transmission. These actions are being compiled Class file, automatically completed.
Code demonstration:
public class ChangeArgs {
public static void main(String[] args) {
int[] arr = { 1,4,62,431,2 };
int sum = getSum(arr);
System.out.println(sum);
// 6 7 2 12 2121
// 求 这几个元素和 6 7 2 12 2121
int sum2 = getSum(6,7,2,12,2121);
System.out.println(sum2);
}
/*
* 完成数组 所有元素的求和 原始写法
public static int getSum(int[] arr){
int sum = 0;
for(int a : arr){
sum += a;
}
return sum;
}
*/
//可变参数写法
public static int getSum(int... arr) {
int sum = 0;
for (int a : arr) {
sum += a;
}
return sum;
}
}
4.6 jdk9 optimization of set addition
Usually, we create a set (for example, list or set) in the code and directly fill it with some elements. Instantiate the set and call several add methods to make the code repeat.
public class Demo01 {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("abc");
list.add("def");
list.add("ghi");
System.out.println(list);
}
}
Java 9 adds several collection factory methods to make it easier to create collections and map instances with a small number of elements. The new static factory methods of list, set and map can more easily create immutable instances of sets.
example:
public class HelloJDK9 {
public static void main(String[] args) {
Set<String> str1=Set.of("a","b","c");
//str1.add("c");这里编译的时候不会错，但是执行的时候会报错，因为是不可变的集合
System.out.println(str1);
Map<String,Integer> str2=Map.of("a",1,2);
System.out.println(str2);
List<String> str3=List.of("a","b");
System.out.println(str3);
}
}
The following two points should be noted:
Chapter V collections
5.1 common functions
Code demonstration:
public class CollectionsDemo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
//原来写法
//list.add(12);
//list.add(14);
//list.add(15);
//list.add(1000);
//采用工具类 完成 往集合中添加元素
Collections.addAll(list,5,222,1，2);
System.out.println(list);
//排序方法
Collections.sort(list);
System.out.println(list);
}
}
结果：
[5,2]
[1,222]
After the code demonstration, we found that our collections are arranged in order, but this order adopts the default order. What should we do if we want to specify the order?
We found that there is another method not mentioned. Public static < T > void sort (list < T > list, comparator ): sort the elements in the collection according to the specified rules. Next, let's explain the arrangement of specified rules.
5.2 comparator comparator
Let's study this method first
Public static < T > void sort (list < T > list): sort the elements in the collection according to the default rules.
However, this time the string type is stored.
public class CollectionsDemo2 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cba");
list.add("aba");
list.add("sba");
list.add("nba");
//排序方法
Collections.sort(list);
System.out.println(list);
}
}
result:
[aba,cba,nba,sba]
We use the default rules to sort strings. How do we define the default rules?
When it comes to sorting, it is simply to compare the size of two objects. Two methods of comparison implementation are provided in Java. One is to adopt Java The lang. comparable interface is implemented. One is flexible. When I need to sort, I choose Java util. Comparator interface completed.
Then, the sorting method of public static < T > void sort (list < T > list) actually requires the sorted type to implement the comparison function of the comparable interface. The string types are as follows:
public final class String implements java.io.Serializable,Comparable<String>,CharSequence {
The string class implements this interface and completes the definition of comparison rules, but this rule is written to death. For example, if I want to arrange strings in descending order according to the first character, it is impossible to modify the source code of string. Then we can use it at this time
The public static < T > void sort (list < T > list, comparator ) method can be completed flexibly. This involves the comparator interface, which is located in Java Under util package, sorting is one of the functions that can be realized by comparator. This interface represents a comparator, which is comparable! As the name suggests, sorting is done. Generally speaking, it is necessary to compare the two objects, who is in the front and who is in the back, so the comparison method is:
The operation is as follows:
public class CollectionsDemo3 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cba");
list.add("aba");
list.add("sba");
list.add("nba");
//排序方法 按照第一个单词的降序
Collections.sort(list,new Comparator<String>() {
@Override
public int compare(String o1,String o2) {
return o2.charAt(0) - o1.charAt(0);
}
});
System.out.println(list);
}
}
The results are as follows:
[sba,aba]
5.3 briefly describe the differences between comparable and comparator interfaces.
Comparable: forces an overall ordering of the objects of each class that implements it. This sort is called the natural sort of class, and the CompareTo method of class is called its natural comparison method. Compareto() can only be implemented once in a class. You can't often modify the code of the class to achieve the sort you want. The list of objects (and arrays) that implement this interface can be automatically sorted through collections.sort (and arrays. Sort). Objects can be used as keys in ordered mappings or elements in ordered collections without specifying comparators.
Comparator forces an object to be sorted as a whole. Comparators can be passed to sort methods, such as collections.sort or arrays.sort, to allow precise control over sort order. Comparators can also be used to control the order of certain data structures, such as ordered sets or ordered mappings, or to provide sorting for collections of objects that do not have natural order.
5.4 practice
Create a student class and store it in the ArrayList collection to complete the specified sorting operation.
Student initial class
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 +
'}';
}
}
Test class:
public class Demo {
public static void main(String[] args) {
// 创建四个学生对象 存储到集合中
ArrayList<Student> list = new ArrayList<Student>();
list.add(new Student("rose",18));
list.add(new Student("jack",16));
list.add(new Student("abc",16));
list.add(new Student("ace",17));
list.add(new Student("mark",16));
/*
让学生 按照年龄排序 升序
*/
// Collections.sort(list);//要求 该list中元素类型 必须实现比较器Comparable接口
for (Student student : list) {
System.out.println(student);
}
}
}
It is found that when we call collections The program reported an error when using the sort () method.
Reason: if you want the elements in the collection to finish sorting, you must implement the comparator comparable interface.
So we have completed an implementation of the student class, as follows:
public class Student implements Comparable<Student>{
....
@Override
public int compareTo(Student o) {
return this.age-o.age;//升序
}
}
Test again and the code is OK. The effect is as follows:
Student{name='jack',age=16}
Student{name='abc',age=16}
Student{name='mark',age=16}
Student{name='ace',age=17}
Student{name='rose',age=18}
5.5 extension
If you want to use independent definition rules when using, you can use collections Sort (list, comparator C) method, define rules by yourself:
Collections.sort(list,new Comparator<Student>() {
@Override
public int compare(Student o1,Student o2) {
return o2.getAge()-o1.getAge();//以学生的年龄降序
}
});
effect:
Student{name='rose',age=18}
Student{name='ace',age=17}
Student{name='jack',age=16}
If you want more rules, you can refer to the following code:
Collections.sort(list,new Comparator<Student>() {
@Override
public int compare(Student o1,Student o2) {
// 年龄降序
int result = o2.getAge()-o1.getAge();//年龄降序
if(result==0){//第一个规则判断完了 下一个规则 姓名的首字母 升序
result = o1.getName().charAt(0)-o2.getName().charAt(0);
}
return result;
}
});
The effects are as follows:
Student{name='rose',age=17}
Student{name='abc',age=16}
Student{name='jack',age=16}