The introduction

Data structures are the way computers store and organize data. Common data structures are:

(1) Linear structure

For example: linear table (including: array, linked list, stack, queue, hash table).

(2) Tree structure

For example: binary tree, AVL tree, red black tree, B tree, heap, Trie, Huffman tree, and search set.

(3) Graphic structure

Such as: adjacency matrix, adjacency list.

Note: In practical application, the most appropriate data structure should be selected according to the application scenario.

The linear table

(1) A linear list is a finite sequence with n (n>=0) elements of the same type. As shown below:

• Each element has an index that can be used to find the corresponding element.

• Is the first node (the first element),Is the tail node (tail element).

• isThe precursor,isSubsequent.

(2) Common linear tables are: array, linked list, stack, queue, hash table (also known as “hash table”).

Linear tables – “dynamic arrays”

1. Array

An array is a linear list of sequentially stored elements with contiguous memory addresses.

Example: Create an array named array using Java.

public static void main(String[] args) {
	int[] array = new int[] {11.22.33};
}
Copy the code

In memory, the local array variable is stored on the stack, and the elements of the new array are sequentially stored in the heap. As shown below:

In many programming languages, arrays have a fatal drawback: they cannot change their capacity dynamically.

In real development, we tend to want the size of an array to change dynamically. To solve this problem, we usually wrap a dynamic array ourselves.

2. Design of Dynamic Array

(1) Structure design of class

Before programming, we need to design the structure of the dynamic Array class (ArrayList). As shown below:

The members of the dynamic array class include:

• The number of elements in an array. //private int size;

Size = Number of elements = Array length ≤ Array capacity

• A variable used to hold an array. //private int[] elements;

• Constructors (visible and invisible parameters)

Using the constructor, we can initialize the capacity of a dynamic array when we create it. On the one hand, we need to build a constructor with parameters to let the user define the capacity of the dynamic array. On the other hand, we will also build a constructor for invisible parameters to handle the case when the user does not define the capacity of the dynamic array.

• Destructors (not available in the Java language)

• The interface function

(2) Interface design

• int size(); // The number of elements
• boolean isEmpty(); // Whether it is empty
• boolean contains(E element); // Whether to contain an element
• E get(int index); // Get the element corresponding to the index position
• E set(int index, E element); // Set the element at index position (override)
• void add(E element); // Add the element to the tail
• void add(int index, E element); // Add the element at index
• E remove(int index); // Delete the element corresponding to the index position
• int indexOf(E element); // View the position of the element
• void clear(); // Clear all elements

Note: Interfaces are called externally by objects, so they should be public members.

3, the implementation of dynamic array

3.1 Programming Implementation

Create a new project where:

1. Create a class named ArrayList (package name: com.atangbiji) to implement the dynamic array.

2. Create a new class named Main (package name: com.atangbiji) to call (test) its own wrapped dynamic array.

Note: The ArrayList class is already wrapped for us in Java. When we call ArrayList, we are prompted for two ArrayList classes, as shown in the figure below. To test the data structure we wrote, at this point we should select the package named com.atangbiji.

3. Let’s consider an array whose elements are all integers. (To be gradually improved on this basis later)

(1) Define private member variables

ArrayList. Java file:

private int size;	// The number of elements in the array
private int[] elements;	// Hold the array variable
Copy the code

(2) Create constructor

ArrayList. Java file:

private static final int DEFAULT_CAPACITY =  10; // Default capacity
/* * constructor * @param capacity Initial capacity * @return * */
public ArrayList(int capacity) {
	capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;// Boundary condition processing
	elements = new int[capacity]; // Create a dynamic array
}
public ArrayList(a) {
	this(DEFAULT_CAPACITY);// Call the constructor of the corporeal parameter
}
Copy the code

Create a dynamic array in the constructor. When the user defines the capacity of a dynamic array, the system calls the constructor with parameters to create an array of capacity. When the user does not define the capacity of the dynamic array, the constructor of the invisible parameter is called. The system creates the array with the default capacity.

Note: a. We set the default capacity to the private static constant DEFAULT_CAPACITY. Among them:

• Static is static. Ensure that there is only one value of a variable.

• Final is a constant, similar to const in C++.

B. Calls between constructors in Java are done using this object.

C. If the user-defined capacity is smaller than the default value, we still create an array of default capacities.

(3) Implement the “SIZE ()” interface

ArrayList. Java file:

