Singly linked lists
- Linked lists are stored as nodes.
- Each node contains a data field and a next field. The next field points to the next node.
- The nodes in the linked list are not necessarily stored consecutively, as shown in the figure below:
- Linked lists are divided into lists with leading nodes and lists without leading nodes, which can be determined according to actual requirements.
Code Implementation (Java)
- The code includes basic adding nodes, modifying node information, deleting nodes, and finding nodes. There are other features as well.
Node class:
class Node {
public int no;
public String name;
public String nickName;
public Node next;
public Node(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName; }}Copy the codeList:
class SignalLinkedList {
private Node head = new Node(0.""."");
// Insert a node by tail
public void addNode(Node node) {
Node temp = head;
while(temp.next ! =null) {
temp = temp.next;
}
temp.next = node;
node.next = null;
}
// Insert in no order
public void addOrderNode(Node node) {
Node temp = head;
// Walk through the list to find the nodes that match the criteria
while(temp.next ! =null) {
if (temp.next.no > node.no) {
node.next = temp.next;
temp.next = node;
return;
} else{ temp = temp.next; }}// In this case, the linked list may be empty, or all the nodes in the list do not meet the conditions, and new nodes can be added directly.
if (temp.next == null) {
temp.next = node;
node.next = null; }}// Change the value of the node. Use "no" to judge. "No" cannot be changed
public void changeNode(int no, String name, String nickName) {
Node temp = head;
Boolean flag = false;
if (temp.next == null) {
System.out.println("Linked list is empty and cannot be modified!");
}
while(temp.next ! =null) {
if (temp.next.no == no) {
temp.next.name = name;
temp.next.nickName = nickName;
flag = true;
}
temp = temp.next;
}
if (flag == false) {
System.out.println("This node is not in the list!"); }}// Delete the corresponding node according to no
public void del(int no) {
Node temp = head;
Boolean flag = false;
if (temp.next == null) {
System.out.println("Linked list is empty and cannot be deleted!");
}
while(temp.next ! =null) {
if (temp.next.no == no) {
temp.next = temp.next.next;
flag = true;
}
temp = temp.next;
}
if (flag == false) {
System.out.println("This node is not in the list!"); }}// Iterate over the node information in the output list
public void showLinkedList(a) {
Node temp = head;
if (temp.next == null) {
System.out.println("Linked list is empty!!");
}
while(temp.next ! =null) {
System.out.printf("no = %d name = %s nickName = %s; \n", temp.next.no, temp.next.name, temp.next.nickName); temp = temp.next; }}// Find the number of valid nodes in a single list
public int nodeNum(a) {
Node temp = head;
int length = 0;
while(temp.next ! =null) {
length++;
temp = temp.next;
}
return length;
}
// Find the KTH last node in a single list
public Node reciprocalKNode(int k) {
Node fast = head;
Node slow = head;
int length = 0;
// for (int i = 0; i < k-1; i++) {
// fast = fast.next;
/ /}
// Define two secondary nodes, so that one node is k-1 ahead of the other node, and then loop both nodes until the fast node reaches the end of the list, at which point the slow node is the KTH from last
while(fast.next ! =null) {
if(length ! = k-1) {
fast = fast.next;
length++;
continue;
}
fast = fast.next;
slow = slow.next;
}
return slow;
}
// Reverse the single-linked list
public void reverseLinkedList(SignalLinkedList List) {
Node reverseHead = new Node(0.""."");
Node listTemp = List.head.next;
Node next = null;
while(listTemp ! =null) { next = listTemp.next; listTemp.next = reverseHead.next; reverseHead.next = listTemp; listTemp = next; } List.head.next = reverseHead.next; }}Copy the codeIn main:
package com.linkedlist;
public class LinkedList {
public static void main(String[] args) {
// Add nodes in random order
Node node1 = new Node(1."Zhang"."The first");
Node node2 = new Node(2."Bill"."A second");
Node node3 = new Node(3."Fifty"."The third");
SignalLinkedList List = new SignalLinkedList();
List.addNode(node1);
List.addNode(node2);
List.addNode(node3);
System.out.println("Linked list of nodes inserted by tail method:");
List.showLinkedList();
// Insert nodes according to the size of no
Node orderNode1 = new Node(6."Water margin"."6");
Node orderNode2 = new Node(5.Journey to the West."V");
Node orderNode3 = new Node(4."Three kingdoms"."4");
List.addOrderNode(orderNode1);
List.addOrderNode(orderNode2);
List.addOrderNode(orderNode3);
System.out.println("Linked list after inserting nodes in no order:");
List.showLinkedList();
// Modify the no value of the node and the modified content
List.changeNode(9.A Dream of Red Mansions."7");
// View the modified list
System.out.println("The modified linked list is:");
List.showLinkedList();
// Delete a node
List.del(5);
// View the deleted list
System.out.println("The deleted linked list is:");
List.showLinkedList();
// The number of valid nodes in the list
System.out.println("Number of valid nodes in a linked list :");
System.out.println(List.nodeNum());
// Find the KTH last node in a single list
Node kNode = List.reciprocalKNode(1);
System.out.println("The information for the penultimate KTH node in a singly linked list is:");
System.out.printf("no = %d name = %s nickName = %s\n", kNode.no, kNode.name, kNode.nickName);
// Reverse the single-linked list
System.out.println("The reversed single-linked list is:"); List.reverseLinkedList(List); List.showLinkedList(); }}Copy the code