Sequence lists and linked lists that are rotten and give you a headache

Article directory

    • Preface
    • What is a sequence list and what is a linked list?
      • The difference in data structure between linked list and sequential list
    • Sequence table
      • 1. Static sequence list and dynamic sequence list
      • 2. Initialization of sequence table and addition, deletion, checking and modification
        • 1. Initialization and deletion of sequence table
        • 2. Addition, deletion, checking and modification of sequence table
    • linked list
      • 1. Definition of one-way linked list
      • 2. Initialization and addition, deletion, and modification of one-way linked lists
        • 1. Initialization and deletion of one-way linked list
        • 2. Addition, deletion, checking and modification of linked list
    • Time complexity analysis of linked lists and sequential lists
      • Time complexity of adding, deleting, checking and modifying linked lists
      • The time complexity of adding, deleting, checking and modifying the sequence table
    • Why use linked list? Why use a sequence table?
      • Advantages and Disadvantages of Sequence Lists
      • Advantages and disadvantages of linked lists
      • When to use linked lists and sequence lists

Foreword

I can see that it has been a long time since I wrote the previous article, and now I am starting to learn more about data structures. Start updating as much as possible now, and I will post my usual practice in the future as a way to push myself.

What is a sequence list and what is a linked list?

We must first distinguish one of their frameworks. The upper one is a sequence list, and the lower one is a linked list. Obviously, each data space in the sequence list is continuous and next to each other, while the linked list is like a chain, strung together one by one. Yes, their data spaces are not continuous. This is the difference between linked lists and sequential lists. So from the data structure point of view, what is the difference between a linked list and a sequential list?

The difference in data structure between linked lists and sequential lists

Both sequential lists and linked lists belong to linear list structures, and linear lists are a collection of the same type of data. Sequential lists are stored continuously, while linked lists are stored in multiple spaces, and the next data is recorded through pointers. Spatial address access. In simple and easy-to-understand terms, the space requested by the sequence table is continuous, but the space requested by the linked list is discontinuous, but it will record the address of the next space so that the next node can be found. Data. Later I will use code to give you a deeper understanding of the difference between linked lists and sequential lists.

Sequence table

1. Static sequence list and dynamic sequence list

// Static sequence table
#define N 1000
typedef int SLDataType;

structSeqList
{<!-- -->
SLDataType a[N];
int size;
};

this! It is the structure of a sequence table we defined. This is a static sequence table. The space is fixed and cannot be expanded. However, this will cause a problem. If we use an array normally, will it need so much space? This is There will be a disadvantage of wasted space, so! We want to improve.

//Dynamic sequence table
typedef int SLDataType;

typedef struct SeqList
{<!-- -->
SLDataType* a;
int size; // Store the number of valid data
int capacity; // space size
}SL;

This is our improved dynamic sequence table. It can dynamically open up memory space. That is, we can judge whether the space needs to be expanded based on the capacity of this sequence table. This is also the definition of our commonly used sequence table.

2. Initialization of sequence table and addition, deletion, checking and modification

Here I am helping everyone understand the code by asking questions, then giving the code and analyzing the code. These questions are also encountered by me in my own study.

1. Initialization and deletion of sequence table

When we start to write the interface function of the sequence table, we first need to define and initialize the sequence table. So what do we need to pay attention to when defining it, and what does initialization mean? And why delete it?

int main()
{<!-- -->
SL s1;
SLInit( &sl);
return 0;
}

First of all, do we have to define a variable s1 in the main function first? Is the type of this variable the same as the structure type we redefined when defining the dynamic sequence table to be SL and the sequence table? Then we go Call this initialization function we wrote.

void SLInit(SL* ps)
{
assert(ps);

ps->a = (LDataType*)malloc(sizeof(SLDataType)*4);
if (ps->a == NULL)
{
perror("malloc failed");
exit(-1);
//return;
}

ps->size = 0;
ps->capacity = 4;
}


int main()
{<!-- -->
SL s1;
SLInit( &sl);
return 0;
}

Here we can see that what we passed is an address. Why is it an address? Because we need to modify the content in this function, and changes in the formal parameters will not affect the actual parameters. A strange thing here is assert, which is an assertion that the thing pointed to by this pointer is not NULL. Later, we use malloc to dynamically apply for space. After applying for space, you need to pay attention to the following

1. There is a possibility of application failure.
2. After the application is completed, the values of size and capacity in the structure need to be changed