/* * Number of elements * @param * @return * */
public int size(a) {
	return size;	// Return the size member variable
}
Copy the code

(4) Implement “isEmpty()” interface

ArrayList. Java file:

/* * Is empty * @param * @return * */
public boolean isEmpty(a) {
	return size == 0;	//size = 0; otherwise, not null
}
Copy the code

(5) Implement the “GET (int Index)” interface

This function simply fetches the corresponding element from the member variable Elements based on the index. Note that we need to process the index boundary condition before we get the element. To make the program friendlier, we’ll throw an exception if index is out of bounds.

Dynamic arrays fetch elements very quickly with O(1) time complexity.

ArrayList. Java file:

* @param: index * @return * */
public int get(int index) {
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	return elements[index];
}
Copy the code

(6) Implement “set(int index, int Element)” interface

ArrayList. Java file:

* @param: element * @param: Element * @return: original element * */
public int set(int index, int element) {
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	
	int old = elements[index];
	elements[index] = element;
	
	return old;
}
Copy the code

(7) Implement “indexOf(int Element)” interface

Iterate through the array to determine if the element exists in the array. If yes, return the index. If not, return -1.

ArrayList. Java file:

private static final int ELEMENT_NOT_FOUND = -1; / / was not found
* @param: element * @return: element * */
public int indexOf(int element) {
	// go through the number group
	for (int i = 0; i < size; i++) {
		if(elements[i] == element)
		{
			returni; }}return ELEMENT_NOT_FOUND;
}
Copy the code

(8) implement the “Contains (int Element)” interface

Looks for the element in the array. If -1 is not returned, the element exists.

ArrayList. Java file:

/* * Contains an element * @param: Element * @return * */
public boolean contains(int element) {
	returnindexOf(element) ! = ELEMENT_NOT_FOUND; }Copy the code

(9) Implement the “Clear ()” interface

To clear the array, you don’t need to free up memory, just set size = 0. At this point, the memory allocated for the array is still there and can be reused later by the array object.

Note: Frequently allocating and freeing memory space is a waste of time (performance).

ArrayList. Java file:

/* * Clear all elements * @param * @return * */
public void clear(a) {
	size = 0;	// There is no need to free array memory
}
Copy the code

(10) Implement the “Remove (int Index)” interface

To delete the index element, simply move the subsequent elements one bit from front to back. That is, move the element corresponding to index+1 to index, and so on.

ArrayList. Java file:

* @param: index * @return: deleted element * */
public int remove(int index) {
	// Check whether it is valid
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	
	int old = elements[index];
	// Loop move
	for (int i = index + 1; i < size; i++) {
		elements[i - 1] = elements[i];
	}
	size --;
	
	return old;
}
Copy the code

(11) ★ Implement “Add (int index,int Element)” interface

1. When size is less than capacity

To add an element to index, simply move the next element back one bit until the index position is empty.

Note: the order of movement cannot be reversed.

ArrayList. Java file:

