Double linked list design and implementation of Java data structure and algorithm

In the single linked list analysis, we can know that each node has only one next field pointing to the successor node. If we know the current node P and need to find its precursor node, we must traverse from the head head pointer to the precursor node of P. the operation efficiency is very low. Therefore, if p has a next field pointing to the precursor node, the efficiency is much higher, The linked list that contains the precursor node domain pre and the successor node domain next in one node is called double linked list. In this article, we will analyze the double linked list from the following nodes

Design and implementation of double linked list

The main advantage of double linked list is that for any given node, its predecessor node or successor node can be easily obtained, and the main disadvantage is that each node needs to add additional next field, so it needs more space overhead. At the same time, the insertion and deletion operations of nodes will be more time-consuming, because more pointer pointing operations are required. The structure diagram of the double linked list is as follows:

Create the headdoubleilinkedlist class and implement the ilinekedlist interface (the same as the interface in the previous blog post)

The node class structure is as follows:

Through the analysis in the previous part, we are also familiar with the insertion, deletion, search, replacement and other operations of the linked list. Therefore, for the implementation of the double linked list, we mainly analyze its insertion, deletion, search, replacement and other methods. For others that have not been analyzed, we can look at the implementation source code (finally, we will give the implementation code of the double linked list)

Analysis and implementation of double linked list insertion operation

Let's first look at the insertion of double linked list. Although there are header nodes without data, it is a two-way linked list, so there are two situations to insert double linked list: one is to insert empty double linked list and tail, and the other is to insert in the middle of double linked list, as shown in the following figure. Insert value x in empty double linked list:

It can be seen from the figure that (a) and (b) belong to the same situation. It is necessary to pay attention to the case of front. Next! = null, otherwise the pointer will be null. While (c) belongs to intermediate insertion, and there is no need to ignore the condition of front. Next! = null, because the subsequent nodes will not be null at any time during intermediate insertion. The implementation code of the insertion method is as follows:

Analysis and implementation of deletion operation of double linked list

The deletion operation of the double linked list is similar to the insertion operation in principle. We can see that (a) and (b) belong to the same situation. It is necessary to prevent p.next.prev from throwing the pointer empty. For (c), it is not necessary to relate the value of p.next.prev. The specific implementation of deletion is as follows:

Analysis and implementation of double linked list lookup operation

The operation of finding the value of a double linked list is no different from that of a single linked list. Just find the current node to find and obtain its value, as follows:

The code implementation is as follows:

Analysis and implementation of replacement value operation of double linked list

In the replacement value process of double linked list, you need to find the node to be replaced first. This process is the same as the process of obtaining the value. After finding the node, you can directly replace the value and return the old value. It's relatively simple, and you can directly use the following code:

OK ~, the main operation implementation of this double linked list has been analyzed. The implementation source code of the double linked list is given below:

Design and implementation of circular double linked list

If the next pointer field of the last node of the double linked list points to the head node and the prev pointer of the head node points to the last node of the head, a circular double linked list is formed. Its structure is shown as follows:

In the circular double linked list, we no longer need to point to the tail node, because the whole linked list has formed a loop, and the position of the tail node can be easily obtained at the head node. For the insertion and deletion of the circular double linked list, there is no need to distinguish the position operation. This is because the particularity of the circular double linked list makes p.next Pre can never be null, so our code implementation is relatively simple when inserting and deleting. Let's first analyze the insertion operation of circular double linked list, as shown below:

We can see that (a), (b) and (c) do not need the difference of relationship position insertion. The code implementation is as follows:

The deletion operation of circular double linked list is shown as follows:

Figure displaying the deletion operation of double linked list

Similarly, from the figure, we can also find that due to the characteristics of circular double linked list, there is no need to distinguish the operation position in the three cases (a), (b) and (c). The code implementation is as follows:

As for the lookup value and replacement value of the circular double linked list, there is not much difference between the circular double linked list and the double linked list, but it should be noted that when traversing the circular double linked list, the end flag is no longer whether the tail node is empty, but whether the next pointer of the tail node points to the head node. OK ~, let's give the implementation code of circular double linked list:

Implementation of sorting circular double linked list

The so-called sorting circular double linked list means that when inserting elements, instead of finding the insertion position according to the index flag, it looks for the insertion position according to the size of the value, but there is an insertion value data that must be the parent class of T or T, and the comoarable interface is implemented. The implementation of sorting circular double linked list is relatively simple. We only need to inherit the previous circular double linked list and rewrite the add method. The main code implementation is as follows:

Analysis of execution efficiency of double linked list

In fact, the analysis in the previous article is almost the same. Here we briefly explain that the execution efficiency of the linked list is relatively high when inserting and deleting elements. From the perspective of the insertion operation, we assume that the front points to a node in the two-way linked list. At this time, the time consumed by inserting the successor node or predecessor node of the front is a constant time o (1), The efficiency of inserting the front precursor node is better than that of the single linked list, and there is no need to traverse from the beginning, but the above is discussed from the case of knowing the front node in the two-way linked list. From the operation of the implementation code, whether inserting or deleting, you need to find the insertion node or deletion node, and the time spent in accessing the node in this process is O (n). Therefore, the time complexity of the insertion or deletion operation or value lookup operation of the double linked list is O (n). As for why the linked list is more suitable for insertion and deletion, we discussed in the previous article, I won't repeat it here. Finally, a comparison table of linked list, array and dynamic array is given:

Design principle of XOR efficient storage double linked list

In the implementation of the double linked list analyzed above, we need a forward pointer to the successor node and a reverse pointer to the predecessor node. For this reason, we need a data field data, a pointer to the successor node next and a pointer prev to the predecessor node when constructing a node class. However, in order to design more efficient and save storage space, a bidirectional linked list based on pointer difference operation was born. Each node of this linked list is still the same as the single linked list. Only one pointer field is used to design the two-way linked list. The new two-way linked list node class structure is as follows:

The ptrdiff field stores the address difference between the successor node and the predecessor node. The pointer difference is realized by XOR operation (for those unfamiliar with XOR, see another article of the blogger: Java operator). We use XOR operation here, and the following calculations are made:

Pridiff = address of the successor node address of the predecessor node

As shown in the figure above, we use XOR difference to calculate the position of each node:

So why can it be calculated like this? Let's first understand the characteristics of XOR:

Therefore, we can easily find the object of the node by using the above XOR feature. For example, if P wants to move from node C to node B, and the ptrdiff value of C is known to be BD, then we need to perform XOR operation between the ptrdiff value of node C and the address of node D. at this time, we can get the address of B. the calculation process is as follows:

If you want to move from node C to node D, the calculation is as follows:

Therefore, the movement of the two-way linked list can be realized through a pointer field of next, and this storage efficient two-way linked list can also save space overhead. In fact, the introduction to the storage efficient double linked list comes from the classic problem analysis of data structures and algorithms. However, bloggers found that this storage efficient linked list is easier to implement in C language, because C language can obtain objects through pointers (addresses) and operate directly. However, in Java language, bloggers did not think of how to realize this storage efficient linked list, At least we haven't thought of a feasible solution yet. Google has a handful of implementation languages, all of which are C, but we haven't found a java implementation, However, bloggers think that this storage efficient linked list is not suitable for Java implementation (only personal point of view). If there is an implementation scheme, please leave a message and thank you. However, the idea of algorithm design is quite good. Ok~, let's talk about the two-way linked list for the time being.

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.