Shulou(Shulou.com)06/01 Report--

A linked list is also a data structure, which is slightly more complex than an array. Linked lists and arrays are very basic and commonly used data structures.

The difference between array and linked list

From the perspective of the underlying storage structure, the memory space requested by the two is not the same:

The array needs a continuous memory space to store, which requires high memory.

A linked list does not require a contiguous piece of memory space, it concatenates a set of scattered memory blocks through pointers.

For example, when we apply for an array of 100MB size, when there is no contiguous and large enough storage space in the memory space, the application will fail even if the total free space remaining in the memory is greater than 100MB. But if we apply for a linked list the size of 100MB, we can apply successfully.

Three common linked list structures

There are many kinds of linked list structures, but the most common ones are as follows:

Single linked list

Bidirectional linked list

Cyclic linked list

2.1 single linked list

Linked lists connect a group of scattered memory blocks together through pointers, and we call memory blocks "nodes" of linked lists. In order to concatenate all the nodes together, the node of each linked list needs to record the address of the next node on the chain in addition to storing data. The pointer to the address of this node is called "successor pointer next".

There are two special nodes in the single linked list, which are the first node and the last node. We habitually call the first node the head node and the last node the tail node.

The header node is used to record the base address in the linked list, and the whole linked list can be obtained according to the traversal of the header node.

Instead of pointing to the next node, the pointer to the tail node points to an empty address, NULL, indicating that this is the last node on the linked list.

Inserting and deleting data in linked lists is more efficient than in arrays. Because insert and delete operations in the array, in order to maintain the continuity of memory data, need to do a lot of data movement, the time complexity is O (n). The storage space in the linked list itself is not continuous, and there is no need to move a large amount of data in order to maintain the continuity of memory.

In the insert and delete operation of the linked list, we only need to consider the pointer change of the adjacent nodes, so the corresponding time complexity is O (1).

Inserting and deleting data in a linked list is more efficient than an array, but when you need to randomly access the k th data, it is not as efficient as the array. Because the data in the linked list is not stored continuously, the corresponding memory address can not be calculated directly according to the first address and subscript like the array, but needs to be traversed according to the pointer, node by node, until the corresponding node is found.

2.2 cyclic linked list

The essence of circular linked list is a special single linked list, and the difference between circular linked list and single linked list is at the end node. The pointer to the tail node in the single linked list points to a null address, indicating that this is the last node. The pointer of the tail node of the circular linked list points to the head node of the linked list.

Compared with single linked list, the advantage of circular linked list is that it is more convenient to go from the end of the chain to the head of the chain. When the data to be processed has the characteristic of circular structure, it is suitable to be processed by circular linked list. Such as the famous "Joseph problem".

2.3 two-way linked list

There is only one direction in a single linked list, and only one subsequent pointer, next, points to the following node. In the two-way linked list, there are two directions, and each node not only has a follow-up pointer to the following node, but also a precursor pointer prev to the front node.

The two-way linked list requires two additional space to store the addresses of the successor node and the precursor node. So when storing the same amount of data, two-way linked lists take up more memory space than single linked lists.

Although two pointers in the two-way linked list waste storage space, it can support two-way traversal, which also brings the flexibility of two-way linked list operation.

From the point of view of the structure of the two-way linked list, the precursor node can be found in the case of O (1) time complexity, so in some cases, the insertion and deletion operation of the two-way linked list is more simple and efficient than the single linked list. In fact, the time complexity of inserting and deleting single linked lists mentioned above is O (1).

2.4 comparison of deletion and insertion operations between single and two-way linked lists

Delete operation

When you delete a data from a linked list, it is usually the following two cases:

Delete a node whose "value is equal to a given value"

Delete the node pointed to by the given pointer

In the first case:

We need to find the node whose value is equal to the given value, and then delete it after finding the node.

In this case, either a single linked list or a two-way linked list needs to start a traversal comparison from the header node until a node whose value is equal to the given value is found. In this case, the time complexity of single linked list and bi-directional linked list search is O (n), and the time complexity of deletion is O (1). According to the addition rule in time complexity analysis, the total time complexity of the linked list operation of the node whose deletion value is equal to a given value is O (n). In this case, a single linked list is as efficient as a two-way linked list.

In the second case:

Although we can find the node to be deleted directly according to the pointer, deleting a node Q needs to know its precursor node, but the single linked list does not support obtaining the precursor node directly. in this case, in order to find the precursor node, we also need to traverse the single linked list from the header node until p-> next=q, indicating that p is the precursor node of Q.

But in this case, the two-way linked list has an advantage, because the nodes in the two-way linked list already hold the pointer of the precursor node and do not need to go through it all over again like a single linked list. So in this case, the time complexity of the single linked list deletion operation is O (n), while the time complexity of the two-way linked list is O (1).

Insert operation

Similarly, in the insert operation, according to the analysis idea of the delete operation, we can know that the time complexity of the two-way linked list is O (1) and the time complexity of the one-way linked list is O (n).