/* * Add element * @param: index * @param: Element * @return * */
public void add(int index,int element) {
	// Check whether it is valid
	if (index < 0 || index > size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	// loop from back to front
	for (int i = size - 1; i >= index; i--) {
		elements[i + 1] = elements[i];
	}
	elements[index] = element;
	size++;
}
Copy the code

Dynamic capacity

2. If size = capacity — Expand the capacity

When size=capacity, if we need to add new elements, we must expand the array first. Since memory is defined when we create an object, we can’t simply splice a chunk of memory at the end of the array to hold new elements.

Here’s what we do:

① Re-create a larger (e.g. 1.5 times) memory space; ② Move the array elements one by one to the new memory; The elements used to store the array point to the new memory space. ④ Free the previous array memory (Java garbage collection automatically).

Therefore, we need to make the following changes to the Add (int Index,int Element) interface.

ArrayList. Java file:

/* * Add element * @param: index * @param: Element * @return * */
public void add(int index,int element) {
	// Check whether it is valid
	if (index < 0 || index > size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	// Ensure sufficient capacity
	ensureCapacity(size + 1);
	// loop from back to front
	for (int i = size - 1; i >= index; i--) {
		elements[i + 1] = elements[i];
	}
	elements[index] = element;
	size++;
}

* @param: Capacity * @return * */
@SuppressWarnings("unchecked")/ / comment
private void ensureCapacity(int capacity) {
	
	// If the original array capacity is sufficient, return
	int oldCapacity = elements.length;
	if(oldCapacity >= capacity)
		return;
	// If the original array capacity is insufficient, expand it by 1.5 times
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	// Create new memory space
	int newElements[] = new int[newCapacity];
	// Move the elements one by one
	for (int i = 0; i < size; i++) {
		newElements[i] = elements[i];
	}
	// points to new memory
	elements = newElements;
	
	System.out.println("Capacity has been removed from" + oldCapacity + "Expand to" + newCapacity);
}
Copy the code

(12) Implement “add(int Element)” interface

The Add (Int Element) interface is a special case of add(int Index,int Element) interface. We just need to add a new element at size.

ArrayList. Java file:

/* * Add element to end * @param: Element * @return * */
public void add(int element) {
	add(size, element);
}
Copy the code

(13) Print all elements in the array

In Java, when we want to print an object, we do so internally by calling the toString() method. By default, print the class name of the object. To print all the elements in the array of objects, we simply override (also known as overwriting) the toString() method and concatenate the strings in it.

Note: The StringBuilder class is recommended for string concatenation in Java.

ArrayList. Java file:

/* * Prints all elements in an array: override toString() * @param * @return array elements * */
@Override
public String toString(a) {
	/ / new StringBuilder
	StringBuilder string = new StringBuilder();
	
	// Concatenates a string
	string.append("size = ").append(size).append("; [");
	for (int i = 0; i < size; i++) {
		string.append(elements[i]);
		
		if(i ! = size -1) {
			string.append(",");
		}
	}
	string.append("]");
	
	return string.toString();
}
Copy the code

3.2 Interface Test

Create a new ArrayList object in the Main class (main.java file) to test the dynamic array you have wrapped. This section only uses the interface of adding elements as an example to test. The testing methods of other interfaces are similar and will not be described here.

The Main. Java file:

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		// Dynamic array interface test
		ArrayList list = new ArrayList();
		
		for (int i = 0; i < 30; i++) { list.add(i); } System.out.println(list); }}Copy the code

Run the program and the output is:

4. Perfect dynamic arrays

4.1 Generics & Object arrays

Because we realize the dynamic array before only consider the array elements as integers, but in the actual application process, we often need to use the dynamic array storing decimal, object and other data types. Therefore, we need to “generalize” the data types that hold elements in the array.

Using generics makes dynamic arrays more versatile, allowing them to hold any data type. The steps to implement generics in Java include:

(1) Generalization in class definition. (Generalization class)

public class ArrayList<E> {}
Copy the code

Where: E is the name of the generalized type, which can be customized by using commonly used generic type variables.

Some common generic type variables:

• E: Element, mostly used in Java collections framework
• K: Key
• N: Number
• T: Type (Type)
• V: Value

(2) Generalize the member variables used to store arrays. (Generalizing member variables)

private E[] elements;	// Hold the array variable
Copy the code

(3) Generalize the data types of all elements in each method. (Generalized member functions) such as:

public void add(E element) {}
Copy the code

It is important to note that you cannot generalize arrays directly when you create them in Java. Elements = new E[capacity]; Is wrong. Since all classes in Java eventually inherit from the Object class, we can generalize the types of array elements by first creating an array of objects and then casting it to a generic array. That is:

elements = (E[]) new Object[capacity]; // Create a dynamic array
Copy the code

Note: There will be a warning. Press Ctrl + 1 and select unCheck from the pop-up menu. The system automatically generates the @SuppressWarnings(” Unchecked “) annotation.

To sum up, the arrayList.java file after the generics is:

package com.atangbiji;

@SuppressWarnings("unchecked")/ / comment

public class ArrayList<E> {
	
	private int size;	// The number of elements in the array
	private E[] elements;	// Hold the array variable
	
	// Note: static is static, ensure that the value of the variable is only one copy;
	//final is a constant, like const in C++
	private static final int DEFAULT_CAPACITY =  10; // Default capacity
	private static final int ELEMENT_NOT_FOUND = -1; / / was not found

	
	/* * constructor * @param capacity Initial capacity * @return * */
	public ArrayList(int capacity) {
		capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;// Boundary condition processing
		elements = (E[]) new Object[capacity]; // Create a dynamic array
	}
	public ArrayList(a) {
		this(DEFAULT_CAPACITY);// Call the constructor of the corporeal parameter
	}
	/* * Clear all elements * @param * @return * */
	public void clear(a) {
		size = 0;	// There is no need to free array memory
	}
	
