1. Preface
Recently, when reviewing data structures and algorithms, some algorithm problems use the idea of stacks, and when it comes to stacks, we have to talk about linked lists. Arrays and linked lists are the basis of linear storage structures, and stacks and queues are applications of linear storage structures~
This article mainly explains the basic knowledge points of single-linked lists, and makes a simple introduction. If there is any mistake, please correct it.
2. Review and Knowledge
Speaking of linked lists, let’s first mention the array. Comparing them with arrays makes you very understanding the storage structure of linked lists very well.
2.1 Review the array
We have learned arrays in both C and Java:
Advantages of arrays:
Disadvantages of arrays:
2.2 Link List Description
After reading the array, go back to our linked list:
The n nodes are discretely allocated and connected to each other through pointers. Each node has only one predecessor node, each node has only one subsequent node, the first node has no predecessor node, and the tail node has no subsequent node.
Advantages of linked list:
Disadvantages of linked lists:
I'll explain the terms related to the linked list through the above picture:
To determine a linked list, we only need a head pointer, and the entire linked list can be deduced through the head pointer~
There are several categories of linked lists:
1. One-way link table
2. Bidirectional link table
3. Recycling link list
What you need to remember when operating a linked list is:
The pointer field in the node points to a node!
3. Java implementation link list
algorithm:
First, we define a class as a node
For the convenience of operation, I directly defined it as public.
public class Node { //Data domain public int data; //Pointer domain, pointing to the next node public Node next; public Node() { } public Node(int data) { this.data = data; } public Node(int data, Node next) { this.data = data; this.next = next; }} 3.1 Create a linked list (add nodes)
Insert data into the linked list:
/** * Add data to the linked list* * @param value Data to be added*/ public static void addData(int value) { //Initialize the node to be added newNode = new Node(value); // Temporary node Node temp = head; // Find the tail node while (temp.next != null) { temp = temp.next; } // The case where the head node.next is null has been included~ temp.next = newNode; } 3.2 Traversing the linked list
We have written the addition method above, and now we will go through it to see if it is correct~~~
Start from the first node and keep searching behind until there is no data on the subsequent node:
/** * Traversing the linked list* * @param head head head node*/ public static void traverse(Node head) { // Temporary node, start from the first node Node temp = head.next; while (temp != null) { System.out.println("Follow the official account Java3y:" + temp.data); //Continue with the next temp = temp.next; } }result:
3.3 Insert node
/** * Insert node* * @param head head pointer* @param index position to be inserted* @param value value to be inserted*/ public static void insertNode(Node head, int index, int value) { //First of all, you need to determine whether the specified position is legal, if (index < 1 || index > linkListLength(head) + 1) { System.out.println("Insert position is illegal."); return; } //Temporary node, start from the beginning node Node temp = head; //Click the current position of the traversal int currentPos = 0; //Initialize the node to be inserted Node insertNode = new Node(value); while (temp.next != null) { //The location of the previous node was found if ((index - 1) == currentPos) { //temp represents the previous node//Point the original pointer from the previous node to the inserted node to insertNode.next = temp.next; //Point the pointer field of the previous node to the node to be inserted temp.next = insertNode; return; } currentPos++; temp = temp.next; } } 3.4 Get the length of the linked list
It is very simple to get the length of the linked list. It can be done by traversing it and get +1 for each node~
/** * Get the length of the linked list* @param head head pointer*/ public static int linkListLength(Node head) { int length = 0; // Temporary node, start from the first node Node temp = head.next; // Find the tail node while (temp != null) { length++; temp = temp.next; } return length; } 3.5 Delete nodes
Deleting a node in a certain location is actually very similar to the insertion node, and you also need to find the previous node. Change the pointer field of the previous node and you can delete it~
/** * Delete nodes according to location * * @param head head pointer * @param index The location to be deleted */ public static void deleteNode(Node head, int index) { //First of all, you need to determine whether the specified location is legal, if (index < 1 || index > linkListLength(head) + 1) { System.out.println("Delete location is illegal."); return; } //Temporary node, start from the beginning node Node temp = head; //The current location of the record traversal is int currentPos = 0; while (temp.next != null) { //The location of the previous node is found if ((index - 1) == currentPos) { //temp represents the previous node//temp.next represents the node you want to delete//Storage the node you want to delete Node deleteNode = temp.next; //The next node that you want to delete the node is handed over to the previous node to control temp.next = deleteNode.next; //Java will recycle it, and it should not make much sense to set it to null (I personally think, if it is not correct, please point it out~) deleteNode = null; return; } currentPos++; temp = temp.next; } } 3.6 Sort the linked list
I have already talked about 8 sorting algorithms [Summary of Eight sorting algorithms]. I will choose a simple bubble sorting this time (actually, I want to write a quick sort, but it feels a bit difficult to try it...)
/** * Sort the linked list* * @param head * */ public static void sortLinkList(Node head) { Node currentNode; Node nextNode; for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) { for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) { if (nextNode.data > nextNode.next.data) { int temp = nextNode.data; nextNode.data = nextNode.next.data; nextNode.next.data = temp; } } } } 3.7 Find the k-last node in the linked list
This algorithm is quite interesting: set two pointers p1 and p2 to make p2 k nodes faster than p1, and traverse backwards at the same time. When p2 is empty, p1 is the k-th last node
/** * Find the k-th until the last node in the linked list (set two pointers p1 and p2, make p2 k faster than p1, and traverse backwards at the same time. When p2 is empty, p1 is the k-th until the last node* * @param head * @param k k-th until the last node*/ public static Node findKNode(Node head, int k) { if (k < 1 || k > linkListLength(head)) return null; Node p1 = head; Node p2 = head; // p2 k nodes faster than fear p1 for (int i = 0; i < k - 1; i++) p2 = p2.next; // As long as p2 is null, then p1 is the k-last node while (p2.next != null) { p2 = p2.next; p1 = p1.next; } return p1; } 3.8 Delete duplicate data on linked list
It's similar to the bubble sort, as long as it's equal, it can be deleted~
/** * Delete duplicate data on the linked list (similar to bubbling, it is equivalent to deletion) * * @param head head head node*/ public static void deleteDuplecate(Node head) { // Temporary node, (starting from the first node-->node with real data) Node temp = head.next; //Next node of the current node (first node) Node nextNode = temp.next; while (temp.next != null) { while (nextNode.next != null) { if (nextNode.next.data == nextNode.data) { //Delete the next node (the current node points to the next node) nextNode.next = nextNode.next.next; } else { //Continue with the next nextNode = nextNode.next; } } //Next round of comparison temp = temp.next; } } 3.9 Query the intermediate nodes of the linked list
This algorithm is also quite interesting: a pointer that takes 1 step each time, a pointer that takes 2 steps each time, and then takes one step, that is the intermediate node
/** * Query the intermediate node of a single linked list*/ public static Node searchMid(Node head) { Node p1 = head; Node p2 = head; // Take one step and one step two steps until it is null. The middle node that you reach (p2 != null && p2.next != null && p2.next.next != null) { p1 = p1.next; p2 = p2.next.next; } return p1; }3.10 Recursively output single-linked tables from tail to head
/** * Output single linked list from tail to head by recursively* * @param head head node*/ public static void printListReversely(Node head) { if (head != null) { printListReversely(head.next); System.out.println(head.data); } } 3.11 Reverse link list
/** * Implement the inversion of linked list* * @param node The head node of linked list*/ public static Node reverseLinkList(Node node) { Node prev ; if (node == null || node.next == null) { prev = node; } else { Node tmp = reverseLinkList(node.next); node.next.next = node; node.next = null; prev = tmp; } return prev; } Reference to the reverse link list from: //www.VeVB.COM/article/136185.htm
4. Finally
It is not difficult to understand the linked list itself, but it can cause headaches when doing related operations. head.next next next next.... (I am still weak in the algorithm... I don't have enough brains...) I wrote this little thing after two days...
You can do anything by simply knowing its head pointer when operating a linked list.
1. Add data to the linked list
2. Traverse the linked list
3. Insert nodes into the linked list at a given location
4. Get the length of the linked list
5. Delete the node at the given location
6. Sort the linked list
7. Find the k-last node in the linked list
8. Delete duplicate data on linked list
9. Query the intermediate nodes of the linked list
10. Recursively output single-linked table from tail to head
11. Reverse link list
PS: Everyone's implementation will be different, so some small details will inevitably change, and there is no fixed way to write it, so you can realize the corresponding functions~
Summarize
The above is the entire content of this article. I hope that the content of this article has certain reference value for everyone's study or work. If you have any questions, you can leave a message to communicate. Thank you for your support to Wulin.com.
References: