Basic data structure

An array of

Concept: a linear table data structure. It uses a continuous set of memory Spaces to store a set of data of the same type.

  • What is a linear list: it’s a linear structure, a long list.

  • Continuous space and the same data type

Because of these features, the address of a node can be calculated directlya[i]_address = base_address + i * data_type_sizeSo arrays have a killer feature random access

To find the

The time complexity of the array is O(1) based on the subscript lookup, because the addresses of the array elements can be computed using the public representation

Because of the CPU’s caching mechanism, contiguous Spaces are cached, so arrays are more efficient to access than linked lists

Therefore, the query efficiency is high

Insert and Delete

Every time you insert or delete, you need to maintain all the subscripts after you change the current subscript, so the time complexity is O(n).

In fact, in some special cases, we don’t necessarily want to pursue the continuity of the data in the array. Wouldn’t deletion be much more efficient if we lumped multiple deletions together? That is, every time we delete it, we just mark it as deleted, rather than actually deleting it. When the memory is insufficient, delete it in a unified manner

The idea is similar to the mark-clean algorithm in the JVM’s garbage collection, where the mark is checked in the first pass and the garbage object is cleared in the second. For the JVM, however, this markup clearness is equivalent to markup defragmentation, which can result in insufficient memory to store large objects

The bottom layer of ArrayList is a dynamically growing array

  • The orderly
  • repeatable
  • The linear table
  • The capacity can be dynamically expanded

Each capacity expansion expands the memory to 1.5 times the original size. Expansion requires copying the original collection elements into a new memory space, which is time-consuming

And array

  1. Methods that encapsulate some basic operations, such as inserting or deleting operations that require moving other data
  2. Dynamic Capacity Expansion

Disadvantages relative to arrays:

  1. You cannot store basic data types such as int and long. You need to use their encapsulation classes Integer and long. But the Autoboxing, Unboxing encapsulated classes have a performance cost

The list

Learn from the beauty of data structures and algorithms

Concept: A linked list is a series of scattered memory blocks through Pointers. Memory space is discontinuous. Because there is no size limit, there is natural support for “dynamic scaling” (even dynamic scaling of ArrayList is time-consuming to copy the original data to another memory space).

  • Singly linked list: The head pointer records the base address of the list, and the tail pointer points to an empty address NULL
  • Two-way linked list
  • Circular lists: Relative to singly linked lists, the tail pointer points to the head node. The nice thing about circular lists is that the tail points to the head so when you’re dealing with data structures that have loops, it’s a little bit cleaner than that

To find the

The search of each node, whether using subscript search or value search, needs to be obtained node by node. Therefore, the search operation of linked list is complex, and the time complexity is O(n).

Delete and Insert

When the address information of the node concerned has been determined, the time complexity of deletion and insertion is O(1), because only the address space of the previous pointer and the next pointer needs to be modified. However, similar to the single linked list insertion operation, first you have to find the subscript where the current value needs to be inserted, and then you need to obtain the address information of the previous node and the next node according to this subscript position. To complete

Two-way Linked list (space for time)

  • More address space, with front and back Pointers, than a single linked list that stores the same data.
  • However, the data of the former node can be obtained at O(1) time complexity. Therefore, insert and delete operations do not need to do an additional step of addressing operations, compared to the single linked list insert and delete operations are faster
  • In certain cases, the query is faster, and the search can also be judged according to the value of the last search to determine whether to search forward or backward, so as to improve the query efficiency

Java LinkedList, LinkedHashMap are two-way linked lists

The stack

Features:

  1. Last in, first out

The stack structure is preferred when a data set involves inserting and deleting data only on one end and is last in, first out, first in, last out.

A stack can be implemented as either an array or a linked list. The stack implemented by arrays is called a sequential stack, and the stack implemented by linked lists is called a chained stack.

// Sequential stack based on array implementation
public class ArrayStack {
  private String[] items;  / / array
  private int count;       // The number of elements in the stack
  private int n;           // Stack size

  // Initialize the array and request an array of size n
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // Push the stack
  public boolean push(String item) {
    // If the array is empty, return false.
    if (count == n) return false;
    // Put the item at the subindex count and add one to the count
    items[count] = item;
    ++count;
    return true;
  }
  
  // Exit the stack
  public String pop(a) {
    // If the stack is empty, null is returned
    if (count == 0) return null;
    // Return array elements with subindex count-1 and count of stack elements minus one
    String tmp = items[count-1];
    --count;
    returntmp; }}Copy the code

The time complexity is O(1) because it is only the operation of the data on the top of the stack. The space complexity (calculating the space complexity refers to the space consumed by removing the original storage, such as temporary variables) is also O(1).

If dynamic expansion is supported, you only need to change the original array to an array that supports dynamic expansion (ArrayList). In fact, dynamic expansion is to apply for a new area to copy data when certain requirements are met

The queue

First in, first out, add elements at the end of the queue, remove elements at the first

Those implemented using arrays are called sequential queues, and those implemented using linked lists are called chained queues


// Queue with array
public class ArrayQueue {
  // Array: items, array size: n
  private String[] items;
  private int n = 0;
  // Head indicates the head index and tail indicates the tail index
  private int head = 0;
  private int tail = 0;

  // Apply for an array of size capacity
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  / / team
  public boolean enqueue(String item) {
    // If tail == n indicates that the queue is full
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  / / out of the team
  public String dequeue(a) {
    // If head == tail, the queue is empty
    if (head == tail) return null;
    // In order to make it more clear for students from other languages, I put the -- operation on a separate line
    String ret = items[head];
    ++head;
    returnret; }}Copy the code

Array code to implement the principle of queue

