The linear table

The data in a linear table is arranged like a line. Each linear table has at most two directions: front and back. Arrays, linked lists, queues, stacks, and so on are all linear table structures.

An array of

An array is a linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type.

Contiguous memory space means that all elements in the array are stored together, and data of the same type means that each element occupies the same amount of space. Both of these conditions are guaranteed to allow random access (that is, access to any value in the array at O(1) complexity). For example:

int[] val = new int[100];

// We assume that the first address of the val array is 100 and that the int takes up 4 bytes
// if a[3] starts with 100+3*4=112, the address ranges from 112 to 115
Copy the code

It is these two factors that make many operations on arrays very inefficient. For example, insert and delete operations require a large amount of data movement to ensure continuity. For example, if the current array has n elements and we want to insert an element at position 2, all data from position 2 needs to be moved one bit further back.

The complexity of the

1. Insert: O (n)
2. Delete: O (n)
3. Change: O (1)
4. Random access: O(1)

Optimization idea

An insert operation on an array

If we want to insert val at inx of length n without having to keep the array ordered, then we can assign the value at inx to n, and then assign val to inx, and the insertion complexity is reduced to O(1).

An array deletion operation

Method one: We can perform multiple deletions all at once (similar to the JVM’s tag sweep garbage collection algorithm). Each delete operation is marked only when the array space is insufficient to trigger the actual delete operation, thus greatly reducing the data movement caused by the delete operation. Just like the garbage in the trash can, it does not disappear but is ” marked ‘as garbage, and only when the trash can is full will the trash can be cleaned up, and then other garbage will be stored again

Method 2: Similar to insert optimization, replace the value at the deleted position with the value at the n-1 position, and maintain the array with the length len=len-1.

Matters needing attention

Be wary of arrays out of bounds ！！！！

In C, all memory Spaces are freely accessible as long as they are not restricted. Therefore, the compiler will not report an error when accessing an out-of-bounds array. Instead, it will encounter some inexplicable logic errors, and these errors are very difficult to debug.

Here’s an example:

#include <stdio.h>

int main(a){
    
    int i = 0;
    int arr[3] = {0};

    for(; i<=3; i++){
        arr[i] = 0;
        printf("%d\n", i);
    }

    return 0;
}
Copy the code

This code will print 0, 1, 2 indefinitely

Since the array ranges from 0 to 2, the value of arr[3] is set to 0 illegally, causing arr[3] to be reset to 0 every time the loop reaches I =3, that is, I to be reset to 0.

As for why arr[3] is I, I suggest you take a look at the C++ memory model

To recap, we declare and create I, and then we declare and create the ARR array. Since the stack address space expands from high to low, I is higher than the ARR memory address. Since 8-byte alignment is the default under compiler 64-bit operating systems, I and ARR [2] address Spaces are contiguous. Since the array elements and I are both ints (4 bytes each), arr[3] is essentially I.

On some systems, such as the Mac, there is no such thing as an infinite loop. Because stack protection is enabled by default, this effect can be achieved by compiling the command line argument -fno-stack-protector to disable stack protection.

Extended task

In addition to these features, arrays have a fatal disadvantage: they cannot be dynamically scaled, which means that arrays are fixed in size and cannot be dynamically scaled based on scenarios.

STL Vector implements the corresponding function, you can take a look at the source code to implement a simple Vector, such as:

1. Apply for global variablescapLen represents the capacity of the array, and len represents the current usage of the arraycapArray pointer, int *a = new int[cap] 3. When adding elements, if len <capA [len++] = val 4capandcap< 100000,cap = cap* 2. If len > =capandcap> = 100000, thencap = cap+ 100000; Copy the elements of the original array into the new array. Let pointer A point to the new array. Then free the memory space of the original array. Consider the failure to apply for a new array memory spaceCopy the code

The list

We learned about arrays and found that they have the following disadvantages:

1. The time complexity O(n) of insert and delete is relatively low. 2. In the array let you implement vector function small task, which let you consider the new array memory space failure. The reason is that arrays require a contiguous chunk of memory, which requires a lot of memoryCopy the code

Linked lists solve both of these problems: Linked lists are linear table data structures that use “Pointers” to concatenate a set of discrete chunks of memory.

Because it is not continuous, the insertion and deletion operations of linked list are O(1). Just because it is not continuous, the memory address of the corresponding element cannot be calculated by addressing formula like array, resulting in the complexity of random access and modification operation to O(n). Therefore, there is no perfect algorithm, only the most suitable algorithm in some scenarios ~

The most commonly used list structures are: single, bidirectional, and circular lists.

Singly linked lists:

Circular linked lists:

The advantage of a circular list is that it is easier to go from the end of the chain to the head of the chain than a single list. Circular linked lists are especially suitable when the data to be processed has a circular structure. Take the famous Joseph problem

Bidirectional linked list:

The complexity of the