Two-way linked list in addition to delete, insert operation has advantages, but also for an ordered linked list. The query efficiency of two-way linked list by value is also higher than that of single linked list.

Because in the two-way linked list, you can record the location p of the last search, and in each subsequent search, you can decide whether to look forward or backward according to the relationship between the value you want to look for and the corresponding value of the p location, so you only need to find half of the data on average.

The data structure of bi-directional linked list is used at the bottom of LinkedHashMap in java.

In the process of our usual development, we have the design ideas of "exchanging space for time" and "exchanging time for space".

When the memory space is sufficient, if you pursue the execution speed of the code, you will choose algorithms or data structures with relatively high space complexity and relatively low time complexity.

If memory is scarce, algorithms or data structures with relatively low space complexity and high time complexity will be selected.

If you integrate a circular linked list and a two-way linked list, it is combined into a "two-way cyclic linked list".

Performance comparison between array and linked list

From the previous study, we know that the memory storage of array and linked list is different, so the time complexity of insert, delete and random access operations is just the opposite.

Of course, you can't just use the time complexity to decide whether to use an array or a linked list, it also depends on the situation.

The array is easy to use, applying for continuous memory space, and the data in the array can be pre-read with the help of CPU's caching mechanism, so that random access will be more efficient. The memory space in the linked list is not contiguous, so the CPU cache mechanism cannot be used and there is no way to effectively pre-read.

The biggest disadvantage of the array is that the size is fixed, and once declared, it will occupy the whole block of continuous memory space. If the applied memory space is too large, when the system does not have enough continuous memory space, it will lead to insufficient memory (out of memory). If the declared array is too small, it may not be enough. At this point, you need to apply for a larger memory space and copy the data in the original array, which is very time-consuming. The linked list itself has no size limit and supports dynamic expansion. This is also the biggest difference between arrays and linked lists.

If the code requires a lot of memory, it is recommended that you use an array. Because each node in the linked list consumes extra storage space to store a pointer to the next node, the memory consumption doubles. Moreover, frequent insertions and deletions of linked lists will lead to frequent memory requests and releases, which can easily lead to memory fragmentation. If you are in java, it is possible to result in frequent GC.

Therefore, in the actual development process, for different types of projects, we should weigh whether to use arrays or linked lists according to the specific situation.

The skill of writing linked list code

I talked about the basic knowledge of linked list, but it is not so easy to write a good linked list code. Here are a few tips on how to write linked list code. If you can master these skills skillfully, and then practice more, I believe you can easily write the linked list code in the future.

4.1 understand the meaning of pointers or references

In some languages, there is the concept of "pointer", such as C language, citation; in some languages, there are no pointers and references are replaced by "references", such as java and Python. In fact, whether it is "pointer" or "reference" they all mean the same thing, and they all store the memory address of the referred object.

A pointer or reference can be understood as assigning a variable to a pointer is actually assigning the address of the variable to the pointer. Or: the pointer stores the memory address of the variable, points to the variable, and the variable can be found through the pointer.

For example, linked list code 1:

P-> next = Q

This code means that the next pointer in the p node stores the memory address of the Q node.

Linked list code 2:

P-> next=p- > next- > next

The next pointer of the p node stores the memory address of the next node of the p node.

Mastering the concept of pointers or references is a prerequisite for understanding linked list code.

4.2 simplify the difficulty of implementation with sentinels

To insert a new node after node p of the above single-linked list, you only need the following two lines of code:

New_node- > next = p-> next

P-> next = new_node

However, when we insert a node into an empty linked list, the above two lines of code will not work, and we need to do some special processing first:

If (head = = null) {

Head = new_node

}

Where head represents the head node of the linked list. Therefore, it can be found that for the insertion operation of a single linked list, the insertion logic of the first node is different from that of other nodes.

Let's take a look at the delete operation of the single-linked list node. If you want to delete the successor node of node p, then one line of code is fine:

P-> next = p-> next- > next

However, if you want to delete the last node in the linked list, the previous deletion code will not work, and you also need to do special processing first:

If (head- > next = = null) {

Head = null

}

From the above analysis, we can see that for the insertion and deletion of the linked list, special treatment is needed for the insertion of the first node and the deletion of the last node. In this way, the implementation of the code will not only appear tedious, but also prone to errors. If we introduce the sentinel node at this time, the head pointer will always point to the sentry node at any time, regardless of whether the linked list is empty or not. The linked list with sentinel nodes is called "lead linked list", and the linked list without sentinel nodes is called "no lead linked list".

Sentinel nodes do not store data. Because the sentinel node exists all the time, inserting the first node and inserting other nodes, deleting the last node and deleting other nodes can all use the same code to implement the logic.

The use of this sentry simplifies the difficulty of programming. It is used in insertion sorting, merging sorting and dynamic programming.

To deepen our understanding, take an example of C code:

Code 1:

/ / in array a, find key and return the location where key is located.

/ / where n represents the length of the array a

Int find (char* a, int n, char key) {

/ / Boundary condition processing, if an is empty, or n

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.