List, Set, data structure, Collections

Learning objectives

  • Be able to tell the characteristics of the List set
  • Be able to say common data structures
  • Be able to tell the characteristics of array structure
  • Be able to tell the characteristics of stack structure
  • Be able to tell the characteristics of queue structure
  • Be able to tell the structural characteristics of one-way linked list
  • Be able to tell the characteristics of Set
  • Be able to tell the characteristics of hash table
  • Use the HashSet collection to store custom elements
  • Be able to say the format of variable parameters
  • Ability to use collection tool classes
  • Ability to sort using Comparator comparator interface

1. List collection

1.1 List interface: ordered with index elements and repeatable

java. util. The List interface inherits from the Collection interface and is an important branch of a single column set. The objects that implement the List interface are habitually called List sets. 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 List set is that the elements are orderly, that is, the storage order of elements is consistent with the extraction order.

  • List interface features:

    • Is an ordered set of elements; For example, if the order of storing elements is 11, 22 and 33, the storage order of elements in the set is 11, 22 and 33

    • Is a set with an index; Through the index, you can accurately operate the elements in the collection (the same reason as the index of the array) get(0)

    • The elements in the collection are repeatable

Tips: subclass of the List interface java util. ArrayList class. All the methods in this class are defined from the List

1.2 common methods in list interface

  • public void add(int index, E element): adds the specified element to the specified position in the collection// Insert element, add

    It can be inserted in the head or tail. The index does not report exceptions, and others report index out of bounds exceptions!!!

  • public E remove(int index): removes the element at the specified position in the list and returns the removed element// Indirect deletion

  • public E set(int index, E element): replace the element at the specified position in the set with the specified element, and return the element before update// Change, set

  • public E get(int index): returns the element at the specified position in the collection// Search to get the element, and get the element according to the index

2. Data structure

2.1 what is the use of data structure?

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 data we need? The algorithm, in so much data, how to do the fastest insertion, search and deletion, is also pursuing faster.

java is an object-oriented language, just like an automatic car, and C language is like A manual jeep. What about the data structure? 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 always only drive, neither repair nor build A car. Of course, the content of data structure is relatively large, and it takes A lot of effort to learn it carefully. It is impossible to achieve it overnight. We will take the common data structures: stack, queue, array, linked list and red black tree as the introduction of data structures. Just learn about their characteristics.

2.2 common data structures

  • The common structures of data storage are stack, queue, array, linked list and red black tree

2.2.1 stack: insert and delete at one end

  • Stack: stack, also known as stack, is a linear table with limited operation. Its limitation is that it is only allowed to insert and delete at one end of the table, and it is not allowed to add, find, delete and other operations at any other location// Applications such as undo

    • First in and last out (that is, the elements stored in can only be taken out after the elements behind it are taken out in turn). For example, when the bullet is pressed into the magazine, the bullet pressed in first is below, and then the bullet pressed in is above. When shooting, first eject the bullet above, and then eject the bullet below.

    • The entrance and exit of the stack are at the top of the stack.

Here are two nouns to note:

  • Stack pressing: is to store elements. That is, the elements are stored at the top of the stack, and the existing elements in the stack move one position to the bottom of the stack in turn.
  • Play stack: that is to take elements. That is, take out the top position elements of the stack, and the existing elements in the stack will move one position to the top of the stack in turn.

2.2.2 queue: insert at one end and delete at the other end

  • Queue: queue, like the stack, is also a linear table with limited operation. Its limitation is that it is only allowed to insert at one end of the table and delete at the other end of the table.

    • First in, first out (that is, the element stored in can only be taken out after the elements in front of it are taken out in turn). For example, when a small train passes through a cave, the front goes first and the rear goes in; The front comes out first and the rear comes out later// Application, network, message queue, you and me
    • The entrance and exit of the queue occupy one side respectively. For example, in the following figure, the left side is the entrance and the right side is the exit.

