This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging
This article introduces singly linked lists in data structures.
An introduction to Linked List
Linked lists can be divided into three categories:
- Singly linked lists
- Two-way linked list
- Circulation list
The application of three linked lists is analyzed in detail below.
Singly linked lists
A linked list is an ordered list that is stored in memory as follows:
- Linked lists are stored as nodes
- Each node contains the Data domain (which stores data), and the Next domain (which points to the next node).
- The nodes of a linked list are not necessarily contiguously stored
After understanding the concept and characteristics of the single list, we will feel the charm of the single list through a case. Requirements: Use a unidirectional linked list with head node to achieve — water Frontier hero list management, complete the operation of adding, deleting, modifying and checking heroes.
- Create a head node that does not store data and represents the head of a single linked list
- Each additional node is added directly to the end of the list
After the analysis, we use the code to implement:
// Define SingleLinkedList management hero
class SingleLinkedList {
// Initialize a header node without storing specific data
private HeroNode head = new HeroNode(0.""."");
// Add a node to the unidirectional linked list
public void add(HeroNode heroNode) {
// When the order of numbers is not considered:
// 1, find the last node in the current list
// 2. Point the next domain of the last node to the new node
// Because the head node cannot move, we need a secondary node temp
HeroNode temp = head;
// Traverse the list to find the tail node
while (true) {
// Find the last node of the list
if (temp.next == null) {
break;
}
// If it is not the tail node, move temp back
temp = temp.next;
}
// Temp refers to the tail node after the loop ends
temp.next = heroNode;// Point the next domain to the new node
}
// Display the list
public void list(a) {
// Check whether the list is empty
if (head.next == null) {
System.out.println("The list is empty.");
return;
}
// Create a secondary node
HeroNode temp = head.next;
while (true) {
// Check whether the end of the list is reached
if (temp == null) {
break;
}
// Output node information
System.out.println(temp);
// Move temp backtemp = temp.next; }}}// Define HeroNode. Each HeroNode object is a node
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;// Point to the next node
/ / the constructor
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString(a) {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }}Copy the codeNow that the list is written, let’s write the test code:
public static void main(String[] args) {
// Create a node
HeroNode hero1 = new HeroNode(1."Sung river"."Just in time.");
HeroNode hero2 = new HeroNode(2."Lu Junyi"."Jade unicorn");
HeroNode hero3 = new HeroNode(3."吴用"."The mastermind");
HeroNode hero4 = new HeroNode(4."Lin"."The head of the leopard.");
// Create a linked list
SingleLinkedList singleLinkedList = new SingleLinkedList();
// Add to the list
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
// Display the list
singleLinkedList.list();
}
Copy the codeRunning result:
HeroNode [no = 1, name = sung river, nickname = timely rain] HeroNode [no = 2, name = jun-yi lu, nickname = jade kirin] HeroNode [no = 3, name = with wu. Nickname = nickname [no=4, name= nickname= nickname]Copy the codeNow this program can create lists, but it doesn’t guarantee that the elements are sorted by number, it just creates them in the order they were added. How to make heroes always rank when they are added to the list? Let’s break it down:
- The first step is to find the location of the newly added node, via a secondary node
- Make next of the new node equal to Next of the secondary node, because the secondary node has already found the place to add, so assign next of the secondary node to next of the new node
- Assign the value of the new node to the next of the secondary node
Here is the code implementation:
// Define SingleLinkedList management hero
class SingleLinkedList {
// Initialize a header node without storing specific data
private HeroNode head = new HeroNode(0.""."");
// The second way to add is to add according to the rank
public void addByOrder(HeroNode heroNode) {
// Create a secondary node to help find where to add
// Since the list is singly linked, the secondary node should be the node before the added node
HeroNode temp = head;
boolean flag = false;// Indicates whether the hero number exists
while (true) {
if (temp.next == null) {
// Temp is at the end of the list
break;
}
if (temp.next.no > heroNode.no) {
// The location is found, just after temp
break;
} else if (temp.next.no == heroNode.no) {
// The id already exists
flag = true;
break;
}
temp = temp.next;// Move temp back
}
// At the end of the loop, determine the flag
if (flag) {
// The number exists and cannot be added
System.out.println("Hero number ready to insert" + heroNode.no + "Repeat, do not join.");
} else {
// Insert into the listheroNode.next = temp.next; temp.next = heroNode; }}// Display the list
public void list(a) {
// Check whether the list is empty
if (head.next == null) {
System.out.println("The list is empty.");
return;
}
// Create a secondary node
HeroNode temp = head.next;
while (true) {
// Check whether the end of the list is reached
if (temp == null) {
break;
}
// Output node information
System.out.println(temp);
// Move temp backtemp = temp.next; }}}Copy the codeWrite test code:
public static void main(String[] args) {
// Create a node
HeroNode hero1 = new HeroNode(1."Sung river"."Just in time.");
HeroNode hero2 = new HeroNode(2."Lu Junyi"."Jade unicorn");
HeroNode hero3 = new HeroNode(3."吴用"."The mastermind");
HeroNode hero4 = new HeroNode(4."Lin"."The head of the leopard.");
// Create a linked list
SingleLinkedList singleLinkedList = new SingleLinkedList();
// Add to the list
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
// Display the list
singleLinkedList.list();
}
Copy the codeOperation effect:
HeroNode [no = 1, name = sung river, nickname = timely rain] HeroNode [no = 2, name = jun-yi lu, nickname = jade kirin] HeroNode [no = 3, name = with wu. Nickname = nickname [no=4, name= nickname= nickname]Copy the codeEven if the order is not correct, the list is still sorted after insertion. This is done at insertion time.
Modification of a single linked list node
Through the above analysis and practice, we already know how to create a singly linked list, so how to modify the nodes of the singly linked list?
// Modify the node information based on the no number
public void update(HeroNode newHeroNode) {
// Change the value based on the number of newHeroNode
// Check whether the list is empty
if (head == null) {
System.out.println("The list is empty.");
return;
}
// Find the node to modify
// Define secondary nodes
HeroNode temp = head.next;
boolean flag = false;// Indicates whether the node is found
while (true) {
if (temp == null) {
break;// The list traversal is complete
}
if (temp.no == newHeroNode.no) {
// Find the node to modify
flag = true;
break;
}
temp = temp.next;// Move temp back
}
// Check whether the node to be modified has been found according to the flag
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
// No node found
System.out.println("Not found."); }}Copy the codeThe implementation of the modifications is relatively simple. Here’s a test:
public static void main(String[] args) {
// Create a node
HeroNode hero1 = new HeroNode(1."Sung river"."Just in time.");
HeroNode hero2 = new HeroNode(2."Lu Junyi"."Jade unicorn");
HeroNode hero3 = new HeroNode(3."吴用"."The mastermind");
HeroNode hero4 = new HeroNode(4."Lin"."The head of the leopard.");
// Create a linked list
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
// Modify the node
HeroNode newHeroNode = new HeroNode(2."小卢"."~ Jade unicorn ~");
singleLinkedList.update(newHeroNode);
// Display the list
singleLinkedList.list();
}
Copy the codeRunning result:
HeroNode [no=3, name= 1, nickname= 1] Nickname = nickname [no=4, name= nickname= nickname]Copy the codeThe hero number 2 is changed.
Deletion of a single linked list node
And then the last operation, delete. First of all:
- Find the previous node that you want to delete and pass through a secondary node temp
- Temp.next = temp.next. Next = temp.next. Next = temp.next. Next = temp.next. Next = temp.Next. Next = temp.Next. Next = temp.Next
- The deleted node will have no other reference and will be collected by the garbage collector
Here’s the code implementation:
// Delete the node
public void delete(int no) {
// Define secondary nodes
HeroNode temp = head;
boolean flag = false;// Check whether the previous node to be deleted is found
while (true) {
if (temp.next == null) {
// The traversal is complete
break;
}
if (temp.next.no == no) {
/ / find
flag = true;
break;
}
temp = temp.next;// Move temp back
}
/ / determine flag
if (flag) {
/ / find
// It can be deleted
temp.next = temp.next.next;
} else {
/ / was not found
System.out.println("The node to be deleted does not exist"); }}Copy the codeTest code:
public static void main(String[] args) {
// Create a node
HeroNode hero1 = new HeroNode(1."Sung river"."Just in time.");
HeroNode hero2 = new HeroNode(2."Lu Junyi"."Jade unicorn");
HeroNode hero3 = new HeroNode(3."吴用"."The mastermind");
HeroNode hero4 = new HeroNode(4."Lin"."The head of the leopard.");
// Create a linked list
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
// Delete the node
singleLinkedList.delete(1);
// Display the list
singleLinkedList.list();
}
Copy the codeRunning result:
Nickname = nickname [no=4, name= 1, nickname= 1, nickname= 1, nickname= 1]Copy the codeSong Jiang was successfully deleted.
Here, on the single linked list to add, delete and check the operation on the end of all the explanation. Analysis of singly linked list operations is critical, and if you can’t analyze and understand the process, it will be difficult to write code to do it.