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

This article introduces the relevant knowledge of "what is a double-linked list". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The difference between double linked list and single linked list

Logically, they are all linked implementations of linear tables, and the main difference is that the structure of nodes is different, which leads to some differences in operations. Single linked list:

A node in a single linked list that has a data for storing data and a backdrive node next (pointer). That is, if the single linked list wants some traversal, it has to go through the front node-> the back node.

Double linked list:

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

Design of double linked list structure

When talking about the single linked list above, we missed the operation mode of the lead node when we designed a lead node linked list, and here we do not take the lead in the node design and implementation of the double linked list. And the above single-linked list is implemented without a tail pointer tail, here we design a double-linked list with a tail pointer.

So the double linked list we constructed is: no lead node, tail pointer (tail), two-way linked list.

For node nodes:

Class node {T data; node pre; node next; public node () {} public node (T data) {this.data = data;}}

For linked lists:

Public class doubleList {private node head;// head node private node tail;// tail node private int length; / / various methods} specific operation analysis

The main operation for a linked list is to add or delete. If you add or delete, you need to consider not only whether the linked list takes the lead node, but also a variety of insertion and deletion forms, such as head insertion, tail insertion, middle insertion and so on. Some of the details are also important (to prevent the list from collapsing). If you don't have a deep understanding of this piece, it's easy to make mistakes and it's hard to troubleshoot them. Of course, the linked list search, bit-by-bit modification operation is still much easier than the add and delete operation.

Initialization

The header pointer to the double-linked list initially points to null. So for this double-linked list without leading nodes. Its head always points to the first real and valid node. Tail also points to the last valid node. At the beginning, head=null, and tail=head, where the linked list is empty, waiting for the node to insert.

Public doubleList () {head = null; tail = head; length = 0;} insert

Empty linked list insertion

For empty linked lists. The addition of the first element can be given special consideration. Because both head and tail are null when the linked list is empty. However, head and tail need to actually point to the real data in the linked list (the lead pointer does not need to be considered). So 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 header insertion. The steps are simple and only need to consider the changes in the head node.

Create a new insert node node

The head precursor points to node

The node rear drive points to head.

Head points to node. (in this case, head only represents the second node, while head needs to represent the first node, so change the direction.)

Tail insert:

For tail insertion. You only need to consider the change of the tail node tail node.

Create a new insert node node

The node precursor points to tail

The tail rear drive points to node.

Tail points to node. (in this case, tail only represents the penultimate node, while tail needs to represent the last node, so it points to node.)

Insert by number

For number insertion. Consider finding and inserting, and inserting has nothing to do with head or tail.

1 create a new insert node node

2 find the previous node preNode that you want to insert into the node. And the latter node nextNode

3 node rear drive points to nextNode,nextNode front drive points to node (at this time node and back are linked to the linked list, but separate from previous processing)

The 4 preNode rear drive points to node. The node precursor points to preNode (insert the complete operation at this time)

The dynamic diagram of the whole process is as follows:

Delete

Only a single node is deleted

> regardless of head deletion or tail deletion, the linked list needs to be re-initialized when a single node is deleted.

If (length = = 1) / / there is only one element {head = null; tail = head; length--;}

Head deletion

> one thing to note about header deletion is that deletion is not empty when waiting header deletion is only related to the head node.

The process is roughly divided into:

The leading pointer of the trailing node of the 1 head node is changed to pre to null. (the node behind head originally points to head, but to delete the first one, let the latter one sever from head.)

2 head node points to head.next (so head points to the first node we need, and the previous node is deleted successfully. If there is a language such as C++, the first isolated node can be deleted and released, but Java will be released automatically)

Tail deletion

> tail deletion should be noted that when deletion is not empty, tail deletion is only related to the tail node. Remember that in the normal linked list, we need to find the precursor node of the tail node when we delete the tail node. You need to traverse the entire table, while a two-way linked list can traverse directly from the tail node to the front.

Tail deletion is to delete the last node in the two-way linked list, that is, the node that the tail pointer points to. The idea is the same as the idea of head deletion. The specific steps are as follows:

The trailing node of the previous node (pre) of the tail.pre.next=null tail node is equal to null

The tail=tail.pre tail node points to its precursor node, and the tail node is already null due to step 1next. Complete deletion

Normal deletion

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

1: find the precursor node prenode of the node node to be deleted (prenode.next is the node to be deleted)

2: prenode.next.next.pre=prenode. (point the pre pointer of the backdrive node aftnode of node to be deleted to prenode, which is equivalent to aftnode.pre=prenode)

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

The dynamic diagram for completing the deletion process is as follows:

Implementation and testing

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

Code:

/ * * public class doubleList {class node {T data; node pre; node next; public node () {} public node (T data) {this.data = data;}} private node head;// header Node private node tail;// tail Node private int length Public doubleList () {head = null; tail = head; length = 0;} boolean isEmpty () {return length = = 0? True: false;} void addFirst (T data) {node teamNode = new node (data); if (isEmpty ()) {head = teamNode; tail = teamNode;} else {teamNode.next = head; head = teamNode;} length++ } void add (T data) / / default tail node insert {node teamNode = new node (data); if (isEmpty ()) {head = teamNode; tail = teamNode;} else {tail.next = teamNode; teamNode.pre=tail; tail = teamNode;} length++ } int length () {return length;} T getElum (int index) / / for simple unification, find {node team=head; for (int iTuno) from scratch.

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.