Data structure and algorithm -- Java implementation (linked list)
1, Single linked list
I wonder if you still remember how you came over when you first came into contact with the data structure. At that time, learning the data structure was implemented in c language. At that time, it would be full of all kinds of questions? What does this * mean, what does that & mean? Why is there something in the structure that is the same as the structure name? Is it very similar to you when you were a beginner in data structure?
1.1 definition of linked list
The linked list is actually a binary. Each node of the linked list stores data and the address of the next node respectively, so that we can abstract the basic attributes in the linked list
- Define Node as Node
- There is data in each node
- And reference to the next address (pointer, there is no concept of pointer in java)
// Define a single linked list
public class Node {
private int data; // The data I store here by default are integers
private Node next; // A reference to the next address
// Write construction method
public Node(int data) {
this.data = data;
}
// Method to get the next node
public Node next() {
return this.next;
}
// Get data in node
public int getData() {
return this.data;
}
}1.2 add a new node to the linked list
Implementation idea: If I want to insert a node into the linked list, but I only know the head node, so I need to find the node one by one until the next node is empty, and then point the address of the node to a node we want to insert to complete the insertion operation. Don't you understand? It doesn't matter. Look at the moving picture below
Here's how to implement it:
The core of this step is to find the last node
// Add nodes to nodes (solve increasing problems)
public Node append(Node node) {
// Get current node
Node currentNode = this;
// Loop backward to find the last node whose next node is empty
while (true) {
// Take out the next node
Node nextNode = currentNode.next;
// If the next node is Null, the current node is already the last node
if (nextNode == null) {
break;
}
// Assign to current node
currentNode = nextNode;
}
// Append the node to be appended to the currently found node
currentNode.next = node;
return this;
}1.3 judge whether the current node is the last node (isLast)
Just judge whether the reference of the current node is empty
// Is the current node the last node
public boolean islast() {
return this.next == null;
}1.4 delete the next node (removeNext)
We want to delete a node
- You need to make the node he points to null
- Point the pointer to the node to the next node Let's watch animation
// This is very simple. Just change the reference
// Delete next node
public void removeNext() {
// Take out the next node
Node newNext = next.next;
// Set the next node as the next node of the current node
this.next = newNext;
}1.5 display node information (show)
Use the cycle to print out the corresponding value of each node in the linked list
// Displays information for all nodes
public void show() {
Node currentNode = this;
while (true) {
System.out.print(currentNode.data+" ");
// Take out the next node
currentNode = currentNode.next;
// If it is the last node
if (currentNode == null) {
System.out.println();// Line feed processing
break;
}
}
}1.6 insert a node (after)
Insert a node into the position of the current node to make it the next node of the current node
// Insert a node as the next node of the current node, which can be compared to exchanging the values of two numbers
public void after(Node node) {
// Take out the next node as the next node
Node nextNext = next;
// Insert the new node as the next node of the current node
this.next = node;
// Take the next node as the next node of the new node
node.next = nextNext;
}1.7 write test class (TestNode)
import Array.util.Node;
public class TestNode {
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
// Append node
n1.append(n2).append(n3).append(new Node(4));
// Show all node contents
n1.show();
// Remove next node
// n1.next().removeNext(); // Delete 3
// n1.show();
// Insert a new node
Node node = new Node(5);
n1.next().after(node);
n1.show();
System.out.println(n1.next().getData());
System.out.println(n2.next().getData());
System.out.println(n3.getData());
System.out.println(n3.islast());
}
}
2, Circular single linked list
Circular linked list is to connect the tail and head of the linked list
2.1 definition of circular single linked list
public class LoopNode {
// Node content
private int data;
// Next node
private LoopNode next = this;
public LoopNode(int data) {
this.data = data;
}
}2.2 get the next node and data
// Method to get the next node
public LoopNode next() {
return this.next;
}
// Get data in node
public int getData() {
return this.data;
}2.3 inserting nodes
// Inserts a node as the next node of the current node
public void after(LoopNode node) {
// Take out the next node as the next node
LoopNode nextNext = next;
// Insert the new node as the next node of the current node
this.next = node;
// Take the next node as the next node of the new node
node.next = nextNext;
}2.4 deleting nodes
// Delete next node
public void removeNext() {
// Take out the next node
LoopNode newNext = next.next;
// Set the next node as the next node of the current node
this.next = newNext;
}2.5 loop through each node
// Displays information for all nodes
public void show() {
LoopNode currentNode = this;
while (true) {
System.out.print(currentNode.data+" ");
// Take out the next node
currentNode = currentNode.next;
// If it is the last node
if (currentNode == null) {
System.out.println();
break;
}
}
}3, Circular double linked list
Circular double linked list refers to the connection between the head and the tail, and has references to the front node and the back node at the same time
3.1 definition of bidirectional circular linked list
// Bidirectional linked list implementation
public class DoubleLoop {
// Previous node
private DoubleLoop pre;
// Next node
private DoubleLoop next = this;
// Node data
private int data;
public DoubleLoop(int data) {
this.data = data;
}
public int getData() {
return data;
}
}3.2 get the upper (lower) node
// Next node
public DoubleLoop next() {
return this.next;
}
// Previous node
public DoubleLoop pre() {
return this.pre;
}3.3 adding nodes
// Add node
public void after(DoubleLoop node) {
// Original next node
DoubleLoop nextNext = next;
// The new node is the next node of the current node
this.next = node;
// The current node is the previous node of the new node
node.pre = this;
// The original next node is the next node of the new node
node.next = nextNext;
// Make the previous node of the original next node the current new node
nextNext.pre = node;
}