preface
Linear lists (sequential lists and linked lists) have been talked about in detail before. Linked lists were mainly talked about at that time, but in actual application, double-linked lists are more commonly used, such as LinkedList.
Double linked lists are different from single linked lists
Logically, they are all chained implementations of linear lists. The main difference is that the structure of nodes is different, and this difference causes some differences in operation. Singly linked lists:
A node in a singly linked list that stores datadataAnd there are rear-drive nodesnext(Pointer). So this single linked list, if you want to go through anything, you have to go through itFront nodes – > back nodes.
Double linked list:
A node in a doubly linked list that stores datadata, there are also rear drive nodesnext(pointer), which is the same as a singly linked list, but it also has a precursor nodepre(Pointer).
Design of double linked list structure
When we talked about single-linked lists, we were designing a list of leading nodes and we missed the operation of non-leading nodes, so we’re not going to design a list of leading nodes. In addition, there is no tail pointer in the single-linked list implementation above. Here, we design a double-linked list with a tail pointer.
So we construct a double-linked list: no leading node, tail, bidirectional list.
For nodes:
class node<T> {
T data;
node<T> pre;
node<T> next;
public node(a) {}public node(T data) {
this.data = data; }}Copy the codeFor linked lists:
public class doubleList<T> {
private node<T> head;/ / head node
private node<T> tail;/ / end nodes
private int length;
// Various methods
}
Copy the codeSpecific operation analysis
For a linked list, the main operation is to add and delete. If you add and delete, you not only need to consider whether the linked list is the lead node, but also the head insert, tail insert, middle insert and delete forms. Some of the details are also more important (to prevent the collapse of the linked list). If you do not understand this deeply, it is easy to write wrong and difficult to check out. Of course, list lookup and bitwise modification are much easier than adding and deleting.
Initialize the
Double-linked lists start with a null header pointer. So for this double-linked list with no leading node. Its head always points to the first truly valid node. Tail also points to the last valid node. At first head=null and tail=head, the list is empty waiting for the node to be inserted.
public doubleList(a) {
head = null;
tail = head;
length = 0;
}
Copy the codeinsert
Empty linked list insertion
- For an empty list. Adding the first element is a special consideration. Because when the list is empty
headandtailAll is null. But head and tail need to actually point to real data in the linked list (the head pointer doesn’t matter). So I’m going to create a new onenodeletHead and tail are equal to it.
node<T> teamNode = new node(data);
if (isEmpty()) {
head = teamNode;
tail = teamNode;
}
Copy the codeHis head
For head insertion. The steps are simple, considering only changes to the head node.
- Create an insert node node
- The head precursor points to node
- The node rear drive points to the head
- Head points to node. (Head is only the second node, and head needs to indicate the first node to change direction)
Insert the tail:
For tail insertion. Just consider the variation of the tail node.
- Create an insert node node
- The node precursor points to tail
- Tail The rear drive points to a node
- Tail Points to a node. (Tail is only the penultimate node, and tail is the last node to point to node.)
Insert by number
For numbering inserts. Consider both lookup and insert, and insert has nothing to do with head or tail.
1 Create a node to be inserted
2 Locate the preNode that precedes the node to be inserted. And the nextNode nextNode
The rear driver of 3 nodes points to nextNode, and the front driver of nextNode points to Node (at this point, node and rear are linked to the list, but separated from the previous state).
4 preNode The rear drive points to a node. Node precursors point to preNodes (insert complete)
Dynamic diagram of the whole process:
delete
Only a single node is deleted
No matter head or tail delete, encounter single node delete need to re-initialize the linked list!
if (length == 1)// There is only one element
{
head = null;
tail = head;
length--;
}
Copy the codeHead to delete
Note that header deletion is only relevant to the head node when the deletion is not null
The process can be roughly divided into:
1 Change the pre pointer of the rear drive node of the head node to null. (The node after the head refers to the head but removes the first node from the head.)
Next (the head is the first node we need to delete, and the first node is deleted successfully. If you have c++ or other languages, the first node is deleted, but Java will automatically release)
The tail to delete
Note that when a tail is not empty, the tail is only associated with the tail node. Remember that in a regular linked list, we delete the tail node by finding the precursor of the tail node. The entire table needs to be traversed, whereas bidirectionally linked lists can be traversed directly from the last node to the front.
Tail deletion is to delete the last node in the bidirectional linked list, that is, the node pointed to by the tail pointer. The idea is the same as the idea of header deletion, and the specific steps are as follows:
tail.pre.next=nullThe back-end node of the preceding node (pre) of the tail node is equal to nulltail=tail.preThe tail node points to its precursor node, where the tail node is due to the step1Next is null. Remove it
Ordinary delete
Common deletion needs to be mastered, and the relationship between nodes to be deleted needs to be properly handled. The specific process is as follows:
1: Find and call the prenode of the node to be deleted (prenode.next is the node to be deleted)
2: prenode.next-next-pre = preNode. (Set aftNode’s pre pointer to prenode, equivalent to aftNode. Pre =prenode)
3: prenode.next=prenode.next.next; The node is skipped and deleted successfully.
Dynamic diagram of complete deletion process:
Implementation and Testing
Through the above ideas to achieve a simple double linked list, of course, some places named not too standard, the implementation of efficiency to be improved, the main purpose is still with you to understand.
Code:
/* * does not include the */ of the leading node
public class doubleList<T> {
class node<T> {
T data;
node<T> pre;
node<T> next;
public node(a) {}public node(T data) {
this.data = data; }}private node<T> head;/ / head node
private node<T> tail;/ / end nodes
private int length;
public doubleList(a) {
head = null;
tail = head;
length = 0;
}
boolean isEmpty(a) {
return length == 0 ? true : false;
}
void addFirst(T data) {
node<T> teamNode = new node(data);
if (isEmpty()) {
head = teamNode;
tail = teamNode;
} else {
teamNode.next = head;
head = teamNode;
}
length++;
}
void add(T data)// The tail node is inserted by default
{
node<T> teamNode = new node(data);
if (isEmpty()) {
head = teamNode;
tail = teamNode;
} else {
tail.next = teamNode;
teamNode.pre=tail;
tail = teamNode;
}
length++;
}
int length(a)
{
return length;
}
T getElum(int index)// Start from scratch for simplicity
{
node<T> team=head;
for(int i=0; i<index; i++)// The number of times that no leading node is traversed is -1
{
team=team.next;
}
return team.data;
}
void add(int index, T data)// Insert the number
{
if (index == 0) {
addFirst(data);
} else if (index == length) {
add(data);
} else {/ / key
node teampre = head;// is the insertion precursor
// Headless node, index-1 to find the precursor node
for (int i = 0; i < index -1; i++)
{
teampre = teampre.next;
}
node<T> team = new node(data);// insert B into a c
team.next = teampre.next;// B.next=c
teampre.next.pre = team;// c.pre=B
team.pre = teampre;// associate a with Bteampre.next = team; length++; }}void deleteFirst(a)// Delete the header
{
if (length == 1)// There is only one element
{
head = null;
tail = head;
length--;
} else{ head = head.next; length--; }}void deleteLast(a) {
if(length==1)
{
head=null;
tail=head;
length--;
}
else {
tail.pre.next=null; tail=tail.pre; length--; }}void delete(int index)
{
if(index==0)deleteFirst();
else if (index==length-1) {
deleteLast();
}
else {// Delete the node from scratch to understand unity
node<T>team=head;
for(int i=0; i<index-1; i++) { team=team.next; }//team insert B a into team
team.next.next.pre=team;// The precursor of c becomes a
team.next=team.next.next;// the back drive of a becomes clength--; }}void set(int index,T data)
{
node<T>team=head;
for(int i=0; i<index-1; i++) { team=team.next; } team.data=data; }@Override
public String toString(a) {
node<T> team = head;
String vaString = "";
while(team ! =null) {
vaString += team.data + "";
team = team.next;
}
returnvaString; }}Copy the codeTesting:
conclusion
In the insert and delete step, many people may not understand because of the tedious process, but in fact this operation may be written in a variety of ways, but the essence of the operation is the same, so it is normal to see differences in other versions.
Next, I’ll show you a trick, if it’s on the right of equals, it’s a node, and if it’s on the left of equals, it’s all nodes except the last dot next. For example node.next-next-next can be thought of as (node.next-next).next.
When doing data structure and algorithm linked list related problems, different problems may give different nodes to complete the insertion and deletion operation. In this case, you need to be careful not to break the linked list structure.
Original public number: Bigsai original is not easy, if there is a harvest please don’t mean your one key three even! Articles have been included in the web-focused Data structure and algorithm learning Repository welcome to STAR
Code operation may be some optimization space, but also ask you to correct! Remember one key three support!