Java basics – data structure

data structure

Stack

A linear table with limited operations only allows insert and delete operations at one end, and does not allow adding, searching, or deleting operations at any other position.

Features:

• First in, Last out
• The entrance and exit of the stack are the top positions of the stack

Queue

A linear table with limited operations that only allows insert operations on one end of the table and delete operations on the other end of the table.

Features:

• First in first out
• The entrance and exit of the queue occupy one side each

Array

An ordered sequence of elements that opens up a continuous space in memory and stores elements in this space

Features:

• Find elements fast (by index)
• Adding and deleting elements is slow (need to create a new array and copy data)

Linked List

It consists of a series of nodes, which can be dynamically generated at runtime. Each node consists of two parts: one is the data field for storing data elements, and the other is the pointer field. Commonly used linked list structures include singly linked lists and doubly linked lists.

Features:

• Connect between multiple nodes by address
• Finding elements is slow (search backwards through connected nodes in turn, each query element must start from the beginning)
• Fast addition and deletion of elements (modification of the pointer has no effect on the overall structure of the linked list)

Red Black Tree

The tree has multiple nodes to store elements. There is a certain relationship between certain nodes, which is represented by connecting lines, which are called edges. The upper node of the edge is called the parent node, and the lower end is called the child node. The tree is like a forked root.

• Binary tree: Binary tree is a special tree, each node of binary tree can only have 2 child nodes at most.

• Sorting tree/search tree: Based on the binary tree, the elements are in order of size, the left subtree is small, and the right subtree is large.

• Balanced tree: The tree whose height difference between the left and right subtrees does not exceed 1 is a balanced binary tree.

• Red-Black Tree

  Features: approaching a balanced tree, the query speed is very fast, and the maximum and minimum number of query leaf nodes does not exceed twice

  Restrictions

  1. Nodes can be red or black

  2. The root node is black

  3. The leaf nodes are black

  4. The child nodes of each red node are black

  5. The number of black nodes on all paths from any node to each leaf node is the same

List interface

The java.util.List interface inherits from the Collection interface and is an important branch of a single-column collection

• Features:
  1. An ordered collection, the order of storing elements and extracting elements is the same
  2. Indexed, including some indexed methods
  3. Allow storage of duplicate elements
• Unique method:
  1. public void add(int index, E element): add the specified element to the specified position
  2. public E get(int index): Returns the element at the specified position in the collection
  3. public E remove(int index): remove the element at the specified position in the collection
  4. public E set(int index, E element): replace the element at the specified position in the set with the specified element (the return value is the element before replacement)

• Note: Prevent IndexOutOfBoundsException

• List implementation class

  1. ArrayList: variable-size array implementation, this implementation is not synchronous

  2. LinkedList: Linked list structure, a collection that facilitates the addition and deletion of elements, this implementation is not synchronized

     Unique method:

     public void addFirst(E e): insert the specified element into the beginning of the linked list

     public void addLast(E e): insert the specified element into the end of the linked list

     public void push(E e): insert the specified element into the stack represented by this list

     public E getFirst(): Returns the element at the beginning of the linked list

     public E getLast(): return the end element of the linked list

     public E removeFirst(): remove the element at the beginning of the linked list

     public E removeLast(): remove the end element of the linked list

     public E pop(): Pop an element from the stack represented by this list

     public boolean isEmpty(): Determine whether the linked list is empty

     Note: Prevent NoSuchElementException

  3. Vector: can realize the growth of the object array, this realization is synchronous

Set interface

The java.util.Set interface inherits from the Collection interface and is an important branch of a single-column set

• Features:
  1. Do not allow storage of duplicate elements
  2. There is no index and no method with index

• Set implementation class

  1. HashSet: is an unordered set, the bottom layer is a hash table structure (very fast query speed)

     Hash value: is an integer, directly given by the system, in the Object class int hashCode() can get the hash value of the object

     Hash table structure: array after JDK1.8++ red-black tree, group elements (the same hash value is a group), red-black tree connects a group of elements together

     The add method will call the hashcode and equals methods. When storing custom elements, the hashcode and equals methods must be rewritten

  2. LinkedHashSet: inherits the HashSet class, has the realization of the hash table and linked list of the Set interface with predictable iteration order

     One more linked list (the storage order of the record elements) to ensure the order of the elements

• variable parameter

  New features after JDK1.5+

  Modifier Return value type Method name (parameter type... formal parameter name) {
      Method body
  }
  

  Equivalent to

  Modifier Return value type Method name (parameter type [] formal parameter name) {
      Method body
  }
  

  Precautions:

  1. The parameter list of a method can only have one variable parameter

  2. If a method has multiple parameters, variable parameters must be written at the end of the parameter list

  3. Special wording of variable parameters

      public static void method(Object... obj){
          Method body
      }
     

Collections

java.utils.Collections is a collection tool class used to manipulate collection elements. Common methods are as follows:

• public static <T> boolean addAll(Collection<T> c, T... elements): add some elements to the collection
• public static void shuffle(List<?> list): 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 (ascending order)
• public static <T> void sort(List<T> list, Comparator<? Super T>): sort the elements in the collection according to the specified rules

note:

1. The prerequisite for the use of the sort method: the elements stored in the sorted collection must implement the Comparable interface, and override the compareTo method to define the sorting rules

2. Sorting rules: this-parameter->ascending order; parameter-this->descending order

3. Comparator can be written as an anonymous inner class

    Collections.sort(list,new Comparator<Student>(){
        @Override
        public int compare(Student o1,Student o2){
            Method body
        }
    })