2.2.3 array: with index, the search is fast, but the addition and deletion are slow

  • Features: fast search, slow addition and deletion because there is an index, and the length of the array is fixed. To add or delete, you need to create a new array, and then copy the elements of the array. It takes time and is relatively slow

  • Array: array is an ordered sequence of elements. Array opens up a continuous space in memory and stores elements in this space. Like a row of rental houses, there are 100 rooms, from 001 to 100, and each room has a fixed number. Through the number, you can quickly find the renter.

    • Find element fast: through the index, you can quickly access the elements in the specified location

  • Slow addition and deletion of elements

  • Add elements at the specified index position: you need to create a new array, store the specified new elements at the specified index position, and then copy the original array elements to the corresponding index position of the new array according to the index. As shown below

  • Specify the index position to delete the element: you need to create a new array, copy the original array element to the corresponding index position of the new array according to the index, and the element with the specified index position in the original array will not be copied to the new array.

2.2.4 linked list: (opposite to array) slow search, fast addition and deletion

  • Linked list: linked list is composed of a series of nodes (nodes) (each element in the linked list is called a node), which can be generated dynamically at run time. Each node consists of two parts: one is the data field that stores the data element, and the other is the pointer field that stores the address of the next node. We often say that the linked list structure includes one-way linked list and two-way linked list. Here we first introduce the one-way linked list.

  • Multiple nodes are connected by address. For example, if more than one person holds hands, each person holds the next person's left hand with his right hand, and so on, so that more than one person is connected

  • Slow to find elements: to find an element, you need to find the specified elements backward through the connected nodes

  • Adding and deleting elements:

    • Add element: just modify the address connecting the next element.

  • Delete element: you only need to modify the address connecting the next element.

2.2.5 red black tree: improve the efficiency of search. Each node can only have two nodes

  • Binary tree: binary tree is an ordered tree with no more than 2 nodes// 1-100 50, binary search

A simple understanding is a structure similar to the 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 in order.

3. Subclass of List

3.1 ArrayList set

  • java. util. The structure of ArrayList collection data storage is 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 in the strict sense.

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.

LinkedList is a two-way linked list. What does a two-way linked list look like? Let's use a figure to understand it

In the actual development, the addition and deletion of a set 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:

  • Public void addfirst (E): inserts the specified element at the beginning of this list// Head and tail

  • Public void addlast (E): adds the specified element to the end of this list.

  • public E removeFirst(): removes and returns the first element of this list// Delete, head and tail

  • public E removeLast(): removes and returns the last element of this list.

  • public E getFirst(): returns the first element of this list// Cha, head and tail

  • public E getLast(): returns the last element of this list.

  • public boolean isEmpty(): returns true if the list does not contain elements// Check whether it is empty

  • public E pop(): pop an element from the stack represented by this list. The bottom layer is the removeFirst method

  • public void push(E e): pushes elements into the stack represented by this list. The bottom layer is the addFirst method

    LinkedList is a subclass of List. All the methods 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 set can also be used as a stack and queue structure. (just understand)

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. There is no functional expansion of the Collection interface, but it 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

  • Set set has several subclasses. Here we introduce Java util. HashSet,java.util.LinkedHashSet these two sets

tips:Set is also a single column set. The methods of extracting elements can be iterators and enhanced for (iterators are also used at the bottom of the set).

4.1 HashSet set (no index, out of order, de duplication, opposite to List 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 may be inconsistent). java. util. The underlying implementation of HashSet is actually a Java util. HashMap support. Since we haven't learned yet, let's learn 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// The default is the Object class, all of which are address values

//Create Set collection
HashSet<String>  set = new HashSet<String>();

//Add element
set.add("bac"); 
set.add("cba"); 
set.add("abc");
set.add(new String("cba"));
set.add("abc");

//HashSet is also a single column set. You can use the enhanced for loop to quickly traverse and get the name of each element in the set
for (String name : set) {//set.for
    System.out.println(name);
}

The output results are as follows, indicating that duplicate elements cannot be stored in the set and the access is out of order:

cba
abc
bac

tips: according to the results, we found that only one string "cba" is stored, that is, duplicate elements are not stored in the set set.

4.2 schematic diagram of HashSet de duplication principle: the bottom layer is the de duplication of hash table storage elements, using hashcode and equals methods, as shown in the following figure: (summary)

4.3 structure of data stored in HashSet set (hash table)

  • What is a hash table?

    • In 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 hash conflicts, and the linked list of the same hash value was 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 in 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 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 part of red black tree), as shown in the figure below.

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.4 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 to establish your own comparison method to ensure the uniqueness of the object 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) {//atl insert, which can be generated automatically
        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() {//atl insert, which can be generated automatically
        return Objects.hash(name, age);
    }
}