1. Insert: O (1)
2. Delete: O (1)
3. Change: O (n)
4. Random access: O(n)

Optimization idea

For linked list insertion and deletion operations, special treatment is needed for inserting the first node and deleting the last node, which may cause errors due to incomplete consideration.

We can use the head list (the head pointer will always point to the sentinel node regardless of whether the list is empty or not. The sentinel node does not store data. Since the sentinel node always exists, inserting the first node and inserting the other nodes, deleting the last node and deleting the other nodes can be unified into the same code implementation logic.)

Matters needing attention

Hand tear linked list must be vigilant pointer loss and memory leakage ！！！！

When we write, we have to be careful not to lose the pointer, and when we add operations, we have to pay attention to the order of operations. Be sure to manually free up memory space during the delete operation

Extended task

A way to determine if a string is a palindrome by storing a string in a single linked list (one character per node)?

The time complexity is O(n) and space complexity is O(1). The specific method is as follows: the fast pointer takes two steps at a time (P = P ->next-> Next) and the slow pointer takes one step at a time (P = P ->next). When the fast pointer reaches the end point, the slow pointer just reaches the midpoint. Modify the next pointer at the same time when the slow pointer is moving forward, so that the first half of the list is in reverse order, and finally compare whether the lists on both sides of the midpoint are equal.

In addition, we can also look at the single linked list flipping, linked list detection whether ring, two ordered linked lists merge, delete the NTH node from the bottom, find the middle node of the linked list and other problems. The corresponding leetcode title number is (206,141,21,19,876)

The stack

A stack is a linear table data structure with limited operation. It is characterized by first in, last out, last in, first out.

The stack consists of two operations: loading and unloading, and of course, checking the stack header, whether it is empty, etc.

This is less flexible than arrays and linked lists, but because only a few interfaces are exposed, it is more controllable for specific scenarios (stacks are essentially arrays or linked lists), such as function call stacks.

The complexity of the

Stack: O (1)

The stack: O (1)

Return stack header: O(1)

Empty stack: O(1)

Application scenarios

The function call stack mentioned above, you can supplement the operating system stack frame related knowledge (future operating system topic will lead you to learn ~).

To recap: The operating system allocates each thread a separate block of memory, organized into a “stack” that stores temporary variables for function calls.

When a function call occurs, the system pushes the parameters and return address of the function to the top of the current stack frame, and then continues to create the next stack frame. The function returns to reclaim the stack frame and returns to the previous stack frame.

In addition, I have recently learned Go language, in which derfer also makes use of the characteristics of stack. In addition, the inverse Polish expression, parenthesis matching and other operations can use the stack to achieve, you can check the details of ~

Extended task

Use dynamic array to write a dynamic expansion of the stack ~

On the stack, you can do on Leetcode 20155232844224682496 items

The queue

A queue is a linear table data structure with limited operation. It is characterized by first in first out, last in last out.

Like a stack, a queue consists of two operations: loading and unloading, which are essentially arrays or linked lists

Queues are implemented by maintaining two Pointers: head(to the head of the queue) and tail(to the tail of the queue)

The complexity of the

Team: O (1)

The team: O (1)

Return to team head: O(1)

Queue empty: O(1)

Optimization idea

Head and tail continue to move backward as the queue enters and exits. When tail moves to the far right, you can no longer add data to the queue even if there is free space in the array.

For the above situation, we can use the circular queue to solve ~, must pay attention to determine the team empty and full judgment conditions:

When the queue is full: (tail+1) % n == head When the queue is empty: head == tailCopy the code

Application scenarios

For most of the limited resources of the scene, when there is no idle resources, basically all can be done by “queue” this kind of data structure request queue, such as the cache, message queues, network routers in the waiting queue, and so on, they are in a lot of underlying system, framework, the development of middleware, it plays a key role

Queue based on linked list, can achieve a queue to support infinite queuing, but may lead to too many requests queuing waiting, suitable for low response sensitivity of the system.

Array based implementation of the queue has a limited size, when the queue request exceeds the size of the queue will reject subsequent requests, suitable for the response sensitivity of the system. The size of the queue should also be set appropriately: too large to affect response time due to too many waiting requests, and too small to fully utilize resources affecting performance.

Extended task

Blocking queue: added blocking operations on the basis of queue: queue is empty, data from queue head will be blocked; When the queue is full, inserting data will be blocked.

Concurrent queues: Based on blocking queues, increase processing efficiency by increasing the number of consumers. Attention should be paid to thread safety in multi-threaded model. Solutions:

1. Lock, simple implementation but low performance 2. Based on circular queue, CAS atomic operation is used to achieve lockless circular queueCopy the code

The principle of queue is applied to the message queue in the service. Its advantages are decoupling, asynchronous and peak clipping, which will not be described in detail.

You can try to implement a thread-safe lock – free loop queue (write – read model)~