Structure Types
When learning C language, the array encountered is a type of linear list in data structures, which consists of a group of n data elements of the same type. Each data element in a linear list has exactly one direct predecessor and exactly one direct successor. Additionally, the first element has no predecessor, and the last element has no successor.
The left adjacent element of a certain element is called the “direct predecessor”, and all data elements to the left of the element are called “predecessor elements”.
The right adjacent element of a certain element is called the “direct successor”, and all data elements to the right of the element are called “successor elements”.
A set of elements that satisfy this mathematical relationship has a logical relationship that is linear, and the logical relationship is one-to-one. For example, a classroom of students’ student IDs, a queue, a stack of plates… all belong to linear structures. Of course, linear structures are independent of storage methods. Simply put, if the logical relationship is one-to-one, it is a linear structure.
Therefore, based on the storage method of data, linear lists can be divided into two types: sequential storage linear lists and linked storage linear lists.
Sequential List
A sequential list refers to using a group of contiguous memory addresses to sequentially store data elements in a linear list. A linear list that uses this storage structure is called a sequential list.
Simply put: data is stored in a contiguous block of memory, which can be a named array in C language or an anonymous array (heap memory).
Characteristics of sequential lists: The logical relationship between data elements is adjacent, and the memory addresses are also adjacent. Therefore, as long as the memory address of the first data element of the linear list is known, any element in the linear list can be accessed randomly. Users typically use dynamically allocated arrays to implement sequential lists, which means using heap memory.
Random access refers to the ability to access any element in the same amount of time, while sequential access, which is the opposite of random access, takes more time. For example, a scroll (sequential) versus a book (random), a tape (sequential) versus a record (random).
Consider a question: Since arrays can be used as linear lists, how can we add, delete, and access elements in the array?
Answer: If you intend to use an array to implement the characteristics of a linear list, you need to know three conditions: the address of the first element of the array, the capacity of the array elements, and the index of the last valid element of the array.
Creating and Initializing a Sequential List
SeqList_t *SeqList_Create(unsigned int size)
{
//1. Use calloc to allocate a block of heap memory for the management structure of the sequential list
SeqList_t *Manager =(SeqList_t *)calloc(1,sizeof(Manager));
if(NULL== Manager)
{
perror("calloc memory for manager is failed");
exit(-1);//Program abnormal termination
}
//2. Use calloc to allocate heap memory for all elements
Manager->Addr =(DataType_t *)calloc(size,sizeof(DataType_t));
if(NULL== Manager->Addr)
{
perror("calloc memory for element is failed");
free(Manager);
exit(-1);//Program abnormal termination
}
//3. Initialize the management structure of the sequential list (element capacity + last element index)
Manager->Size = size;//Initialize the capacity of the sequential list
Manager->Last =-1;//Since the sequential list is empty, the initial value of the last element index is -1
return Manager;
}Checking if the Sequential List is Full
bool SeqList_IsFull(SeqList_t *Manager)
{
return(Manager->Last +1== Manager->Size)?true:false;
}Adding Elements to the Head of the Sequential List
bool SeqList_HeadAdd(SeqList_t *Manager, DataType_t Data)
{
//1. Check if the sequential list is full
if(SeqList_IsFull(Manager))
{
printf("SequenceList is Full!\n");
returnfalse;
}
//2. If there is free space in the sequential list, all elements need to be moved back by one unit
for(int i = Manager->Last;i >=0;i--)
{
Manager->Addr[i+1]= Manager->Addr[i];
}
//3. Add the new element to the head of the sequential list and update the element index in the management structure +1
Manager->Addr[0]= Data;
Manager->Last++;
returntrue;
}Adding Elements to the Tail of the Sequential List
bool SeqList_TailAdd(SeqList_t *Manager, DataType_t Data)
{
//1. Check if the sequential list is full
if(SeqList_IsFull(Manager))
{
printf("SequenceList is Full!\n");
returnfalse;
}
//2. If there is free space in the sequential list, add the new element to the tail of the sequential list
Manager->Addr[++Manager->Last]= Data;
returntrue;
}Checking if the Sequential List is Empty
bool SeqList_IsEmpty(SeqList_t *Manager)
{
return(-1== Manager->Last)?true:false;
}Deleting Elements from the Sequential List
bool SeqList_Del(SeqList_t *Manager,DataType_t DestVal)
{
int temp =-1;//Record the index of the element to be deleted
//1. Check if the sequential list is empty
if(SeqList_IsEmpty(Manager))
{
printf("SequenceList is Empty!\n");
returnfalse;
}
//2. At this point, we need to check if the target value is in the sequential list
for(int i =0; i <= Manager->Last;++i)
{
//If the target value is the same as the value of the element in the sequential list
if(DestVal == Manager->Addr[i])
{
temp = i;//Backup the index of the target element to the variable temp
break;
}
}
//3. If the sequential list does not contain the target value, terminate the function directly
if(-1== temp)
{
printf("destval [%d] is not found\n",DestVal);
returnfalse;
}
//4. If the target element is found, move the successor elements forward by one unit
for(int i = temp ; i < Manager->Last ;++i)
{
Manager->Addr[i]= Manager->Addr[i+1];
}
//5. Since one element has been deleted, the valid element index of the sequential list needs to be decremented by 1
Manager->Last--;
returntrue;
}Traversing Elements in the Sequential List
void SeqList_Print(SeqList_t *Manager)
{
for(int i =0; i <= Manager->Last;++i)
{
printf("Element[%d] = %d\n",i,Manager->Addr[i]);
}
}Example Problem
void SeqList_Insert(SeqList *L,int x)
{
int temp =-1;//Record the index of the element to be inserted
//Traverse the sequential list to find the insertion position, comparing elements
for(int i =0; i <= last;++i)
{
if(x <L[i])
{
temp = i;
break;
}
}
if(-1== temp)
{
L[last+1]= x;
return;
}
//Move the successor elements of the insertion position backward
for(int i = last; i >= temp; i--)
{
L[i+1]=L[i];
}
L[temp]= x;
}
int SeqList_Remove(*L,int p)
{//Check if the address of the sequential list is valid
if(NULL==L)
{
return0;
}
int e =0;//Variable e, record the value of the element to be deleted
//Backup the value of the element to be deleted to variable e
e =L[p];
//Move the successor elements of the element to be deleted forward by one unit
for(int i = p; i < length;++i)
{
L[i]=L[i+1];
}
return1;
}Linked List
As you can see, adding and deleting data in a sequential list is relatively cumbersome because it requires moving a contiguous block of memory.
The advantage of a sequential list is that since the memory addresses of the data elements are contiguous, random access can be achieved, and no extra information is needed to describe the related data, resulting in high storage density.
The disadvantage of a sequential list is that when adding or deleting data, large blocks of memory need to be moved. Additionally, when the number of data elements is large, a large contiguous block of memory needs to be allocated, and when the number of data elements changes drastically, the sequential list is inflexible.
Consider a question: Since adding and deleting data in a sequential list is cumbersome and occupies contiguous memory, is there a better solution?
Answer: Yes, a linked storage linear list can be used, which refers to using discrete memory units to store data elements. Users need to connect all data elements in some way, which transforms it into a linked linear list, commonly known as a linked list, which can efficiently use fragmented memory.
As you can see, the difference between sequential lists and linked lists is that sequential lists use contiguous memory, while linked lists use discrete memory space.
Consider a question: Since the address of each data element in a linked list is not fixed, how can users access a certain element?
Answer: Since the address of each data element in a linked list is not fixed, each data element should use a pointer to point to the memory address of its direct successor. Of course, the last data element has no direct successor, so the last data element points to NULL. As a user, you only need to know the memory address of the first data element to access the successor elements.
Note: If using linked storage, each data element in the linear list needs to store not only its own data but also the address of its direct successor. Therefore, each data element in a linked list consists of two parts: the part that stores its own data is called the data field, and the part that stores the direct successor’s address is called the pointer field. The data element composed of the data field and pointer field is called a node.
Note: The working principle of a linked list is actually very simple. As long as you understand the usage process of a linked list, you can easily understand it. The specific operation steps of a linked list are as follows:
Based on the number of pointer fields in the nodes of the linked list and whether the head and tail of the linked list are connected, linked linear lists can be divided into the following types: single linked list, single circular linked list, double linked list, double circular linked list, kernel linked list. The usage rules of these linked lists are similar, but the number of pointer fields is different.
The above image shows the internal structure of the simplest single linked list. You can see that each node saves an address, and each address is the address of the logically adjacent next node, except that the last node’s pointer points to NULL.
Additionally, note that there is a head pointer in the linked list. The head pointer only points to the address of the first element, and to access a certain element in the linked list, you only need to use the head pointer.
Consider a question: When using a sequential list, a management structure needs to be created to manage the sequential list. Does a linked list need to be created?
Answer: It can be chosen based on user needs. Generally, linked lists are divided into two types: one without a head node and one with a head node. The head node refers to the management structure, but the head node only stores the memory address of the first element and does not store valid data. The significance of the head node is only for convenient management of the linked list.
Linked List without Head Node
Linked List with Head Node
It can be seen that the head pointer is necessary because the elements of the linked list can only be accessed through the head pointer. The head node is optional and is only for convenient management of the linked list.
Note: In a linked list, there are also two professional terms: one is the head node, and the other is the tail node. The differences between the three are as follows:
Head Node: does not store valid data, only stores the address of the first data element, and the head pointer only points to the head node.
First Node: stores valid data and also stores the address of the direct successor. The first node is the only node that points to other nodes and is not pointed to by other nodes.
Tail Node: stores valid data, and the tail node is the last node of the linked list, so the address stored in the tail node generally points to NULL. The tail node is the only node that is pointed to by other nodes and cannot point to other nodes.
To facilitate the management of a single linked list, it is necessary to construct the data types for the head node and the valid node, as follows:
Creating an Empty Linked List with a Head Node and Initializing the Linked List
LList_t *LList_Create(void)
{
//1. Create a head node and allocate memory for the head node
LList_t *Head =(LList_t *)calloc(1,sizeof(LList_t));
if(NULL== Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2. Initialize the head node, which does not store valid content!!!
Head->next =NULL;
//3. Return the address of the head node
return Head;
}Creating a New Node and Initializing the New Node (Data Field + Pointer Field)
LList_t *LList_NewNode(DataType_t data)
{
//1. Create a new node and allocate memory for the new node
LList_t *New =(LList_t *)calloc(1,sizeof(LList_t));
if(NULL== New)
{
perror("Calloc memory for NewNode is Failed");
returnNULL;
}
//2. Initialize the data field and pointer field of the new node
New->data = data;
New->next =NULL;
return New;
}Inserting the New Node into the Linked List Based on Conditions (Tail Insertion, Head Insertion, Specified Position Insertion)
Example of Head Insertion
bool LList_HeadInsert(LList_t *Head,DataType_t data)
{
//1. Create a new node and initialize the new node
LList_t *New =LList_NewNode(data);
if(NULL== New)
{
printf("can not insert new node\n");
returnfalse;
}
//2. Check if the linked list is empty. If empty, insert directly
if(NULL== Head->next)
{
Head->next = New;
returntrue;
}
//3. If the linked list is not empty, insert the new node at the head of the linked list
New->next = Head->next;
Head->next = New;
returntrue;
}Deleting a Node from the Linked List Based on Conditions (Tail Deletion, Head Deletion, Specified Element Deletion)
Example of Head Deletion
bool LList_HeadDelete(LList_t *Head)
{// 1. Check if the linked list is empty
if(NULL== Head->next){
printf("The linked list is empty, unable to delete\n");
returnfalse;
}
// 2. Save the node to be deleted
LList_t *DelNode = Head->next;
// 3. Point the head node's next to the second node
Head->next = DelNode->next;
// 4. Free the memory of the deleted node
free(DelNode);
returntrue;
}