public class HashSetDemo2 {
    public static void main(String[] args) {
        //Create a collection object that stores Student type objects
        HashSet<Student> stuSet = new HashSet<Student>();
        
        //storage 
        Student stu = new Student("Yu Qian", 43);
        stuSet.add(stu);
        
        stuSet.add(new Student("Guo Degang", 44));
        stuSet.add(new Student("Yu Qian", 43));
        stuSet.add(new Student("Guo Qilin", 23));
        stuSet.add(stu);

        for (Student stu2 : stuSet) {
            System.out.println(stu2);
        }
    }
}
Execution result:
Student [name=Guo Degang, age=44]
Student [name=Yu Qian, age=43]
Student [name=Guo Qilin, age=23]

4.5 LinkedHashSet, the same as HashSet, and in order

HashSet ensures that elements are unique, but there is no order in which elements are stored. So 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 demo code is as follows:

Set<String> set = new LinkedHashSet<String>();//Polymorphic writing

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());
}
result:
    bbb
    aaa
    abc
    bbc

4.6 variable parameters (essentially an array, representing 0 or more parameters)

In jdk1 After 5, define a method, which needs to accept multiple parameters, and the types of multiple parameters are the same,

Format: can say the format of variable parameters: int... a

Modifier return value type method name(Parameter type... Formal parameter name){  }//int...a / / variable parameter, which is essentially an array

In fact, this writing is completely equivalent to

Modifier return value type method name(Parameter type[] Formal parameter name){  }//int[] a

Only for the latter definition, the array must be passed when calling, while the former can directly pass data.

JDK1. After 5. Simplified operation appears When used in 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 number group first, and then pass them. 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);
        
        // Find these elements and 6 7 2 12 2121
        int sum2 = getSum(6, 7, 2, 12, 2121);
        System.out.println(sum2);
    }

    /*
     * Complete the original writing method of summing all elements of the array
      public static int getSum(int[] arr){
        int sum = 0;
        for(int a : arr){
            sum += a;
        }
        
        return sum;
      }
    */
    
    //Variable parameter writing
    public static int getSum(int...arr) {//int[] arr
        int sum = 0;
        for (int a : arr) {
            sum += a;
        }
        
        return sum;
    }
}

tips: only one of the above add methods can exist in the same class. Because of the uncertainty of the call

Note: if the method has multiple parameters when writing, and the parameters contain variable parameters, the variable parameters must be written at the end of the parameter list. Otherwise, the variable parameter written in the front will receive all data during assignment, and the subsequent formal parameters cannot be assigned

5. Collections collection utility class

5.1 common functions

  • java.utils.Collections is a collection tool class, and the object of operation is a collection. Some methods are used as follows:

    • Public static < T > Boolean addall (collection < T > C, t... Elements): add some elements to the incoming collection
    • Public static void shuffle (list <? > list): random permutation, that is, it can disrupt the order of the collection
    • Public static < T > void sort (list < T > list): sort the elements in the collection according to the default rules, and sort integers from small to large
    • Public static < T > void sort (list < T > list, comparator <? Super T > C): sort the elements in the collection according to the specified rules

Code demonstration:

public class CollectionsDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //Original writing
        //list.add(12);
        //list.add(14);
        //list.add(15);
        //list.add(1000);
        
        //Use the tool class to add elements to the incoming collection list  
        Collections.addAll(list, 5, 222, 1, 2);
        System.out.println(list);
         //The extension reverses the set
        Collections.reverse(list);
        Collections.shuffle(list);//Shuffle the elements in the set, randomly disrupt, randomly index random elements, and must List the set
        
        //Sort collection elements
        Collections.sort(list);
        System.out.println(list);
    }
}
result:
[5, 222, 1, 2]
[1, 2, 5, 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 <? Super T >): sort the elements in the set according to the specified rules. Next, let's explain the arrangement of specified rules.

5.2 Comparator interface 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.

But this time it's a string type.

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");
        
        //Sorting method
        Collections.sort(list);//No comparator is specified. The default rule is to arrange integers. The default rule is from small to large. Guess the string?
        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 between two objects, so two methods of comparison implementation are provided in JAVA. One is to adopt JAVA Lang. comparable interface, which is flexible and can be selected when I need to sort util. Comparator interface completed.

