1 Sequential List and Linked List

Course Content#

Overview of the 【Basic Data Structures】 course
- Focus on mastering the red!
Three equations
- Program = Algorithm + Data Structure
- Program Design = Algorithm + Data Structure + Programming Paradigm
- Data Structure = Structure Definition + Structure Operations
Through algorithms and data structures, enable computers to use resources rationally, making computing resources more valuable.

【More advanced arrays】

Continuous space, can store any type of same elements
- A sequential list can also store sequential lists
size: The size of the sequential list's space
length: The number of stored elements
data_type: The type of stored elements

Insertion
- 👇👇👇
- Cannot insert empty, must be continuous
- All elements after the insertion position move back one position
  - Move from the back; each element moves back one position
- Must change the attribute: length + 1
  - size may need to change; for expansion, see below
Deletion
- 👇👇👇
- Not really deleting, but telling the system that this address's storage area can be occupied or overwritten
- Move all subsequent elements forward one position
  - Equivalent to overwriting the value at the position to be deleted
  - How to overwrite the last value?
    - Directly set length - 1
    - Actually, it can be custom designed
- Must change the attribute: length - 1
⭐Add Expansion Operation
- Dynamic memory allocation functions
  - malloc: just allocates space, value is uncertain. Example: renting a room without a cleaning lady
  - calloc: allocates space and initializes it. Example: after renting a room, a cleaning lady comes to clean
  - realloc: reallocates space. Example: upgrading the room type

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

3 Cases of [realloc]

First, try to add space directly after the original address; if not possible,
Find another address, request space, then copy the original space data to the new space, and free the original space; if not possible, (can design to reduce expansion)
Just return a null address, without clearing the current address.

Inside the program + inside the memory
- 【Inside the program】 only exposes the head pointer
  - Head pointer, little handle, mother hen: records the address of the first node
  - Associating with the eagle catching chicks
- 【Inside the memory】 are 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 belong to sequential storage structures
- Linked list logic is continuous, but physically may not be continuous.

Insertion
- ① Go to the previous position of the node to be inserted, node p
- ② First, set the pointer field of the new node x to point to the node p.next to be inserted
- ③ Set the pointer field of p to point to the new node x
- The order cannot change! Otherwise, it may cause memory leaks (you want to use it but can't, while the system thinks you are using it)
Deletion
- Go to the previous position of the node to be deleted
Reversal
- Method one
  - Use a new linked list to store, using the head insertion method
  - Continuously insert nodes at index = 0
  - Shortcoming: wastes space, troublesome
- Method two
  - Reverse in place, using two variables, also using the head insertion method
  - Premise: Each operation should not cause memory leaks
  - The NULL address is still at the end, will not be reversed.
Code demonstration can be seen later.

For the case of needing to insert a node at index = 0
- 🆒 When head records the tail node, directly insert after the tail node pointed to by head.
- ❌ If head still records the address of the head 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 head, before the node at index = 0.
For the case of inserting a node at the tail
- Need to modify head to point to the new tail node【8】!

Initialization, destruction
- Use malloc to allocate space to initialize the structure
- Free from the structure to the outside, then set the pointer to null
Expansion operation
- Assign the address returned by realloc to a temporary variable to avoid losing the original data in case of returning NULL
- After realloc succeeds, the original address space is automatically freed
- Can design to reduce the expansion space by half until there is indeed no space left to return a failure flag 0
- Many details, see comments for more information.
Insertion, deletion
- Note the situations that cannot be operated
- When full, perform expansion operation.
Printing: user-friendly
Main function test: use rand(), magical modulus operation (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 normal variable to define head, ❓ considering
  - The virtual head node is relatively fixed, does not need to be freed at any time
  - A normal variable is more stable than a pointer variable, no need for malloc.

⭐ When initializing data structures [such as linked lists, linked list nodes], why dynamically allocate memory [using malloc, etc.] instead of defining normal variables?
- First, exclude blind spots: it's not because pointers can only accept addresses returned by malloc; pointers can also point to normal variables.
- Key: 【Memory allocated by malloc is in heap space, while normal variables are defined in stack space (defined inside functions)】
- Stack space: size is only 8MB; variables are automatically released when out of function [scope].
- Heap space: can allocate large memory; variable lifecycle is long, generally needs to be manually released.
❓ The difference between defining a virtual head node as a normal variable and a pointer variable.
- My understanding is that using a pointer variable is to receive the address returned by malloc.
- However, the virtual head node is just an indication, does not require large space, so no need for malloc; a normal variable is sufficient.