当前位置：网站首页>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 ,
边栏推荐
- Vscode下中文乱码问题
- It's great to save 10000 pictures of girls
- Carsim-问题Failed to start Solver: PATH_ID_OBJ(X) was set to Y； no corresponding value of XXXXX?
- 常量指针和指针常量
- Global and Chinese markets of tilting feeders 2022-2028: Research Report on technology, participants, trends, market size and share
- CarSim problem failed to start solver: path_ ID_ OBJ(X) was set to Y； no corresponding value of XXXXX?
- 实现双向链表(带傀儡节点)
- Animation synchronization of CarSim real-time simulation
- 力扣每日一题刷题总结：二叉树篇（持续更新）
- Carsim-路面3D形状文件参数介绍
猜你喜欢
乐理基础(简述）
Dynamic extensible representation for category incremental learning -- der
How to build the alliance chain? How much is the development of the alliance chain
Static library and dynamic library
On the confrontation samples and their generation methods in deep learning
On November 24, we celebrate the "full moon"
C语言实现XML生成解析库(XML扩展)
Data reverse attack under federated learning -- gradinversion
Carsim problem failed to start Solver: Path Id Obj (X) was set to y; Aucune valeur de correction de xxxxx?
MySQL optimization
随机推荐
Meta learning Brief
Wang extracurricular words
16: 00 interview, came out at 16:08, the question is really too
How to wrap qstring strings
Global and Chinese market of medicine cabinet 2022-2028: Research Report on technology, participants, trends, market size and share
SQLyog远程连接centos7系统下的MySQL数据库
Animation synchronization of CarSim real-time simulation
使用Matplotlib绘制图表初步
OpenCV3 6.2 低通滤波器的使用
Short video with goods source code, double-click to zoom in when watching the video
Chinese garbled code under vscade
Business architecture diagram
Cvpr19 deep stacked hierarchical multi patch network for image deblurring paper reproduction
Li Kou daily one question brushing summary: binary tree chapter (continuous update)
Force deduction method summary: find classes
St-link connection error invalid ROM table of STM32 difficult and miscellaneous diseases
SQL operation database syntax
Command line is too long
稀疏矩阵存储
Force deduction method summary: double pointer