Java realizes the addition deletion modification search reversal and reverse order of single linked list SingleLinkedList
- 2021-11-29 07:17:58
- OfStack
Node class
Node properties can be modified as needed. Pay attention to rewriting
toString()
Method for subsequent output operations.
// Node class
class Node {
public int id;
public String name;
public Node next;
public Node(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Node{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
Linked list class (main)
The functions of adding, deleting, modifying, checking, reversing and reversing are basically applicable. The realization idea is annotated in the code.
// Linked list class (management node)
class LinkedList {
// Head node
Node head = new Node(0,null);
// Number of valid data in linked list (length of linked list) (excluding head node)
public int size(){
Node temp = head;
int size = 0;
while (true){
if (temp.next == null){
break;
}
size++;
temp = temp.next;
}
return size;
}
// Show linked list
public void list(){
if (head.next == null){
System.out.println(" Linked list is empty! ");
return;
}
Node temp = head.next;
while (true){
if (temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
// Increase ( According to id From small to large )
public void add(Node newNode){
Node temp = head;
while (true){ // Used to find the end of the linked list
if (temp.next == null) {
break;
}
if (temp.id == newNode.id){
System.out.println(" Of the node to add id Already exists, adding failed! ");
return;
}
if (temp.next.id > newNode.id){
break;
}
temp = temp.next;
}
Node node = newNode;
newNode.next = temp.next;
temp.next = node;
}
// Delete ( According to id Matching deletion )
public void remove(int id){
if (head.next == null){
System.out.println(" Linked list is empty !");
return;
}
Node temp = head;
boolean flag = false; // Used to mark whether a corresponding is found id Node of
while (true){
if (temp.next == null){
break;
}
if (temp.next.id == id){ // Find the preceding of the node to delete 1 Nodes
flag =true;
break;
}
temp = temp.next;
}
if (flag){
temp.next = temp.next.next;
}else {
System.out.println(" The node to be deleted was not found, and the deletion failed !");
}
}
// Change (according to id Match the node to be modified)
public void update(int id,String name){
if (head.next == null){
System.out.println(" Linked list is empty! ");
return;
}
Node temp = head;
boolean flag = false; // Used to mark whether a corresponding is found id Node of
while (true){
if (temp.next == null){
break;
}
if (temp.id == id){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.name = name;
}else {
System.out.println(" The node to be modified was not found, and the modification failed! ");
}
}
// Check (according to id Matching)
public Node show(int id){
if (head.next == null){
System.out.println(" Linked list is empty! ");
return null;
}
Node temp = head.next;
boolean flag = false;
while (true){
if (temp == null){
break;
}
if (temp.id == id){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
return temp;
}else {
System.out.println(" The node to be found was not found, and the search failed! ");
return null;
}
}
// Find the penultimate n Nodes
public Node lastShow(int n){
Node temp = head.next;
int size = this.size();
if (size < n || n <= 0){
System.out.println(" The node you are looking for does not exist! ");
return null;
}
for (int i = 0; i < size - n; i++) {
temp = temp.next;
}
return temp;
}
// Inversion of linked list
public void reverse(){
if (head.next == null || head.next.next == null){
return;
}
Node reverseHead = new Node(0,null);
Node cur = head.next; // Record the node currently traversed to
Node next = null; // Record the following of the node currently traversed to 1 Nodes
while (true){
if (cur == null){ // Make sure to traverse to the end 1 A
break;
}
next = cur.next; // Save under 1 Nodes to avoid chain breakage
// So that the inversion header node points to the traversed current node, and the traversed current node points below the inversion header node 1 Nodes
// Ensure that the current node traversed to is always below the inverted header node 1 A
cur.next = reverseHead.next;
reverseHead.next = cur;
// Traversal
cur = next;
}
head.next = reverseHead.next; // Finally, make the original head node point below the inverted head node 1 Nodes, the original linked list can be reversed
}
// Reverse printing
// Method 1 Reverse first
// Method 2 Using stack structure
public void reversePrint(){
if (head.next == null){
System.out.println(" Linked list is empty! ");
return;
}
Stack<Node> nodes = new Stack<>();
Node temp = head.next;
while (true){
if (temp == null){
break;
}
nodes.push(temp);
temp = temp.next;
}
while (nodes.size() > 0){
System.out.println(nodes.pop());
}
}
}
Test class
import java.util.Stack;
/**
* @Author: Yeman
* @Date: 2021-10-14-12:55
* @Description:
*/
// Test class
public class SingleLinkedListTest {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
Node node1 = new Node(1, " Alan ");
Node node2 = new Node(2, " Luo Guofu ");
Node node3 = new Node(3, " Daniel F. Akerson ");
// You can not follow id Sequential addition
linkedList.add(node1);
linkedList.add(node3);
linkedList.add(node2);
linkedList.list();
System.out.println(linkedList.size()); // Length of linked list
// System.out.println(linkedList.lastShow(2)); // Reciprocal search
// linkedList.update(2," Zhang Yuning "); // Change
//
// linkedList.remove(3); // Delete
//
// System.out.println(linkedList.show(2)); // Check
// linkedList.reverse(); // Inversion of linked list
linkedList.reversePrint(); // Reverse printing
}
}
Summary
The node of single linked list consists of concrete data field and pointer field, while the head node of single linked list with head node does not store concrete data, and its pointer field points to the first effective node of linked list, that is, the first node without head node.
When adding, deleting, modifying, searching and reversing the order of a single linked list, an auxiliary variable of Node type should be defined to traverse the linked list, and the head node should be kept unchanged.
When inverting the operation, the head node needs to point to the first node of the inverted linked list, which is the only 11 places where the head node changes.