当前位置：网站首页>Implementation of bidirectional linked list (simple difference, connection and implementation between bidirectional linked list and unidirectional linked list)
Implementation of bidirectional linked list (simple difference, connection and implementation between bidirectional linked list and unidirectional linked list)
2022-07-02 08:22:00 【Ischanged】
Preface
I wrote some articles before to briefly introduce the sequence table , Basic knowledge of linked list , It also summarizes several written test questions of the linked list , Continue to work today , I'd like to briefly introduce the headless bidirectional circular linked list and its code implementation to the old ironworkers .
Why introduce headless two-way circular linked list ？？？？？
We can simply think like this , A one-way linked list can only access other nodes from the head node in one direction , You can't access other nodes without retreating , You can't cycle through , Different from one-way linked list , The bidirectional linked list does not need to look for the precursor node when inserting and deleting , Because it can return to the previous node ,** When looking for , We can use the idea of two distribution , From the head node （head) Look backward for operations and last（ Caudal node ） Forward search operations are synchronized , In this way, the search of double linked list can be doubled ,** When implementing the addition, deletion, modification and query of the bidirectional linked list, their operations are also different , We can compare it before and after , We can better understand them .
Advantages, disadvantages and usage scenarios of one-way linked list and two-way linked list
One way linked list ： There is only one pointer to the next node . advantage ： Adding and deleting nodes in one-way linked list is simple . There is no dead loop when traversing ;
shortcoming ： Can only traverse from beginning to end . Only successors can be found , Can't find the precursor , That is, we can only move forward . It is applicable to the addition and deletion of nodes .Double linked list ： There are two pointers , One points to the previous node , One points to the next node . advantage ： You can find precursors and successors , Go in and go out ;
shortcoming ： Add and delete node complexity , Need to allocate one more pointer storage space . It is applicable to the case where the node value needs to be searched in two directions
Here are some things to pay attention to ：
1、 The precursor domain is introduced , It solves the pain point that the single linked list can only be accessed one way .
2、 For a two-way linked list , it is to be noted that : The precursor of the first node is null And the last node, followed by null
3、 The introduction of a last, Flag tail node .
Simple implementation and graphic analysis of bidirectional linked list
The simple model of the two-way linked list is shown in the figure ：
Declare two classes, one ListNode, Node is a class whose member attributes include the value of the node data,prev Precursor domain ,next Successor domain , One MyLinkedList The member properties of the linked list class , Including header nodes head, Tail node last,curNext Nodes etc. .
The code is as follows ：
// Node class
class ListNode {
public int data;
public ListNode prev;
public ListNode next;
public ListNode(int data) {
this.data = data;
}
}
// Linked list this class
public class MyLinkedList {
public ListNode head;// Head node
public ListNode last;// Caudal node
ListNode curNext;// Record the next node
}
The first interpolation
The basic idea
** The newly inserted node is the head node ,** If this is the first insertion , There was no node before , The newly inserted node is the head node , If there is a node before the head plug , makes node Of next Point to the head node ,head Of prev Point to node , Then the new head node becomes the newly inserted node .
As shown in the figure ：
Code implementation ：
// The first interpolation
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
this.head = node;
this.last = node;// Write but not write
} else {
node.next = head;
this.head.prev = node;
this.head = node;
}
}
The tail interpolation ：
The inserted node is the tail node , If it is the first insertion , The inserted node is both head and tail , If not the first insert , Make the last node next Point to node,node Of prev Point to last The node can be .
Pictured ：
// The tail interpolation
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
this.head = node;
this.last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}
Insert at any position , The first data node is 0 Subscript no. ：
First, judge the legitimacy of the insertion position if , Insertion position index Is negative or greater than the length of the linked list , Then the entered position is illegal , If the insertion position is equal to the length of the linked list , Is tail interpolation , The insertion position is 0 Location , Then it is head insertion , The middle position is inserted normally . When inserting, we also use a function to find a certain position findIndex, By traversing , Find where to insert , Return to the insert function . When inserting, the inserted nodes should be connected with the front and back nodes , The order of connection is no matter , But be sure to connect to .
Graphic analysis ：
Code implementation ：
// Insert at any position , The first data node is 0 Subscript no.
public void addIndex(int index, int data) {
// Judge the legitimacy of the location , Insert at any position , The first data node is 0 Subscript no.
if (index < 0 || index > size()) {
System.out.println(" The position entered is illegal ");
return;
} else {
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
} else {
ListNode node = new ListNode(data);
ListNode cur;
cur = findIndex(index);
cur.prev.next = node;// When index==size when , If tail interpolation is not used , A null pointer exception will occur
node.prev = cur.prev;
cur.prev = node;
node.next = cur;
}
}
}
// Find the node at a certain location
// Start from the beginning , Need to go to 0 The position goes 0 Step , Need to go to n The position goes n Step
public ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
Delete the first keyword as key The node of
The general idea is , Traverse the linked list to find the node to be deleted , If the deletion is found, the deletion is over , Can't find the list that has been traversed , The found node is also divided into head node or tail node, intermediate node , Finding the head node also depends on whether there is only one node or multiple nodes , There is no need to divide the tail node , The intermediate node can be deleted normally .
Let's combine the code and illustration to understand ：
// Delete the first keyword as key The node of
public void remove(int key) {
ListNode cur = this.head;
while (cur != null) {
//
if (cur.data == key) {
// Determine whether it is a header node
if (cur == this.head) {
this.head =this.head.next;
// The head node is the only node
if (this.head == null) {
this.last = null;
} else {
// The head node is not the only node
this.head.prev = null;
}
} else {
cur.prev.next = cur.next;
// Determine whether it is the last node
if (cur.next == null) {
this.last = cur.prev;
} else {
cur.next.prev = cur.prev;
}
}
return;
} else {
cur = cur.next;
}
}
}
Delete all values as key The node of
This idea and the above delete the first occurrence key The value is almost the same , Just delete all that appear key value , We just need to judge whether it is key value if Add... After the statement cur=cur.next, In this way, if you find the element to be deleted, continue to look back and delete , If you don't find it, keep looking backwards , Until you finish traversing the linked list .
// Delete all values as key The node of
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
//
if (cur.data == key) {
// Determine whether it is a header node
if (cur == this.head) {
this.head = this.head.next;
// The head node is the only node
if (cur.next == null) {
this.last = null;
} else {
// The head node is not the only node
this.head.prev = null;
}
} else {
cur.prev.next = cur.next;
// Determine whether it is the last node
if (cur.next == null) {
this.last = cur.prev;
} else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next; Keep going back Don't stop Until null When
}
}
Get the length of the single linked list ：
This is very simple , Traverse the linked list node is not empty , Counter count Add one , After traversing all the time .
// Get the length of the single linked list
public int size() {
ListNode cur =this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
Print linked list
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
Look for keywords key Is it in a single linked list
// Look for keywords key Is it in a single linked list
public boolean contains(int key) {
/
if(this.head==null) return false;
ListNode cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur=cur.next;
}
//return false;
return false;
}
Empty the list
Emptying the linked list cannot simply put head Set as null,last Set as null, To traverse the linked list, set the predecessor and successor of each node to null, But pay attention to setting the value of the node to null Record the location of the next node in advance .
public void clear() {
ListNode cur = this.head;
while (cur != null) {
curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;// Record the location of the next node in advance
}
this.head = null;
this.last = null;
}
Complete code ：
MyLinkedList.java
class ListNode {
public int data;
public ListNode prev;
public ListNode next;
public ListNode(int data) {
this.data = data;
}
}
public class MyLinkedList {
public ListNode head;// Head node
public ListNode last;// Caudal node
ListNode curNext;// Record the next node
// Find the node at a certain location
public ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
// The first interpolation
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
this.head = node;
this.last = node;// Write but not write
} else {
node.next = head;
this.head.prev = node;
this.head = node;
}
}
// The tail interpolation
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
this.head = node;
this.last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}
// Insert at any position , The first data node is 0 Subscript no.
public void addIndex(int index, int data) {
// Judge the legitimacy of the location , Insert at any position , The first data node is 0 Subscript no.
if (index < 0 || index > size()) {
System.out.println(" The position entered is illegal ");
return;
} else {
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
} else {
ListNode node = new ListNode(data);
ListNode cur;
cur = findIndex(index);
cur.prev.next = node;// When index==size when , If tail interpolation is not used , A null pointer exception will occur
node.prev = cur.prev;
cur.prev = node;
node.next = cur;
}
}
}
// Look for keywords key Is it in a single linked list
public boolean contains(int key) {
// Correct the mistake
if(this.head==null) return false;
ListNode cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur=cur.next;
}
//return false;
return false;
}
// Delete the first keyword as key The node of
public void remove(int key) {
ListNode cur = this.head;
while (cur != null) {
//
if (cur.data == key) {
// Determine whether it is a header node
if (cur == this.head) {
this.head =this.head.next;
// The head node is the only node
if (cur.next == null) {
this.last = null;
} else {
// The head node is not the only node
this.head.prev = null;
}
} else {
cur.prev.next = cur.next;
// Determine whether it is the last node
if (cur.next == null) {
this.last = cur.prev;
} else {
cur.next.prev = cur.prev;
}
}
return;
} else {
cur = cur.next;
}
}
}
// Delete all values as key The node of
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
//
if (cur.data == key) {
// Determine whether it is a header node
if (cur == this.head) {
this.head = this.head.next;
// The head node is the only node
if (cur.next == null) {
this.last = null;
} else {
// The head node is not the only node
this.head.prev = null;
}
} else {
cur.prev.next = cur.next;
// Determine whether it is the last node
if (cur.next == null) {
this.last = cur.prev;
} else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next; Keep going back Don't stop Until null When
}
}
// Get the length of the single linked list
public int size() {
ListNode cur =this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
public void clear() {
ListNode cur = this.head;
while (cur != null) {
curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = null;
this.last = null;
}
}
TestDemo.java
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList =new MyLinkedList();
myLinkedList.addFirst(1);
myLinkedList.addFirst(2);
myLinkedList.addFirst(3);
myLinkedList.addFirst(4);
myLinkedList.display();
System.out.println(myLinkedList.contains(0));
myLinkedList.remove(4);
myLinkedList.display();
}
}
️ Too small 🧑*🧑* If 9️⃣ Remember to hold in words ,
边栏推荐
- It's great to save 10000 pictures of girls
- Global and Chinese market of recovery equipment 2022-2028: Research Report on technology, participants, trends, market size and share
- 2022 Heilongjiang latest construction eight members (materialman) simulated examination questions and answers
- 【无标题】
- Introduction to parameters of CarSim pavement 3D shape file
- 力扣每日一题刷题总结：二叉树篇（持续更新）
- Matlab数学建模工具
- E-R画图明确内容
- 2022 Heilongjiang's latest eight member (Safety Officer) simulated test question bank and answers
- Vs code configuration problem
猜你喜欢
应对长尾分布的目标检测 -- Balanced Group Softmax
Carsim-问题Failed to start Solver: PATH_ID_OBJ(X) was set to Y； no corresponding value of XXXXX?
Carsim-問題Failed to start Solver: PATH_ID_OBJ(X) was set to Y； no corresponding value of XXXXX?
CarSim problem failed to start solver: path_ ID_ OBJ(X) was set to Y； no corresponding value of XXXXX?
Data reverse attack under federated learning -- gradinversion
The internal network of the server can be accessed, but the external network cannot be accessed
链表经典面试题（反转链表，中间节点，倒数第k个节点，合并分割链表，删除重复节点）
Fundamentals of music theory (brief introduction)
【无标题】
Command line is too long
随机推荐
程序猿学英语-Learning C
Command line is too long
Global and Chinese markets for conventional rubber track 2022-2028: Research Report on technology, participants, trends, market size and share
OpenCV关于x,y坐标容易混淆的心得
Sqlyog remote connection to MySQL database under centos7 system
C语言实现XML生成解析库(XML扩展)
It's great to save 10000 pictures of girls
OpenCV常用方法出处链接（持续更新）
2022 Heilongjiang latest construction eight members (materialman) simulated examination questions and answers
Cvpr19 deep stacked hierarchical multi patch network for image deblurring paper reproduction
Principes fondamentaux de la théorie musicale (brève introduction)
Development of digital collection trading website development of metauniverse digital collection
Matlab - autres
Summary of one question per day: linked list (continuously updated)
When a custom exception encounters reflection
Valin cable: BI application promotes enterprise digital transformation
W10 is upgraded to W11 system, but the screen is black, but the mouse and desktop shortcuts can be used. How to solve it
Organigramme des activités
Jz-061-serialized binary tree
Comparable，Comparator，Clonable 接口使用剖析