	/* * Number of elements * @param * @return * */
	public int size(a) {
		return size;	// Return the size member variable
	}
	
	/* * Is empty * @param * @return * */
	public boolean isEmpty(a) {
		return size == 0;	//size = 0; otherwise, not null
	}
	
	/* * Add element to end * @param: Element * @return * */
	public void add(E element) {
		add(size, element);
	}
	
	* @param: index * @return * */
	public E get(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
		}
		return elements[index];
	}
	
	* @param: element * @param: Element * @return: original element * */
	public E set(int index, E element) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
		}
		
		E old = elements[index];
		elements[index] = element;
		
		return old;
	}
	
	/* * Add element * @param: index * @param: Element * @return * */
	public void add(int index,E element) {
		// Check whether it is valid
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
		}
		// Ensure sufficient capacity
		ensureCapacity(size + 1);
		// loop from back to front
		for (int i = size - 1; i >= index; i--) {
			elements[i + 1] = elements[i];
		}
		elements[index] = element;
		size++;
	}
	
	* @param: Capacity * @return * */
	private void ensureCapacity(int capacity) {
		
		// If the original array capacity is sufficient, return
		int oldCapacity = elements.length;
		if(oldCapacity >= capacity)
			return;
		// If the original array capacity is insufficient, expand it by 1.5 times
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		// Create new memory space
		E[] newElements = (E[]) new Object[newCapacity];
		// Move to elements one by one
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		// points to new memory
		elements = newElements;
		
		System.out.println("Capacity has been removed from" + oldCapacity + "Expand to" + newCapacity);
	}
	
	* @param: index * @return: deleted element * */
	public E remove(int index) {
		// Check whether it is valid
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
		}
		
		E old = elements[index];
		// Loop move
		for (int i = index + 1; i < size; i++) {
			elements[i - 1] = elements[i];
		}
		size --;
		
		return old;
	}
	
	* @param: element * @return: element * */
	public int indexOf(E element) {
		// go through the number group
		for (int i = 0; i < size; i++) {
			if(elements[i] == element)
			{
				returni; }}return ELEMENT_NOT_FOUND;
	}
	
	/* * Contains an element * @param: Element * @return * */
	public boolean contains(E element) {
		returnindexOf(element) ! = ELEMENT_NOT_FOUND; }/* * Prints all elements in an array: override toString() * @param * @return array elements * */
	@Override
	public String toString(a) {
		/ / new StringBuilder
		StringBuilder string = new StringBuilder();
		
		// Concatenates a string
		string.append("size = ").append(size).append("; [");
		for (int i = 0; i < size; i++) {
			string.append(elements[i]);
			
			if(i ! = size -1) {
				string.append(",");
			}
		}
		string.append("]");
		
		returnstring.toString(); }}Copy the code

Ps: Generic interface testing

Create a new Person class, add member variables: age, name, and press Shift+Alt+S to quickly generate the constructor and toString() function from the pop-up menu.

Person. Java file:

package com.atangbiji;

public class Person {
	private int age;
	private String name;
	
	// constructor
	public Person(int age, String name) {
		this.age = age;
		this.name = name;
	}

	@Override
	public String toString(a) {
		return "Person [age=" + age + ", name=" + name + "]"; }}Copy the code

Create an array of objects with elements as Person objects in the main.java file and test the dynamic array interface after generalization. This section only uses the interface of adding elements as an example to test. The testing methods of other interfaces are similar and will not be described here.

The Main. Java file:

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		// Dynamic array interface test
		// Array of objects
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10."Tom"));
		persons.add(new Person(12."Jack"));
		persons.add(new Person(15."Rose"));
		
		System.out.println(persons);
		
		// Array of integers (wrapper class for Integer)
		ArrayList<Integer> ints = new ArrayList<>();
		
		for (int i = 0; i < 30; i++) { ints.add(i); } System.out.println(ints); }}Copy the code

Run the program and the output is:

Thus, the generalized dynamic array can hold elements of various data types.

Note: The generalized data structure cannot store the basic data type directly. In this case, we need to use the corresponding wrapper class. The following table describes the eight basic data types provided in Java and their corresponding wrapper classes.

4.2 Object array memory management

A generically completed dynamic array can store both primitive data types and reference types (objects).

(1) If the array elements are primitive data types, the array memory stores the data itself.

