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

This article mainly introduces "how to use double linked list". In daily operation, I believe many people have doubts about how to use double linked list. Xiaobian consulted all kinds of materials and sorted out simple and easy operation methods. I hope to help you answer the doubts about "how to use double linked list"! Next, please follow the small series to learn together!

Difference between double linked list and single linked list

Logically they are both chained implementations of linear tables, the main difference being the construction of the node structure, which leads to some differences in operation.

Single-linked list:

A node of a single-linked list, with data for storing data, and a next(pointer) node. That is to say, if you want to traverse a single-linked list, you have to go through the previous node-> the next node.

Double-linked list:

A node of a double linked list has data for storing data and next(pointer), which is the same as a single linked list, but it also has a predecessor node pre(pointer).

Design of Double Linked List Structure

When we talked about the single-linked list above, we were designing a linked list with a leading node and missed the operation mode without leading nodes. Here, we will not take the lead in designing and implementing the linked list. And when the single-linked list above is implemented, there is no tail pointer tail, where we design the double-linked list with tail pointer.

So we construct this double linked list: no head node, tail pointer (tail), double linked list.

For node nodes: class node { T data; node pre; node next; public node() { } public node(T data) { this.data = data; } } For lists: public class doubleList { private head node;//head node private node tail;//tail node private int length; //various methods } Specific operation analysis

For a list of the main operations or add and delete. Add and delete words not only need to consider whether the list is the leading node, there are head insertion, tail insertion, middle insertion and other forms of insertion and deletion, some of which are also more important details (to prevent the list collapse error), if you do not understand this in-depth it is easy to write wrong is also difficult to find out. Of course, the lookup and bitwise modification operations of the linked list are still much easier than the addition and deletion operations.

initialization

At first the head pointer of the doubly linked list points to null. So for this doubly linked list without the head node. Its head always points to the first truly valid node. tail also points to the last valid node. Initially head=null and tail=head, the list is empty and waiting for the node to be inserted.

public doubleList() { head = null; tail = head; length = 0; } Insert Empty List Insert

For empty lists. The addition of the first element can be considered specially. Because both head and tail are null when the list is empty. But the head and tail need to actually point to the real data in the list (the head pointer does not need to be considered). So at this point, create a new node so that head and tail are equal to it.

node teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; } Head insertion

For head insertion. The steps are simple, just consider the changes in the head node.

HarmonyOS Technology Community

New insertion node

The head points to the node.

Node drives back to head

Head points to node. (In this case, the head only indicates the second node, and the head needs to indicate the first node, so it changes its direction)

Tail insertion:

For tail insertion. Just consider the tail node tail node changes.

HarmonyOS Technology Community

New insertion node

node precursor tail

tail points to node

tail points to node. (In this case, tail only indicates the penultimate node, and tail needs to indicate the last node, so it points to node)

insert by number

For number insertion. Consider finding and inserting, and insert is independent of either head or tail.

1 New insertion node

2 Find the node preNode before the node you want to insert. and the next node nextNode

3 node backdrive points to nextNode,nextNode forerunner points to node(at this time node and the back have been linked with the linked list, but they are separated from the previous processing)

4 preNode points to node. node precursor points to preNode(insert complete operation completed at this time)

The dynamic diagram of the whole process is as follows:

Delete Only a single node Delete

Regardless of whether the head or tail delete, encounter a single node delete need to re-initialize the linked list!

if (length == 1)//only one element { head = null; tail = head; length--; } header deleted

Head deletion needs to be noted that when deletion is not empty, head deletion is only related to the head node

The process is roughly divided into:

The first pointer to the node behind the head node is changed to null. (head The next node originally points to head, but to delete the first one, let the latter one sever the relationship with head first)

2 head node points to head.next(this way head points to the first node we need, the previous node will be deleted successfully, if there are languages such as c++, the first isolated node will be deleted and released, but Java will automatically release)

tail deletion

Tail deletion needs to be noted that when deletion is not empty, tail deletion is only related to tail nodes. Remember that in a normal linked list, we delete the tail node by finding its predecessor. The entire table needs to be traversed, whereas a doubly linked list can be traversed directly from the tail node to the front.

Tail deletion is to delete the last node in the doubly linked list, that is, the node pointed to by the tail pointer. The idea is the same as that of head deletion. The specific steps are as follows:

HarmonyOS Technology Community

tail.pre.next =null The node immediately preceding (pre) the trailing node equals null

tail=tail.pre The tail node points to its predecessor node, which is null due to step 1next. completed the delete

general deletion

Ordinary deletion needs to be mastered, and ordinary deletion needs to properly handle the relationship between the nodes to be deleted. The specific process is as follows:

1: Find the predecessor node of the node to be deleted (prenode.next is the node to be deleted)

2 : prenode.next.next.pre=prenode. (Point the pre pointer of aftnode to prenode, equivalent to aftnode.pre=prenode)

3: prenode.next = prenode.next.next; node is skipped and deleted successfully.

The dynamic diagram for completing the deletion of the entire process is:

implementation and test

Through the above ideas to achieve a simple double linked list, of course, some places are not very standardized naming, efficiency needs to be improved, the main purpose is to bring everyone to understand.

Code (code posted in the form of pictures, if you need source code can read the original or add my friend to send you):

Testing:

At this point, on "how to use double linked list" learning is over, I hope to solve everyone's doubts. Theory and practice can better match to help everyone learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

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.