Then, the sorting method of public static < T > void sort (list < T > list) actually requires that the sorted types need to implement the function of Comparable interface to complete comparison. 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, then 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 <? Super T >) 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 comparator can realize. This interface represents a comparator, which is comparable! As the name suggests, sorting is done. Generally speaking, it is necessary to compare two objects, who is in the front and who is in the back. Then the method of comparison is:

  • public int compare(String o1, String o2): compare the order of the two parameters.

    There are three kinds of comparison results between two objects: greater than, equal to and less than.

    If you want to sort in ascending order, then o1-o2, sort from small to large;
    If o1 is less than o2, it returns (negative number), if equal, it returns 0, and if 01 is greater than 02, it returns (positive number)
    If you want to sort in descending order
    If o1 is less than o2, it returns (positive number), if equal, it returns 0, and if 01 is greater than 02, it returns (negative number)

    Sort summary:If o1-o2,Sort from small to large,Row what, order what

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");
        
        //The sorting method sorts each word in descending order from large to small according to one character of the string
        Collections.sort(list, new Comparator<String>() {//new C option
            @Override//o1 is about to be added to the elements of the set, and there are already existing elements in the o2 set
            public int compare(String o1, String o2) {
                return o2.charAt(0) - o1.charAt(0);//Sort in ascending order, then o1-o2, sort from small to large;
            }
        });
        
        System.out.println(list);
    }
}

The results are as follows:

[sba, nba, cba, aba]

5.3 briefly describe the difference between Comparable interface and Comparator comparator interface

Comparable: forcibly sort the objects of each class that implements it as a whole. 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. Objects (and arrays) that implement this interface can be accessed through collections Sort (and Arrays.sort) for automatic sorting. Objects can be used as keys in ordered mappings or elements in ordered collections without specifying a comparator// Memory, class internal implementation comparator, default rule

Comparator: it also forces an object to be sorted as a whole. Comparators can be passed to sort methods, such as Collections.sort or Arrays.sort, allowing precise control over the sort order. You can also use comparator to control the order of some data structures (such as ordered set or ordered mapping), or to provide sorting for objects that do not have natural order// Memory, external comparator, write rules outside the class

//Memory, whether internal comparator or external comparator, should implement one of these two interfaces as long as sorting,

If both interfaces are implemented, the external Comparator is preferred

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{//The Comparable interface is not implemented
    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) {
        // Create four student objects and store them in the collection
        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));

        //Ask students to rank in ascending order according to their age
        //Collections.sort(list);// An error is reported. The element type in the list must implement the Comparable interface of the comparator

        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 to sort the elements in the collection, you must implement the Comparable interface, the 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;//Ascending order
    }
}

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) mode, define rules by yourself:

Collections.sort(list, new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return o2.getAge()-o1.getAge();//In descending order according to the age of the students
    }
});

effect:

Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='jack', age=16}
Student{name='abc', age=16}
Student{name='mark', 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) {
                // Age descending order
                int result = o2.getAge()-o1.getAge();//Age descending order

                if(result==0){//The first rule judges the ascending order of the first letter of the name of the next rule
                    result = o1.getName().charAt(0)-o2.getName().charAt(0);
                }

                return result;
            }
        });

The effect is as follows:

Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='abc', age=16}
Student{name='jack', age=16}
Student{name='mark', age=16}

extend

//Sort by age first. If the age is the same, sort by the first letter of the name
//int num = o1.getAge()-o2.getAge();
//if (num==0){
//    num = o1.getName().charAt(0)-o2.getName().charAt(0);
//}
//
//return num;

Sort by age first,If the same age,By name string.com Dictionary order method
//int num = o1.getAge()-o2.getAge();
//if (num==0){
//    num = o1.getName().compareTo(o2.getName());//o1-o2;
//}
//
//return num;

//First sort by age from small to large. If the age is the same, according to the name string com dictionary order in reverse order
int num = o1.getAge()-o2.getAge();
if (num==0){
    num = o2.getName().compareTo(o1.getName());
}

return num;

Keywords: Java Programming data structure queue

Added by sanchan on Sun, 30 Jan 2022 00:31:20 +0200

Popular Keywords

©2024 Programming VIP