(2) If the elements of an array are objects of a class, the memory of the array contains references to each object.

Note: When an object (or objects) in an array is no longer in use, we need to actively free the memory space occupied by that object (or objects). That is, we need to set the address of the deleted object in the object array to NULL. Every advantage has a disadvantage.

Therefore, we also need to improve the following interface of the ArrayList class.

4.3 Perfecting Interfaces

(1) Perfect the Clear () interface

ArrayList. Java file:

/* * Clear all elements * @param * @return * */
public void clear(a) {
	for (int i = 0; i < size; i++) {
		elements[i] = null;	// Actively free the memory space occupied by the deleted objects in the array
	}
	size = 0;	// There is no need to free array memory
}
Copy the code

Note: We only clear the object to which the address in the array points, not the array itself.

Attachment: improve the post-interface test

To prove that the improved interface really frees the memory space of the deleted objects, we can use Java’s finalize() method to test, and we can leave the “last words” of objects before they die in this method.

Person. Java file:

@Override
protected void finalize(a) throws Throwable {
	// TODO Auto-generated method stub
	super.finalize();
	
	System.out.println("Memory space of the deleted object has been freed");
}
Copy the code

Note: finalize() is similar to the destructor in C++.

The Main. Java file:

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		// Dynamic array interface test
		// Array of objects
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10."Tom"));
		persons.add(new Person(12."Jack"));
		persons.add(new Person(15."Rose"));
		
		persons.clear();
		// Remind the JVM to do garbage collectionSystem.gc(); System.out.println(persons); }}Copy the code

Run the program and the output is:

If the clear() interface is restored to the state before perfection and the program is run again, the output result is:

Therefore, the improved dynamic array will actively release the memory space occupied by the deleted object, and the system performance is better.

(2) Improve the Remove (int Index) interface

Similarly, for the remove(int index) interface, when we delete the index corresponding element, the original memory space of the last element must also be actively emptied, otherwise the last element in the object array cannot be completely deleted.

ArrayList. Java file:

* @param: index * @return: deleted element * */
public E remove(int index) {
	// Check whether it is valid
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	
	E old = elements[index];
	// Loop move
	for (int i = index + 1; i < size; i++) {
		elements[i - 1] = elements[i];
	}
	size --;
	
	elements[size] = null;// Empty the last element of the dynamic array
	
	return old;
}
Copy the code

(3) Improve the “indexOf(E Element)” interface

① Equals (Object obj

The previous method of obtaining the element ordinal number is done by comparing elements for equality. When the array elements are numbers, we can use “==” to determine whether they are equal. Since object arrays hold references (addresses) to objects, how can two objects be compared for equality when the element type is object?

In Java, we generally do not recommend comparing memory addresses to be equal. Instead, we override equals(Object obj) and define the condition that two objects are equal inside. For example, here we can customize: Two Person objects are considered equal when their age and name are equal. The specific code is as follows:

Person. Java file:

@Override
public boolean equals(Object obj) {
	Person person = (Person)obj;
	When the age and name of two people are equal, we consider the two Person objects to be equal
	return (this.age == person.age)&&(this.name.equals(person.name));
}
Copy the code

The equals method is overridden by default in the Integer class, where two elements are equal for numeric equality. Therefore, to make the indexOf(E Element) interface more generic, we need to optimize it as follows:

ArrayList. Java file:

* @param: element * @return: element * */
public int indexOf(E element) {
	// go through the number group
	for (int i = 0; i < size; i++) {
		if(elements[i].equals(element))
		{
			returni; }}return ELEMENT_NOT_FOUND;
}
Copy the code

Object1. Equals (Object2) = Object1. Equals (Object2) = Object1.

At this point, the interface can be used for both primitive data types and object types of array elements.

(2) Null handling

Does the dynamic array we designed allow null array elements? Let’s test:

The Main. Java file:

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		// Dynamic array interface test
		// Array of objects
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10."Tom"));
		persons.add(new Person(12."Jack"));
		persons.add(new Person(15."Rose"));
		persons.add(null); System.out.println(persons); }}Copy the code

Run the program and the output is:

As you can see, the dynamic array we designed earlier allows array elements to be null.

Note: In general, dynamic arrays in Java also allow empty elements.

Methods cannot be called because of null elements. If elements[I] = null, elements[I].equals() is null. Therefore, in order for dynamic arrays to handle null elements better, we need to optimize the indexOf(E Element) interface further.

