Introduction: What is a data structure?

• Data structures are how computers store and organize data

• Linear structure: linear tables (arrays, linked lists, stacks, queues, hashes)

• Tree structure: binary tree, AVL tree, red black tree, B tree, heap, Huffman tree, and search set

• In the actual application, we should choose the appropriate data structure according to the actual application scenario

## 1. Array

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

• Array is stored in stack space
• The elements in an array hold heap space, and each element occupies 4 bytes
• Memory addresses are contiguous in the heap space

## 2. Dynamic arrays

• You can implement a dynamic array with an array, the memory of a dynamic array is changing and you can dynamically expand it
• Dynamic array can realize add, delete, change and check operations

### 2.1. Exposed interfaces for dynamic arrays

• External calls to the array’s common function interface

// 元素的数量 int size(); // 是否为空 boolean isEmpty(); // 是否包含某个元素 boolean contains(E element); // 添加元素到最后面 void add(E element); // 返回index位置对应的元素 E get(int index); // 设置index位置的元素 E set(int index, E element); // 往index位置添加元素 void add(int index, E element); // 删除index位置对应的元素 E remove(int index); // 查看元素的位置 int indexOf(E element); // 清除所有元素 void clear();

### 2.2. Design of dynamic arrays

• Creating a dynamic ArrayList starts with two elements:

• Size property: Manages the number of elements in an array

• Create the ArrayList

public class ArrayList { private int size; private E[] elements; }

• Initialize ArrayList, create size, elements, and set the initialization space of elements

public class ArrayList { private int size; private E[] elements; Private static final int CAPACITY_DEFAULT = 10; public ArrayList(int capacity) { capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity; elements = (E[]) new Object[capacity]; } // Default public ArrayList() {this(CAPACITY_DEFAULT); }}

## 3, the implementation of dynamic array

### 3.1. Number of elements

• We created the ArrayList and we already initialized size, so we just need to return the current size

``@return */ public int size() {return size; }Copy the code``

### 3.2, check whether the array is empty

• You can determine whether it is empty by judging the number of sizes

``Public Boolean isEmpty() {return size == 0; }Copy the code``

### 3.3, whether to contain an element

• When the element is present, you only need to determine if the index content is ELEMENT_NOT_FOUND = -1

/ * *

• Whether an element is contained
• @param element
• @return

*/ public boolean contains(E element) { return indexOf(element) ! = ELEMENT_NOT_FOUND; }

• When we add elements, we add them at the end of the array.
• The index of the newly added element is ** the length of the current array, **size is the length of the current array, so place the newly added element at the size index, then size plus 1

``````public void add(E element) {
elements[size] = element;
size++;
}
Copy the code``````

### 3.5, query elements by index

• When querying the index, check whether the index exceeds the boundary and directly fetch the element corresponding to the index

``public E get(int index) { rangeCheck(index); return elements[index]; } / / prompt output error private void outOfBounds (int index) {throw new IndexOutOfBoundsException (" index: "+ index +", Size:" + size); } / / check if the index cross-border private void rangeCheck (int index) {if (index < 0 | | index > = size) {outOfBounds (index); }}Copy the code``

### 3.6, set the element at index position

• Gets the index location element for replacement

Public E set(int index, E element) {public E set(int index, E element) { E oldElement = elements[index]; Elements [index] = element; // return oldElement; }

### 3.7, the element added at index position

• The arrayList originally has five elements, with a new element at index=2. I’m going to move 55, which was index=4, to index=5, and I’m going to move it to the right

• Note: When inserting, the last element is moved first to prevent the element from being overwritten

``Public void add(int index, E element) {// Move the element backwards for (int I = size-1; i >= index; i--) { elements[i + 1] = elements[i]; } // Insert elements; // size+1 size++; }Copy the code``
• Note: Insert elements can also be inserted in the last position, index=size

Public void rangeCheckForAdd (int index) {/ / when the index is less than zero or greater than the size An exception is thrown if (index < 0 | | index > size) {throw new IndexOutOfBoundsException(“Index:” + index + “, Size:” + size); }}

### 3.8, delete the element corresponding to index

• The arrayList has 7 elements, and the elements with index=3 need to be removed. The elements with index 4, 5, and 6 need to be moved to the left in that order
• Get rid of the last element, size minus 1

``Public E remove(int index) {// Check whether the index exceeds the rangeCheck(index); E element = elements[index]; For (int I = index; i < size - 1; i++) { elements[i] = elements[i + 1]; Elements [--size] = null; // Return element for the deleted element; } // private void rangeCheck(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index:"  + index + ", Size:" + size); }}Copy the code``
• Note: The passed index must not be greater than or equal to size

### 3.9, View the position of the element

• First, check whether the incoming element is NULL or not, and return the corresponding index by traversing the elements for comparison

private static final int ELEMENT_ON_FOUND = -1; public int indexOf(E element) { if (element == null) { for (int i = 0; i < size; i++) { if (elements[i] == null) return i; } }else { for (int i = 0; i < size; i++) { if (element.equals(elements[i])) return i; } } return ELEMENT_ON_FOUND; }

### 3.10, Empty the array

• Clear the corresponding element by iterating through the index, and set size to 0

Public void clear() {// Clear the stored data for (int I = 0; i < size; i++) { elements[i] = null; } // set size to 0; }

### 3.11. Array expansion

• Because the original array space is fixed, when the element is full, it needs to be expanded.
• Array expansion: The original oldArray cannot be expanded. Copy the original oldArray array into newArray and expand the newArray
• Move oldArray’s data to the corresponding newArray, and the pointer to Elements points to newArray

``Private void ensureCapacity() {// Obtain the current capacity of the array int oldCapacity = contact.length; // If (size < oldCapacity) return if (size < oldCapacity) return; Int newCapacity = oldCapacity + (oldCapacity >> 1); // Create a new array E[] newElements = (E[]) new Object[newCapacity]; For (int I = 0; i < size; i++) { newElements[i] = elements[i]; } // reference new array elements = newElements; }Copy the code``