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

  • Graph structure: adjacency matrix, adjacency list

  • 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

  • Elements property: Used to manage access to array elements

  • 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; }

3.4. Add elements

  • 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