ArrayList. Java file:

* @param: element * @return: element * */
public int indexOf(E element) {
	// If the element is null
	if (element == null) {
		// go through the number group
		for (int i = 0; i < size; i++) {
			Elements [I] may or may not be null.
			if (elements[i] == null) {
				returni; }}}else {
		// If the element is not null.
		// go through the number group
		for (int i = 0; i < size; i++) {
			Elements [I] may or may not be null.
			if(element.equals(elements[i]))
			{
				returni; }}}return ELEMENT_NOT_FOUND;
}
Copy the code

Attachment: improve the post-interface test

The Main. Java file:

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		// Dynamic array interface test
		// Array of objects
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10."Tom"));
		persons.add(new Person(12."Jack"));
		persons.add(new Person(15."Rose"));
		persons.add(null);
		persons.add(new Person(12."Jack"));
		persons.add(null);
		
		System.out.println(persons);
		
		Person person = new Person(12."Jack");
		System.out.println(The index of the first Jack in the dynamic array is: + persons.indexOf(person) + ".");
		
		System.out.println(The index of the first empty element in the dynamic array is: + persons.indexOf(null) + "."); }}Copy the code

Run the program and the output is:

(4) Shrinkage

① Remove (int index) shrinks the capacity

When the data size is large, expanding the dynamic array may have more free space. If memory usage is tight, we can consider reducing the size of the dynamic array.

The capacity reduction and capacity expansion operations are similar. Both are: ① open up a new memory space; ② Then move the array elements one by one to the new memory; The elements used to store the array point to the new memory space. ④ Free the previous array memory (Java garbage collection automatically). However, the expansion of the new open up more memory space, shrinking the new open up less memory space.

We mainly consider whether to shrink after deleting elements. (Here we consider that when “free space > total capacity /2”, we reduce it. Of course, we don’t want the size of the array to be too small, so the size of the array is no less than the default size.

ArrayList. Java file:

* @param: index * @return: deleted element * */
public E remove(int index) {
	// Check whether it is valid
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("Index error, Index =" + index +"; Size =" + size);	// Throw an exception
	}
	
	E old = elements[index];
	// Loop move
	for (int i = index + 1; i < size; i++) {
		elements[i - 1] = elements[i];
	}
	size --;
	
	elements[size] = null;// Empty the last element of the dynamic array
	
	// Determine whether the dynamic array needs to be shrunk
	trim();
	
	return old;
}

/* * Dynamic array shrink * @param * @return * */
private void trim(a) {
	// Array capacity
	int oldCapacity = elements.length;
	// When the free space of the array exceeds half of the total capacity, it is reduced
	// The size of the array must be no smaller than the default size
	if (size < (oldCapacity >> 1) && oldCapacity > DEFAULT_CAPACITY) 
	{
		// If the original array capacity is sufficient, reduce the size by 0.5 times
		int newCapacity = oldCapacity >> 1;
		// Create new memory space
		E[] newElements = (E[]) new Object[newCapacity];
		// Move to elements one by one
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		// points to new memory
		elements = newElements;
		
		System.out.println("Capacity has been removed from" + oldCapacity + "Shrink to"+ newCapacity); }}Copy the code

Attached: dynamic array reduction test

The Main. Java file:

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		// Dynamic array shrink test
		ArrayList<Integer> list = new ArrayList<>();
		
		/ / add
		for (int i = 0; i < 40; i++) {
			list.add(i);
		}
		
		System.out.println(list);
		
		/ / delete
		for (int i = 0; i < 40; i++) {
			list.remove(0); } System.out.println(list); }}Copy the code

Run the program and the output is:

② Complexity oscillation (grasp the conclusion)

** Note: ** If the expansion multiple and reduction timing are not properly designed, complexity oscillations may occur.

For example: if we set the dynamic array expansion array capacity ×2; If free space is greater than or equal to total capacity /2, the dynamic array shrinks. Then: When the capacity of the array is N and the number of elements in the array is n (that is, it is just full), if we add another element to the array at this time, the expansion operation will be triggered. If we then remove the newly added element from the array, the shrink operation is triggered again. If you perform the above two steps repeatedly, the dynamic array will be expanded and shrunk repeatedly. In this case, the time complexity of each step is O(n). This is contrary to the fact that in most cases, it takes n operations to add (or delete) elements to the end of the array before the time complexity of one operation is O(n) and the time complexity of the other operations is O(1). This sudden condition is called “complexity shock”.