  1. There are only top operations relative to the stack, and the queue needs two operations, so two Pointers head and tail are needed
  2. When you join a queue, don’t move the head, just move the tail. Insert several data tail changes several times
  3. When you leave the queue,head moves, delete a few data to move several times

In fact, we can leave the team without having to move data. If there is no free space, we only need to join the queue, and then trigger a data migration operation.


   // Put the item at the end of the queue
  public boolean enqueue(String item) {
    // tail == n indicates that there is no space at the end of the queue
    if (tail == n) {
      // tail ==n && head==0, indicating that the entire queue is full
      if (head == 0) return false;
      // Data is moved
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // Update head and tail after the move
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }
Copy the code

As you can see, each deletion only leaves the header element empty, but the array still has elements. Only when the insert operation is performed, the original information will be reordered, and the whole will be copied and shifted

List code to implement the principle of queue

  1. You also need two Pointers,head and tail
  2. Tail ->next= new_node, tail = tail->next; Head = head->next.

Circular queue

//TODO is not understood

Blocking queues and concurrent queues

//TODO

List the code

1.1 Tip 1: Understand the concepts of Pointers and references

Pointers (C, C++, Go) and references (Python, Java) are both meant to store the memory address of the object to which they are pointing

When you assign a variable to a pointer, you actually assign the address of that variable to the pointer, or conversely, the pointer stores the memory address of that variable, points to that variable, and that variable is found through the pointer.

When writing linked list code, we often have this code: p->next=q. This line of code says that the next pointer in node P stores the memory address of node Q. There is a more complex one, which we often use when writing linked list code: p->next=p->next->next. This line of code says that the next pointer to node p stores the memory address of the node next to node p.Copy the code

1.2 Tip two: vigilance pointer loss and memory leak

When we insert nodes, we must pay attention to the order of operation. We must first point the next pointer of node X to node B, and then point the next pointer of node A to node X, so as not to lose the pointer and cause memory leak.

For example, if the next pointer of a stores the memory address of x, then the next pointer of A will not be able to find b, so the x line cannot be used again

1.3 Tip 3: Use sentry to simplify the difficulty of implementation

Insertion of a linked list

new_node->next=p->next p-next->new_node 1. (p->next and now_node->nex both store the same memory address and point to the same value.) The memory address of new_node is stored with p-next, which is equivalent to p-next=new_node, new_node-> the next node, thus the node insertion operation is implementedCopy the code

Insert a node at the beginning of the list

if (head == null) {
  head = new_node;
}
Copy the code

A node was deleted from the linked list

p->next = p->next->next;
Copy the code

Delete the last node

if (head->next == null) {
   head = null;
}
Copy the code

So the sentinels are really designed to solve this kind of border problem

The idea is to add a sentinel node to each list header. This sentinel node doesn’t store any data, it just sits there. All insertions and deletions can be implemented in one set of code

1.4 Skill four: focus on boundary conditions

Some of the boundary conditions I often use to check that my linked list code is correct are:

  1. Does the code work if the list is empty?
  2. Does the code work if the list contains only one node?
  3. Does the code work if the list contains only two nodes?
  4. Does the code logic work when dealing with the head and tail nodes?

1.5 Technique five: illustrations to help thinking

The attached

1. Two-dimensional arrays

The indices of a two-dimensional array are retrieved by dimension. Such as

A = new int int [] [] [] [] {{1, 2, 3, 4}, {null, 2,3,1}, {1}} a [1] [2] is obtained the second external third numerical arraysCopy the code

2. Why do array indices start at 0

Reason 1: Addressing formula: A [I]_address = base_address + I * datA_TYPE_size If the subscript starts from 1, then the addressing formula needs to be: A [I]_address = base_address + (i-1) * data_type_size. Therefore: the system needs one more step subtraction operation. Secondly, it’s possible that the designer started the array from this formula, so the formula doesn’t do I minus one and then the subscript has to do an operation from zero to satisfy the formula

Reason two: when other languages were developed, the C language was used to start with the subscript 0.

3. Addressing two-dimensional arrays

For m * n array, a [I][j] (I < m,j < n) address is: address = base_address + (I * n + j) * type_size

4. LRU cache elimination algorithm based on linked list

  1. Create an ordered, singlelinked list structure that is traversed from scratch each time the cache data is retrieved
  2. If the data is in the linked list, delete the location data and add an identical data from the header
  3. If the data is not in the linked list
    1. If the list is not full, add a new data in the header
    2. When the list is full, the last piece of data in the tail is deleted and the query data is added from the header

5. How to move the browser forward and backward

Create two stacks X and y. The first viewed page is pushed onto stack X. When the backward operation is performed, the top page of stack X is taken out and pushed onto stack Y. When the forward operation is entered, the top of the stack Y is taken off and pushed onto the stack X.

backforwardCannot advance (stack Y has no data)

6. Queue-based implementation of thread pool blocking requests

What should the thread pool do when a new task requests thread resources when there are no idle threads in the thread pool? How are various processing strategies implemented?

The first is a non-blocking processing mode that rejects the task request directly. The other is the blocking method, which queues the requests until there is an idle thread, and then retrives the queued requests to continue processing. So how do you store queued requests?

  • Based on the linked list implementation, will achieve an unrestricted blocking thread pool, that is, unrestricted accumulation to wait. The new one has been waiting in line in the back
  • With an array implementation, you implement a concept that allows you to configure a maximum number of waiting links.

In most resource-limited scenarios where you need to wait, you can use queues to implement first-in, first-out