This series of articles are recorded in the form of notes, and the main content is referred to The Beauty of Data Structures and Algorithms by Professor Wang Zheng.
The list
What is a linked list
An “array” that concatenates a set of discrete chunks of memory through a “pointer”;
Common linked list structures
- Singly linked lists
- Circular linked list
- Two-way linked list
Singly linked lists
One head node, N intermediate nodes, and one tail node; The intermediate node contains the data center of the node and a pointer to the address of the next nodeSuccessor pointer next.
Insert, delete:Because the storage space of the linked list itself is not continuous, we only need to consider the pointer change of adjacent nodes, so the corresponding time complexity is O(1).
Looking for:However, there are pros and cons. Linked lists are not as efficient as arrays for randomly accessing the KTH element. Because the data in the linked list is not stored continuously, the corresponding memory address can not be directly calculated according to the initial address and subscript through the addressing formula like array. Instead, the corresponding node needs to be traversed according to the pointer node by node until the corresponding node is found.
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. While it is possible to do this with a single list, the code is much cleaner with a circular list.
Circular linked list
Circular linked list is a special single linked list. A pointer to the tail of a circular list points to the head of the list.
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.
Two-way linked list
Support for two directions, each node has not only a successor pointer next to the next node, but also a precursor pointer prev to the previous node.
Bidirectional circular linked lists
The circular version of a bidirectional list, without saying much, goes straight to the figure above.
Linked list VS array performance
The time complexity of their insert, delete and random access operations is opposite.
Array is easy to use, in the implementation of the use of continuous memory space, you can use the CPU cache mechanism, preread the array of data, so the access efficiency is higher. Linked lists are not stored consecutively in memory, so they are not CACHE-friendly and cannot be preread effectively.
The disadvantage of arrays is that they are fixed in size and occupy the entire contiguous memory space once declared. Then you have to apply for a larger memory space and copy the original array into it, which is very time-consuming. Linked lists have no size limit and naturally support dynamic expansion, which I think is the biggest difference between them and arrays.
In addition, if your code is very memory intensive, arrays are more suitable for you. Because each node in the linked list consumes extra storage space to store a pointer to the next node, memory consumption doubles. In addition, frequent insertion and deletion of linked lists will lead to frequent memory requests and releases, which can easily lead to memory fragmentation and Garbage Collection (GC) if the Java language is used.
Some DOS and don ‘ts for linked lists
Understand the meaning of Pointers or references
Whether “pointer” or “reference”, in fact, they mean the same thing, they are the memory address of the object referred to. Assigning a variable to a pointer is essentially assigning the address of the variable to the pointer, or conversely, the pointer holds the memory address of the variable, points to the variable, and the pointer finds the variable.
Be alert for pointer loss and memory leaks
p.getNext() = x; // set p's next pointer to x;
x.setNext(p.getNext()); // next pointer on node x to node b;
Copy the codeThe x node is going to point to itself. So the whole list is split in half, and all nodes from node B onwards are inaccessible. For the insert we just did, we simply reversed the order of lines 1 and 2.
In C, memory management is the responsibility of the programmer. If the memory space corresponding to the node is not released manually, memory leaks will occur. Similarly, when deleting linked list nodes, you must also remember to manually free up memory space, otherwise, memory leaks will also occur. Of course, for a programming language like Java, where the VIRTUAL machine automatically manages memory, this is not a concern.
Use sentries to simplify the implementation
Sentinel, it’s about borders between countries. In the same way, sentinels solve “boundary problems” and are not directly involved in business logic.
When we insert the head of a one-way list and delete the tail, it is inevitable to nullify it, such as:
if (head == null) {
head = new_node;
}
if(head. GetNext () = =null) {
head = null;
}
Copy the codeIf we introduce a sentinel node, the head pointer will always point to that sentinel node regardless of whether the list is empty or not. We also call this type of list with sentinel nodes a lead list. Conversely, a list without sentries is called an unheaded list.
In fact, this technique of using sentinels to simplify programming is useful in many code implementations, such as insertion sort, merge sort, and dynamic programming. Here is a simple application example: without sentry:
// In array A, find the key, return the location of the key
// where n represents the length of array A
int find(char* a, int n, char key) {
// If a is null, or n<=0, there is no data in the array
if(a == null || n <= 0) {
return -1;
}
int i = 0;
I
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}
return -1;
}
Copy the codeUse sentry: Let’s set the key we need to look for as a boundary, reducing one judgment.
// In array A, find the key, return the location of the key
// where n represents the length of array A
// I'll give you two examples. You can use the examples to walk through the code
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// The value of a[n-1] will be replaced by key
if (a[n-1] == key) {
return n-1;
}
// Temporarily store the value of a[n-1] in the TMP variable for later recovery. TMP = 6.
// The reason for doing this is that the find() code does not change the contents of the A array
char tmp = a[n-1];
// insert key into a[n-1] where a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// The while loop has fewer I
while(a[i] ! = key) { ++i; }A = {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// If I == n-1, 0... There is no key between n and 2, so -1 is returned
return -1;
} else {
// Otherwise, return I, the index of the element equal to key
returni; }}Copy the codeWe successfully omit a comparison statement I <n by using a sentry a[n-1] = key, and the cumulative time becomes apparent when it is executed tens or hundreds of thousands of times.
Of course, this is just to illustrate the sentry function, you should never write code like the second paragraph, because it’s not very readable. For the most part, we don’t need such extreme performance.
Pay special attention to boundary condition processing
In software development, code is prone to bugs in some boundary or abnormal situations.
For linked lists, we can check boundaries by asking the following questions:
- Does the code work if the list is empty?
- Does the code work if the linked list contains only one node?
- Does the code work if the linked list contains only two nodes?
- Does the code logic work when dealing with heads and tails?
In fact, when you write any code, not just linked list code, don’t just implement business-as-usual functions. Think about what boundary cases or exceptions your code might encounter when it runs. Write code that is robust when confronted with what to do about it!
Other articles in this series: Table of contents for Data Structures and Algorithms