Note: We only need to set “capacity expansion multiple × capacity reduction condition ≠1” to avoid complexity shock. Here we have 1.5×0.5≠1, so there is no complexity oscillation.

③ Shrink when clear()

You are advised to shrink the dynamic array after clearing it. If the array length is greater than the default size, the array length will be automatically reduced to the default size.

ArrayList. Java file:

/* * Clear all elements * @param * @return * */
public void clear(a) {
	for (int i = 0; i < size; i++) {
		elements[i] = null;	// Actively free the memory space occupied by the deleted objects in the array
	}
	size = 0;	// There is no need to free array memory
	
	// If the array length is greater than the default capacity, the array length is automatically reduced to the default capacity
	if(elements ! =null && elements.length > DEFAULT_CAPACITY) {
		elements = (E[]) newObject[DEFAULT_CAPACITY]; }}Copy the code

5, java.util.ArrayList class source analysis

In fact, an ArrayList class is already wrapped for us in Java’s java.util package. By comparison, we can analyze that the dynamic array implemented by ourselves is almost the same as that provided by the official, but the official interface is richer, and we only implemented the commonly used add, delete, change and check interface.

6. Time complexity analysis of dynamic array

In general, the runtime we refer to is the worst-case code runtime.

Sometimes the time complexity of a piece of code varies from case to case. To describe the different time complexities of the code in different cases, we introduce the best, worst, average, and amortized time complexities.

(1) Best Case Time complexity

In the best case, the time complexity of executing this code.

(2) Worst case time complexity

In the worst case, the time complexity of executing this code.

(3) Average Case Time complexity

That is, the average time complexity. (also known as “weighted average time complexity” and “expected time complexity”)

• Average case time complexity = sum of execution times for various cases ÷ total cases

For example, due to the different positions of dynamic array inserts and deletes, the time complexity will be different in order of magnitude. In this case, we need to consider the average case time complexity.

Because best – and worst-case complexity is extreme, the probability of occurrence is not great. Therefore, the average case time complexity is the more meaningful of all cases.

Note: In most cases, we do not need to distinguish between best-case, worst-case, and average-case time complexity. In order to describe the time complexity of the code more effectively, we will distinguish the three cases only when the time complexity of the same code in different cases has a difference of magnitude.

(4) Amortized Time complexity

Amortized complexity is a more advanced concept. It is a special case and applies to more specific and limited scenarios.

For example, for the “Add (int Element)” interface, since most of the cases are size < capacity, the new element is directly added at the end of the array, and the time complexity is O(1). However, when the array space runs out, size=capacity, if a new element is added, it needs to be expanded, so that the time complexity of this element will jump to O(n), then back to O(1), and so on. It is more reasonable to use the amortized complexity to describe the complexity of the algorithm for the function with abrupt execution time in some special cases. That is, the execution time of this mutation is evenly amortized over each call (in general, amortized complexity = best-case complexity). (It’s as if the bigwigs’ incomes are being averaged!)

In the process of repeated execution of a certain code, if the time complexity of a certain execution has a sudden change. That is, when a set of operations have a sequential sequential relationship, the time complexity is low in most cases, and high only in a few cases. At this point, if we analyze this group of operations together and amortize the execution time of this mutation to each call, it will be more reasonable to use the amortized complexity to describe the time complexity of the algorithm. Because there are too many places to go, the time complexity of general amortization is equal to the time complexity of the best case.

Note: In fact, we can further optimize the add(int index,int Element) and remove(int index) interfaces for dynamic arrays. Specific optimization ideas and implementation process we will explain in the back of the learning cycle queue, the knowledge can understand.

7,

(1) Advantages of dynamic array:

• It can hold both basic data types and objects of classes.
• You can dynamically expand capacity.
• Rank based access, random access is very fast. (Save time)

(2) Disadvantages of dynamic array:

• (size<=capacity) (size<=capacity) (Memory utilization is generally less than 100%)

(The series of blog posts will continue to be updated after this lecture.)

---

References:

• Fall in love with Data Structures and Algorithms by MJ
• Data Structures and Algorithms, Deng Junhui

---

How do I get the source code?

Follow the wechat public account of “Atang Handwriting” and reply the key words “Data structure and algorithm design and implementation” in the background to obtain the source code of the project.

Blogger’s latest posts on personal blogwww.atangbiji.com/Release.