1. Sequential List and Linked List

Course Content#

Overview of Basic Data Structures
- Focus on the red part!
Three Equations
- Program = Algorithm + Data Structure
- Program Design = Algorithm + Data Structure + Programming Paradigm
- Data Structure = Structure Definition + Structure Operation
Through algorithms and data structures, computers can make rational use of resources and make computing resources more valuable.

[An array with higher functionality]

Space is continuous and can store elements of the same type
- Sequential lists can also store sequential lists
size: the size of the sequential list
length: the number of elements stored
data_type: the type of elements stored

Insertion
- 👇👇👇
- Cannot insert in an empty position, must be continuous
- All elements after the insertion position move one position back
  - Move from the back, each element moves one position back
- Attributes that must be changed: length + 1
  - Size may need to be changed, see below for expansion
Deletion
- 👇👇👇
- Not really deleted, but tells the system that the storage area at this address can be occupied and overwritten
- Move all the elements after it one position forward
  - The value at the position to be deleted is overwritten
  - How to overwrite the last value?
    - Simply set length - 1
    - Can be customized
- Attributes that must be changed: length - 1
⭐Add expansion operation
- Dynamic memory allocation function
  - malloc: only allocates space, value is not determined. For example: checking in without a cleaning lady
  - calloc: allocates space and initializes it. For example: checking in with a cleaning lady to clean up
  - realloc: reallocates space. For example: upgrading the room

void* realloc (void* ptr, size_t size); // Returns the address of the newly allocated space

3 cases [realloc]

First, try to add space directly after the original address, and the address of the space remains unchanged; if not,
Try a different address, allocate space, and then copy the data from the original space to the new space, and free the original space; if not, (you can design to reduce expansion)
Return a null address without clearing the current address

Internal to the program + internal to memory
- [Internal to the program] only exposes the head pointer
  - Head pointer, small hand, mother hen: records the address of the first node
  - Similar to an eagle catching a chick
- [Internal to memory] is the connected nodes
  - Node: data field + pointer field
  - Pointer field
    - The pointer field of the last node is NULL
    - The pointer field of a singly linked list is also known as "successor"; a doubly linked list has "predecessor" and "successor"
Both sequential lists and linked lists belong to sequential storage structures
- Linked lists are logically continuous, but not necessarily physically continuous

Insertion
- ① Go to the node p at the previous position of the insertion position
- ② First, set the pointer field of the new node x to the node p.next at the insertion position
- ③ Set the pointer field of p to the new node x
- The order cannot be changed! Otherwise, it may cause memory leaks (you can't use it anymore, but the system thinks you are using it)
Deletion
- Go to the previous position of the node to be deleted
Reversal
- Method 1
  - Use a new linked list and use head insertion
  - Continuously insert nodes at index = 0
  - Disadvantages: waste of space, troublesome
- Method 2
  - In-place reversal, using two variables to reverse, also using head insertion
  - Premise: each operation should not cause memory leaks
  - The NULL address is still at the end and will not be reversed
Code demonstration to follow

For the case of inserting a node at index = 0
- 🆒When the head records the address of the tail node, directly insert after the tail node pointed by head
- ❌If the head still records the address of the first node, it won't work because
  - To find the previous node of the node at index = 0, you may need to traverse the entire linked list to find the tail node
  - Unlike a singly linked list, where you can directly insert after the head and before the node at index = 0
For the case of inserting a node at the end
- Need to modify the head to point to the new tail node [8]!

Initialization, destruction
- Use malloc to allocate space and initialize the structure
- Free from inside to outside the structure, then set the pointer to NULL
Expansion operation
- Assign the return address of realloc to an intermediate variable to avoid returning NULL, which would cause the original data to be lost
- After realloc is successful, the original address space is automatically freed
- Can design to reduce the expansion space by half until there is no space left and return a failure flag of 0
- There are many details, see comments for more information
Insertion, deletion
- Pay attention to the situations where operations cannot be performed
- When inserting a full list, perform an expansion operation
Printing: user-friendly
Main function testing: use rand(), magical modulo operation (to get data, simulate various examples, determine the number of operations), remember to clear space

Partial results

Virtual head node, convenient for inserting and deleting the first node
- Use a regular variable to define the head, ❓considering that
  - The virtual head node is relatively fixed and does not need to be freed at any time
  - Regular variables are more stable than pointer variables, and there is no need to malloc

⭐Why do we need to dynamically allocate memory [using malloc, etc.] when initializing data structures [such as linked lists, linked list nodes], instead of defining regular variables?
- First, rule out the blind spot: it is not because pointers can only accept addresses returned by malloc, pointers can also point to regular variables
- Key: [Memory allocated by malloc is in the heap space, regular variables defined in the stack space (defined in functions)]
- Stack space: only 8MB in size; variables are automatically released after leaving the function [scope]
- Heap space: can allocate large memory; variables have a long life cycle and generally need to be manually released
❓Difference between defining the virtual head node as a regular variable and a pointer variable
- Personally, using a pointer variable is to receive the address returned by malloc
- The virtual head node is just an indicator here, does not require a large space, so there is no need to malloc, a regular variable is sufficient