Make writing a habit together! This is the 12th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
⭐️ ⭐️
This article take you know data structure and algorithm of double linked list, the list is a continuous logical structure, physical structure of discrete data structure, can be divided into two categories, singly linked lists and double linked list, add or delete text will introduce the double linked list to check, for the list of concept has been in a table of the data structure and algorithm of single has been introduced in this paper, Therefore, the concept of linked list theory is no longer described in this paper, the last time to achieve a single linked list without the lead node, this time to introduce a lead double linked list! Description code: Java.
📒 blog homepage: not seen flower smell blog homepage 🎉 welcome to pay attention to 🔎 like 👍 collect 🎉 🎉 message 📒 📆 Nuggets debut: 🌴 April 13, 2022 🌴 ✉️ Perseverance and hard work will be exchanged for poetry and distance! 💭 refer to books: 📚 “interesting learning data structure”, 📚 “data structure” 💬 refer to online programming website: 📚 niuke.com Falikou blogger’s code cloud Gitee, usually the program code written by the blogger are in it. Github of the blogger, the program code written by the ordinary blogger is in it. 🍭 author level is very limited, if you find mistakes, be sure to inform the author in time! Thank you, thank you!
1. Theoretical basis of double linked lists
1.1 Basic structure of doubly linked lists
We know that there are 8 types of linked lists in practice. Many types of linked lists can be derived according to whether there are lead nodes, whether there are loops, and references pointing to these three points, but they are essentially the same. They are always discrete in physical structure and continuous in logical structure. This article will introduce the non-cyclic double – linked list of the leading node, hereinafter referred to as double – linked list. First of all, no matter what type of linked list, the basic structure of its nodes is the same, they are all data domain + reference (pointer) domain. Single linked list reference domain has only one direction pointing, while double linked list reference domain has front and back bidirectional pointing.
The next field of the head node always points to the first node, the prev field always points to NULL, and if the list is empty, the next field also points to null.
1.2 The difference between double and single linked lists
The biggest difference between single linked list and double linked list is direction, single linked list is one-way, can only “grow” in one direction, double linked list is two-way, can “grow” in both directions. When traversing a linked list, a singly linked list can only find the successor, but not the precursor, while a doubly linked list can find both. When deleting a target node, a singly linked list must know its precursor to delete the target node, while a doubly linked list can delete the target node without knowing its precursor.
2. Double linked lists from theory to practice
2.1 Double-linked list nodes
class DoubleLinkedListNode {
public int val;/ / data domain
public DoubleLinkedListNode next;// point to the successor
public DoubleLinkedListNode prev;// point to the precursor
public DoubleLinkedListNode(int val) {
this.val = val;// constructor}}Copy the code
2.2 Double linked list (lead node) class
public class DoubleLinkedList {
public DoubleLinkedListNode head;/ / head node
public DoubleLinkedList(a) {
this.head = new DoubleLinkedListNode(0);
}
// Function implementation method
}
Copy the code2.3 Double linked list to add, delete, check and change
2.3.1 Printing of double linked list
So this is very simple, just going through a double-linked list.
public void display(a){
DoubleLinkedListNode cur = head.next;
while(cur ! =null) {
System.out.print(cur.val + "");
cur = cur.next;
}
System.out.println();
}
Copy the code2.3.2 interpolation
If the list is not empty, the new node points to the next node, and then the head node points to the new node.
If the list is empty, you do not need to complete step 2 in the figure (that is, you do not need to point head.next-prev to the new node).
/ / head interpolation
public void addFirst(int data){
DoubleLinkedListNode node = new DoubleLinkedListNode(data);
node.next = head.next;
if(head.next ! =null) {
head.next.prev = node;
}
head.next = node;
node.prev = head;
}
Copy the code2.3.3 interpolation
Find the last node in the list and insert the last node. If the list is empty, the last node may be the head node.
/ / stern interpolation
public void addLast(int data) {
DoubleLinkedListNode cur = this.head;
while(cur.next ! =null) {
cur = cur.next;
}
DoubleLinkedListNode node = new DoubleLinkedListNode(data);
cur.next = node;
node.prev = cur;
}
Copy the code2.3.4 Obtaining the linked list length
Just iterate.
// Get the length of the double-linked list
public int size(a){
int cnt = 0;
DoubleLinkedListNode cur = this.head.next;
while(cur ! =null) {
cnt++;
cur = cur.next;
}
return cnt;
}
Copy the code2.3.5 Insert it in any Position
It can be divided into three situations:
- After insertion at zero, the head node, use the head interpolation method.
- Insert at the position subscript size of the linked list, using the tail interpolation method.
- In other cases, insert as shown.
If the insertion position is illegal, either return or throw the exception directly. In the single linked list implementation, we used the direct return method, this time using throw exception. Exception custom, need to inheritRuntimeExceptionorException, the former is the parent class of runtime exceptions, which is checked at run time, and the latter is the parent class of various exceptions, which is checked at compile time. In this case, we don’t know whether the subscript value passed in is valid until we run it, so we need to inherit when we customize the exceptionRuntimeExceptionClass.
An exception can be thrown using a try… catch… Statement capture, which is briefly demonstrated here, but if it does not return directly, the exception will be covered in more detail in a future blog post.
try{
// possible exception statements;
dls.addIndex(20.10);// There may be an illegal subscript
}catch(IndexExcept(catch exception classes) e(reference variables)) {// Catch an exception
e.printStackTrace();// Displays abnormal information
}
Copy the codeclass IndexExcept extends RuntimeException{
public IndexExcept(String message) {
super(message); }}Copy the code // Insert the first data node with subscript 0 at any position
public void addIndex(int index,int data) throws IndexExcept{
if (index < 0 || index > size()) {
throw new IndexExcept(index + "Illegal location!");
}
if (size() == 0) {
addFirst(data);
return;
}
if (size() == index) {
addLast(data);
return;
}
DoubleLinkedListNode node = new DoubleLinkedListNode(data);
DoubleLinkedListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
node.next = cur.next;
cur.next.prev = node;
node.prev = cur;
cur.next = node;
}
Copy the code2.3.6 Determine whether a data is in the linked list
Traverse to find.
// Check whether the key is included in the single linked list
public boolean contains(int key){
if (this.head.next == null) {
return false;
}
DoubleLinkedListNode cur = head.next;
while(cur ! =null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
Copy the code2.3.7 Deleting nodes of a double-linked list
If cur.next=null, make cur.prev = cur.next. Otherwise, next points to the next node and prev points to the previous node. When the list is empty, it can either return directly or throw an exception. Last time we implemented a single list, we used the method of return. This time we try to throw a custom exception.
Exception customization. You need to inherit RuntimeException or Exception. The former is the parent class of the Exception when running, which is checked at runtime, and the latter is the parent class of each Exception, which is checked at compile time. In this case, we don’t know if the list is empty until we run it, so we need to inherit the RuntimeException class when we customize the exception.
class LinkedListElemNull extends RuntimeException{
public LinkedListElemNull(String message) {
super(message); }}Copy the codeDelete the first node in the linked list whose value is key
// Delete the node whose keyword is key for the first time
public void remove(int key){
if (this.head.next == null) {
throw new LinkedListElemNull("LinkedList is null");
}
DoubleLinkedListNode cur = this.head.next;
while(cur ! =null) {
if (cur.val == key) {
cur.prev.next = cur.next;
if(cur.next ! =null) {
cur.next.prev = cur.prev;
}
return;
}
cur = cur.next;
}
System.out.println("No target node found!");
}
Copy the codeDelete all nodes in the linked list whose value is key
// Delete all nodes whose value is key
public void removeAllKey(int key){
if (this.head.next == null) {
throw new LinkedListElemNull("LinkedList is null");
}
DoubleLinkedListNode cur = this.head.next;
while(cur ! =null) {
if (cur.val == key) {
cur.prev.next = cur.next;
if(cur.next ! =null) { cur.next.prev = cur.prev; } } cur = cur.next; }}Copy the code2.3.8 Destruction of double-linked lists
As with a singly linked list, the next node is saved and the reference field of the current node is empty.
public void clear(a){
DoubleLinkedListNode cur = this.head.next;
DoubleLinkedListNode next = null;
while(cur ! =null) {
next = cur.next;
cur.next = null;
cur.prev = null;
cur = next;
}
this.head.next = null;
}
Copy the code3. The source code
3.1 the implementation class
class IndexExcept extends RuntimeException{
public IndexExcept(String message) {
super(message); }}class LinkedListElemNull extends RuntimeException{
public LinkedListElemNull(String message) {
super(message); }}class DoubleLinkedListNode {
public int val;
public DoubleLinkedListNode next;
public DoubleLinkedListNode prev;
public DoubleLinkedListNode(int val) {
this.val = val; }}public class DoubleLinkedList {
public DoubleLinkedListNode head;/ / head node
public DoubleLinkedList(a) {
this.head = new DoubleLinkedListNode(0);
}
/ / head interpolation
public void addFirst(int data){
DoubleLinkedListNode node = new DoubleLinkedListNode(data);
node.next = head.next;
if(head.next ! =null) {
head.next.prev = node;
}
head.next = node;
node.prev = head;
}
/ / stern interpolation
public void addLast(int data) {
DoubleLinkedListNode cur = this.head;
while(cur.next ! =null) {
cur = cur.next;
}
DoubleLinkedListNode node = new DoubleLinkedListNode(data);
cur.next = node;
node.prev = cur;
}
// Insert the first data node with subscript 0 at any position
public void addIndex(int index,int data) throws IndexExcept{
if (index < 0 || index > size()) {
throw new IndexExcept(index + "Illegal location!");
}
if (size() == 0) {
addFirst(data);
return;
}
if (size() == index) {
addLast(data);
return;
}
DoubleLinkedListNode node = new DoubleLinkedListNode(data);
DoubleLinkedListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
node.next = cur.next;
cur.next.prev = node;
node.prev = cur;
cur.next = node;
}
// Check whether the key is included in the single linked list
public boolean contains(int key){
if (this.head.next == null) {
return false;
}
DoubleLinkedListNode cur = head.next;
while(cur ! =null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
// Delete the node whose keyword is key for the first time
public void remove(int key){
if (this.head.next == null) {
throw new LinkedListElemNull("LinkedList is null");
}
DoubleLinkedListNode cur = this.head.next;
while(cur ! =null) {
if (cur.val == key) {
cur.prev.next = cur.next;
if(cur.next ! =null) {
cur.next.prev = cur.prev;
}
return;
}
cur = cur.next;
}
System.out.println("No target node found!");
}
// Delete all nodes whose value is key
public void removeAllKey(int key){
if (this.head.next == null) {
throw new LinkedListElemNull("LinkedList is null");
}
DoubleLinkedListNode cur = this.head.next;
while(cur ! =null) {
if (cur.val == key) {
cur.prev.next = cur.next;
if(cur.next ! =null) { cur.next.prev = cur.prev; } } cur = cur.next; }}// Get the length of the double-linked list
public int size(a){
int cnt = 0;
DoubleLinkedListNode cur = this.head.next;
while(cur ! =null) {
cnt++;
cur = cur.next;
}
return cnt;
}
public void display(a){
DoubleLinkedListNode cur = head.next;
while(cur ! =null) {
System.out.print(cur.val + "");
cur = cur.next;
}
System.out.println();
}
public void clear(a){
DoubleLinkedListNode cur = this.head.next;
DoubleLinkedListNode next = null;
while(cur ! =null) {
next = cur.next;
cur.next = null;
cur.prev = null;
cur = next;
}
this.head.next = null; }}Copy the code3.2 Test code
public class Test {
public static void main(String[] args) {
DoubleLinkedList dls = new DoubleLinkedList();
dls.addLast(1);
dls.addLast(2);
dls.addFirst(3);
dls.display();
System.out.println("= = = = = = = = = = = =");
dls.addIndex(0.4);
dls.addIndex(4.5);
dls.addIndex(2.6);
dls.display();
System.out.println(dls.contains(4));
System.out.println(dls.contains(99));
System.out.println("= = = = = = = = =");
try{
dls.addIndex(20.10);
}catch (IndexExcept e) {
e.printStackTrace();
dls.display();
}
System.out.println("= = = = = = = = = = = =");
dls.remove(5);
dls.remove(6);
dls.remove(4);
dls.display();
System.out.println("= = = = = = = = = = =");
dls.addIndex(0.7);
dls.addIndex(3.7);
dls.addIndex(3.7);
dls.addIndex(3.7);
dls.addIndex(7.7);
dls.display();
dls.removeAllKey(7);
dls.display();
System.out.println("= = = = = = = = = = = = ="); dls.clear(); dls.display(); }}Copy the code
3.3 Project Files
Approach 1: the blogger’s code cloud Gitee, the usual program code written by the blogger are in it.
Channel 2: github of the blogger, the program code written by the ordinary blogger is in it.
Route 3: Contact me!