In the first case, we can just use a judgment statement to avoid it.

In the second case, we have to pay attention to the fact that size is the number of data in the array, and capacity is the space size of the array. The two are different. We have just initialized this sequence table. Is there any data in it? Of course there is none, so size is 0, so how many spaces have we applied for? It is 4, then capacity = 4.
The above is our initialization of the sequence table.

With initialization, deletion is of course indispensable. If you do not delete, you will face a problem. When we learned C language, we also knew that if we apply for space and do not release it, there will be a risk of memory leakage. In order to avoid this problem, We also need to write a function to free up space.

void SLInit(SL* ps)
{<!-- -->
assert(ps);

ps->a = (LDataType*)malloc(sizeof(SLDataType)*4);
if (ps->a == NULL)
{<!-- -->
perror("malloc failed");
exit(-1);
//return;
}

ps->size = 0;
ps->capacity = 4;
}


void SLDestroy(SL* ps)
{<!-- -->
assert(ps);

free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}

int main()
{<!-- -->
SL s1;
SLInit( &sl);
SLDestroy( & amp;s1);
return 0;
}

When deleting a function, the first thing to do is assert. Here is the necessity of assertions.

If this points to an empty node, it is an illegal operation when we dereference the empty node.

The next step is to release the space. The released space must be the space we applied for, otherwise an error will be reported (this is a truth I only understood after making many mistakes), and what we release can only be the space we applied for the array, and It’s not the sequence table structure. To prevent others from accessing this space later, we need to point it to null and reset the data to zero.

2. Addition, deletion, checking and modification of sequence table
//Delete the head plug and delete the tail plug.
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//Return the subscript, if there is no search, return -1
int SLFind(SL* ps, SLDataType x);

//Insert x at pos position
void SLInsert(SL* ps, int pos, SLDataType x);
// Delete the value of pos position
void SLErase(SL* ps, int pos);

Our interface to the sequence table mainly implements these functions. I will also use the code to help everyone understand the structure of the sequence table while talking about it.

Let’s talk about insertion first, and then deletion, so that it will be easier for everyone to understand.
When we insert data, we have to consider two possibilities:

1. Ordinary insertion
2. Capacity expansion insertion


From this picture, we can see that when inserting 4, the space of this array is enough. This is our ordinary insertion. But when inserting 5, we find that the capacity is not enough. At this time, we need to expand the capacity, that is, expand the capacity. Inserted.

void SLCheckCapacity(SL* ps)
{<!-- -->
assert(ps);

// Expand when full
if (ps->size == ps->capacity)
{<!-- -->
SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
if (tmp == NULL)
{<!-- -->
perror("realloc failed");
exit(-1);
}

ps->a = tmp;
ps->capacity *= 2;
}
}

Because we often use expansion when inserting, we can write a separate function for it. When it is full, size == capacitty. For expansion, we will use another way to open up space, realloc, through a tmp. The capacity is expanded in the new space, and finally copied back to the original array to achieve expansion, but how much expansion is also a question. We generally choose 2 times expansion in order to make space utilization more efficient.

How to achieve the end insertion, tail insertion and middle insertion?

Tail insertion is very simple. After describing expansion insertion and normal insertion, it is actually to directly add data to the end of the array without moving the data.

void SLPushBack(SL* ps, SLDataType x)
{<!-- -->
assert(ps);
SLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size + + ;
}

I won’t talk about the first two. The old friend asserts and the new friend checks the capacity. The subsequent insertion is easier to understand, which is to add data after the array. Note that size is the amount of data in the array, which is n, and the subscript is n. -1, so when inserting, be sure to insert it into a[size], not size-1, otherwise it will be overwritten, and the final size will be + 1;

void SLPushFront(SL* ps, SLDataType x)
{<!-- -->
assert(ps);
SLCheckCapacity(ps);
//Move data
int end = ps->size - 1;
while (end >= 0)
{<!-- -->
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size + + ;
}

In terms of header insertion, we have to pay attention to moving all the data back one bit first. How to move it? Is it better to move from the beginning to the back or from the back to the front? We have to analyze it first.

Moving from front to back, we need to create a variable to record the later data, and then overwrite the previous data to the later data.
Moving from back to front, we only need to move the last number one digit to the back, and then move the previous number back. There is no need to create a new variable to save it.

Obviously, it is better to use the second method, so we only need to move the last number forward in sequence until end == 0, and then insert it at the head if the capacity is sufficient.

void SLInsert(SL* ps, int pos, SLDataType x)
{<!-- -->
assert(ps);

assert(pos >= 0 & amp; & amp; pos <= ps->size);
SLCheckCapacity(ps);

int end = ps->size - 1;
while (end >= pos)
{<!-- -->
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size + + ;
}

Middle insertion is actually very similar to head insertion. The issue we need to pay attention to is which bit should be moved to and stop. In addition, the position of pos also needs to be noted. It cannot exceed the last bit of the last number in the array, otherwise it will not be continuous and cannot In front of the subscript 0, this will go out of bounds. Returning to the previous question, we want to insert at the pos position, which means that the number we insert must be at the position with the subscript pos, so the stop position is at pos. The previous digit will move all the numbers including the pos position backward.

while (end >= pos)
{<!-- -->
ps->a[end + 1] = ps->a[end];
--end;
}

In terms of deletion, it is actually to remove the inserted part of the inserted data, change the size from increase to size decrease, deletion of the head and tail, and deletion in the middle are similar to insertion.

void SLPopBack(SL* ps)
{<!-- -->
assert(ps);
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;
ps->size--;
}

void SLPopFront(SL* ps)
{<!-- -->
assert(ps);
assert(ps->size > 0);
int begin = 1;
while (begin < ps->size)
{<!-- -->
ps->a[begin - 1] = ps->a[begin];
+ + begin;
}
ps->size--;
}

void SLErase(SL* ps, int pos)
{<!-- -->
assert(ps);
assert(pos >= 0 & amp; & amp; pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{<!-- -->
ps->a[begin - 1] = ps->a[begin];
+ + begin;
}

ps->size--;
}

What needs to be noted here is that when we delete, we can use the overwriting method, and just overwrite the last digit of the number to be deleted in order, instead of overwriting from the last digit forward, which is like inserting The problem from front to back is the same as from back to front. The question is whether to create new variables.

The search problem is actually simpler. Given a number to find the subscript of that number, in layman’s terms we just traverse the array and return the subscript.

int SLFind(SL* ps, SLDataType x)
{<!-- -->
assert(ps);

for (int i = 0; i < ps->size; i + + )
{<!-- -->
if (ps->a[i] == x)
{<!-- -->
return i;
}
}

return -1;
}

The above is our study of the sequence list. Next, we will start to learn the linked list, the good brother of the sequence list.

Linked list

1. Definition of one-way linked list

This is a new data structure. We first need to know how linked lists are linked.

As you can see, each node stores a piece of data, and each node has a pointer named next, which points to the next node. The next node also has a next pointer pointing to its next node. , are connected to form a chain structure, which is a linked list.

Then when we define the linked list, we have to create a variable to store the data and a pointer to the next node.

typedef int SLTDataType;

typedef struct SListNode
{<!-- -->
SLTDataType data;
struct SListNode* next;
}SLTNode;

We first redefine a type so that we can change the data type later. In the linked list structure, we can see that we have a variable whose data type was redefined earlier, and a structure pointer, which points to the next linked list structure. body, so our type is also this structure type.

2. Initialization and addition, deletion, and modification of one-way linked lists

1. Initialization and deletion of one-way linked list

Like the sequence list, the linked list also needs to be initialized and deleted, but is there any difference between the initialization of the linked list and the sequence list?

SListNode* BuySListNode(SLTDateType x)
{<!-- -->
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
plist->data = x;
plist->next = NULL;
return plist;
}

void SListDestory(SLTNode** pphead)
{<!-- -->
assert(pphead);

SLTNode* cur = *pphead;
while (cur)
{<!-- -->
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}

int main()
{<!-- -->
SListNode* L1 = BuySListNode(1);
SListDestroy( & amp;L1);
}

In fact, we can see that the creation of a linked list is similar to that of a sequence list, except that the data inside is different. The sequence table has a data volume and space size, but the storage space of each data in the linked list is independent, so he only needs to create a linked list. The space of the structure is enough. Why let its next = NULL? Because we only created a node and there are no nodes behind it. When we introduced it, we can see that the last node of the linked list points to NULL node.
When deleting, we need to delete nodes one by one, which involves the traversal of the linked list. We can create a cur pointer to record the address of the current node, and then create a next pointer to Record the address of the next node to achieve iterative release.

2. Addition, deletion, checking and modification of linked list
//Single linked list tail insertion
void SListPushBack(SListNode** pplist, SLTDateType x);
// Header of singly linked list
void SListPushFront(SListNode** pplist, SLTDateType x);
//Tail deletion of singly linked list
void SListPopBack(SListNode** pplist);
//Delete single linked list header
void SListPopFront(SListNode** pplist);
//Singly linked list search
SListNode* SListFind(SListNode* plist, SLTDateType x);
//Insert x after pos position in singly linked list
void SListInsertAfter(SListNode* pos, SLTDateType x);
//Singly linked list deletes the value after pos position
void SListEraseAfter(SListNode* pos);

What is the difference between adding, deleting, checking and modifying a linked list and adding, deleting, checking and modifying a sequence list? What should we pay attention to?
First of all, adding and deleting linked lists is very convenient. We only need to find the previous node and the next node of the node to be added or deleted, and then link them together, which is an insertion. On the contrary, it is a deletion.

void SListPushBack(SListNode** pplist, SLTDateType x)
{<!-- -->
assert(*pplist);
SListNode* newnode = BuySListNode(x);
SListNode* tail = *pplist;
while (tail->next != NULL)
{<!-- -->
tail = tail->next;
}
tail->next = newnode;
}

void SListPushFront(SListNode** pplist, SLTDateType x)
{<!-- -->
assert(*pplist);
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}

There is a question here that everyone needs to look at carefully.

Why is the secondary pointer passed here?

Let’s look back and see if we created a pointer when we created the linked list. If we passed a pointer that is also a first-level pointer, would there be a problem that the formal parameters cannot change the actual parameters? So, solve The only solution is to pass a secondary pointer. This problem also appeared in the linked list just released. Did anyone find it?

Looking at the code, we can see that when inserting at the end, our assertion is still at the first place. This is the rigor of the code. We create a new node in it, put our data in, and then use A pointer to record the head node so that we can traverse, find the last node, and connect the new node to the next node pointed to by the last node. It is more convenient when plugging in the head. You only need to create a new node and connect the next node of this node to the previous linked list, which is head plugging.

When deleting the header plug, we need to pay attention to several points

1. Deleted data is limited
2. Whether the deleted node needs to be released

See the code content

void SListPopBack(SListNode** pplist)
{<!-- -->
assert(*pplist);
if ((*pplist)->next == NULL)
{<!-- -->
free(*pplist);
}
else
{<!-- -->
SListNode* tail = *pplist;
SListNode* Prev = *pplist;
while (tail->next != NULL)
{<!-- -->
Prev = tail;
tail = tail->next;
}
Prev->next = NULL;
free(tail);
}
}

void SListPopFront(SListNode** pplist)
{<!-- -->
assert(*pplist != NULL);
SListNode* newhead = (*pplist)->next;
free(*pplist);
*pplist = newhead;
}

We can see that below the assertion, there is a judgment. When the last linked list is deleted, the next node it points to will be empty. At this time, we only need to delete that node. , and we also see that every time a node is deleted, it needs to be released. This is because each node in the linked list has to apply for space. If it is not released, memory leaks will occur.

However, when we see that the header is deleted, why do we not need to judge? At this time, we need to analyze the code. When asserting, we have already asserted that the code is not empty. At this time, we define a new header node , is the next node of the head node of the current linked list. We release the current head node. Even if this is the last node, its next node is NULL, newhead = NULL, and the released one is Previous node. Therefore, head deletion is more efficient than tail deletion.

When I saw the problem of middle insertion and middle deletion, I made a picture to help everyone understand.

Here we can see that as long as we find the previous node and the next node at the insertion or deletion position, disconnect them, and then insert and delete, we can complete our intermediate insertion and intermediate deletion functions.

Get the code! 

void SListInsertAfter(SListNode* pos, SLTDateType x)
{<!-- -->
assert(pos != NULL);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

void SListEraseAfter(SListNode* pos)
{<!-- -->
assert(pos != NULL & amp; & amp; pos->next != NULL);
SListNode* next = pos->next->next;
free(pos->next);
pos->next = next;
}

Here is the implementation of inserting a node after a certain node position and deleting the node after a certain position. There are two problems here.

1. Why not insert before pos position?
2. Why not delete the node at pos position?

Here we can see that what we are given is a pointer to the pos position. In the picture just now, we also know that insertion and deletion can be achieved by knowing the previous node and the next node. So here, we give The node at the pos position, but we don’t know what the node before pos is. We don’t have a pointer pointing to the previous node, so we cannot meet this condition, so when inserting and deleting, we can only go after the pos position. accomplish.

At this time, I know that some students will ask questions, “I can traverse from the beginning, so I can find the previous node“.

Danshi, students, have you ever thought about the time complexity required to traverse it once? What if there are 10,000 numbers here, or 10,000 numbers? In this way, we will waste a lot of time on the traversal, which is very inefficient. of.

As for searching, it is actually traversal, so we can just look at the code.

SListNode* SListFind(SListNode* plist, SLTDateType x)
{<!-- -->
SListNode* tmp = plist;
while (tmp->next != NULL)
{<!-- -->
if (tmp->data == x)
{<!-- -->
return tmp;
}
else
{<!-- -->
tmp = tmp->next;
}
}
printf("?");
return NULL;
}

It’s just a simple traversal process, I believe it’s easy for students to understand.

Time complexity analysis of linked lists and sequential lists

Time complexity of adding, deleting, checking and modifying linked lists

When the linked list is added, deleted, checked and modified, it is divided into three parts: head insertion, middle insertion and tail insertion. The same is true for deletion. When we perform head insertion and head deletion, we do not need to traverse the linked list, so the time complexity of head plug deletion is O( 1), During middle insertion, middle deletion, and tail insertion and tail deletion, we need to traverse the entire linked list, so the time complexity of the search is O(N), middle insertion, middle deletion, and tail insertion and tail deletion. The time complexity is also O(N).

Time complexity of adding, deleting, checking and modifying sequence tables

When adding, deleting, and modifying the sequence table, due to the help of subscripts, the time complexity of the sequence table is O(1). When performing additions, deletions, and modifications, it needs to be divided into three parts: the head and the tail. Among them, the tail insertion Tail deletion is the most efficient because there is no need to move the data and it can be accessed directly based on the subscript, so the time complexity is O(1). However, the insertion and deletion of the middle and head parts require moving the data, which is equivalent to traversal. The sequence is listed, so the time complexity is O(N), and the search is also O(N).

Why use linked list? Why use a sequence table?

To solve these two problems, we must first know the advantages and disadvantages of sequence lists and linked lists.

Advantages and disadvantages of sequence tables

Disadvantages
1. It is inconvenient to insert data in the header and in the middle. The sequence table is equivalent to an array. We can think about it. Inserting a piece of data at the head of the array requires moving the data of the entire array backward. The same is true for inserting in the middle. The time complexity is O(N).
2. The space is limited and frequent expansion is required. Even if the code is doubled, this will lead to a new problem.
3. Waste of space, a waste of space caused when the sequence table is expanded too much.

Advantages
1. It is very convenient to insert and delete the tail. Although it is inconvenient to delete the head plug, tail insertion and tail deletion of the sequence table are very convenient, that is, inserting or deleting data at the end of the array. This does not require us to move the data, and we may need to consider expansion.
2. Support random access. This is the biggest advantage of the sequential list compared to the linked list. It can randomly access any data in the array based on the subscript.

Advantages and disadvantages of linked lists

Disadvantages
1. Random access is not supported. The linked list does not have subscripts, so it does not support randomly viewing a certain data in the linked list.
2. It is inconvenient to insert and delete the tail. Because there is no subscript, the only way to find the end of the linked list is to traverse the entire linked list, so the time complexity of tail insertion and tail deletion of the linked list is O(N).

Advantages
1. You can apply for and release space on demand. Since the space for each data in the linked list is independent, we only need to apply for the space for this data when inserting data.

Opportunities to use linked lists and sequence lists

It’s time to solve the problem of why we use linked lists and why we use sequence lists. In fact, based on the advantages and disadvantages of sequence lists and linked lists we have just analyzed, it is not difficult to see that when we need to traverse and search a set of data, it is more convenient for us to use sequence tables to store data. When adding or deleting data, it is very convenient to use a linked list.

above! It’s just about learning linked lists and sequence tables. This is also a review process for me. I hope everyone will try it out in three consecutive chapters (I really didn’t expect that one day I would ask for three consecutive chapters, hahahaha). There is still a lot to learn about data structures. I will follow up. It will be updated one by one, destroying this data structure that gives you a headache.