One, foreword
Recently in the review of data structure and algorithm, some algorithm questions used the idea of stack, speaking of stack has to say linked list. Arrays and linked lists are the basis of linear storage structures. Stacks and queues are applications of linear storage structures
This article mainly explains the basic knowledge of single linked list, do a simple introduction ~ if there is wrong place please correct
Review and learn new
When we talk about linked lists, let’s talk about arrays first.
2.1 Reviewing Arrays
We can learn arrays in both C and Java:
- An array is a linear structure of continuous storage with the same element type and equal size
Advantages of arrays:
- Fast access speed
Disadvantages of arrays:
- You must know the length of the array beforehand
- Inserting and removing elements is slow
- Space is usually limited
- Large contiguous blocks of memory are required
- Inserting and deleting elements is inefficient
2.2 Linked list Description
Having looked at the array, go back to our linked list:
- Linked lists are discrete storage linear structures
N nodes are distributed discreetly and connected to each other by Pointers. Each node has only one precursor node, and each node has only one follow-up node. The first node has no precursor node, and the last node has no follow-up node.
Linked list advantages:
- There is no limit to space
- Insert removes elements quickly
Disadvantages of linked lists:
- Slow access
Linked list related terms, I still through the above diagram to illustrate it:
To determine a linked list we only need the head pointer, through the head pointer can be the whole list can be deduced ~
The linked list is divided into several categories:
- Singly linked list
- One node points to the next
- Two-way linked list
- A node has two pointer fields
- Circular linked list
- You can find all the other nodes through any one node, and loop by pointing the last node of both (bidirectional/one-way) lists to the first node
When working with linked lists, keep in mind:
- The pointer field in a node points to a node!
Java implementation of linked lists
Algorithm:
- traverse
- To find the
- empty
- The destruction
- For the length of the
- The sorting
- Remove nodes
- Insert the node
Ps: I define the head node on the member variable:
private static Node head = new Node();
Copy the codeFirst, we define a class as a node
- Data fields
- Pointer to the domain
I’m just going to call it public for convenience.
public class Node {
/ / data domain
public Integer data;
// pointer field, pointing to the next node
public Node next;
public Node(a) {}public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next; }}Copy the code3.1 Creating a Linked List (Adding nodes)
Insert data into a linked list:
- Find the tail node and insert
- Next connects the head node to the new node even if the head node is null (I already initialized the head node, so there is no need to determine whether the head node is null) ~ without going through the while loop
/** * Add data to the list **@paramValue Data to be added */
public static void addData(int value) {
// Initializes the node to be added
Node newNode = new Node(value);
// Temporary node
Node temp = head;
// Find the tail node
while(temp.next ! =null) {
temp = temp.next;
}
// The head node is included. Next is null
temp.next = newNode;
}
Copy the code3.2 Traversing the linked list
We have written the increment method above, now let’s iterate over it to see if it works
Start at the first node and continue until the next node has no data:
/** * traverses the list **@paramHead Indicates the head node */
public static void traverse(Node head) {
// Temporary nodes, starting from the first node
Node temp = head.next;
while(temp ! =null) {
if(temp.data ! =null) {
System.out.println("Java3y:" + temp.data);
}
// Move on to the next onetemp = temp.next; }}Copy the codeResults:
3.3 Inserting a Node
- To insert a node into a linked list, you must first check whether the location is valid
- Just find the node above the position you want to insert
/** * Insert node **@paramHead Indicates the header pointer *@paramIndex The position to insert *@paramValue Specifies the value to be inserted */
public static void insertNode(Node head, int index, int value) {
// Check whether the specified position is valid.
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("The insertion position is illegal.");
return;
}
// Temporary node, starting from the beginning node
Node temp = head;
// Record the current position of the traversal
int currentPos = 0;
// Initialize the node to be inserted
Node insertNode = new Node(value);
while(temp.next ! =null) {
// Find the location of the last node
if ((index - 1) == currentPos) {
// Temp represents the previous node
// Pass the pointer from the previous node to the inserted node
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; }}Copy the code3.4 Obtaining the length of the Linked List
To get the length of the list, it is easy to iterate over each node +1
/** * get the length of the list *@paramHead Indicates the header pointer */
public static int linkListLength(Node head) {
int length = 0;
// Temporary nodes, starting from the first node
Node temp = head.next;
// Find the tail node
while(temp ! =null) {
length++;
temp = temp.next;
}
return length;
}
Copy the code3.5 Deleting a Node
Deleting a node at a location is similar to inserting a node, in that you need to find the previous node. Change the pointer field of the previous node to delete ~
/** * Delete node ** by location@paramHead Indicates the header pointer *@paramIndex The location to be deleted */
public static void deleteNode(Node head, int index) {
// Check whether the specified position is valid.
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("Deleting a location is illegal.");
return;
}
// Temporary node, starting from the beginning node
Node temp = head;
// Record the current position of the traversal
int currentPos = 0;
while(temp.next ! =null) {
// Find the location of the last node
if ((index - 1) == currentPos) {
// Temp represents the previous node
//temp.next represents the node you want to delete
// Store the node you want to delete
Node deleteNode = temp.next;
// The next node that wants to delete the node is taken over by the previous node
temp.next = deleteNode.next;
//Java will recycle it, so setting it to null doesn't make much sense.
deleteNode = null;
return; } currentPos++; temp = temp.next; }}Copy the code3.6 Sorting linked Lists
8 kinds of sorting algorithms have been described before, this time pick simple bubble sort bar (in fact, I want to write a quick sort, try to feel a little difficult…..)
/** * 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) {
inttemp = nextNode.data; nextNode.data = nextNode.next.data; nextNode.next.data = temp; }}}}Copy the code3.7 Find the KTH last node in the linked list
This algorithm is quite interesting: set two Pointers P1 and p2, so that P2 is k nodes faster than P1. At the same time, it traverses backwards. When P2 is empty, p1 is the KTH node from last
/** * find the last KTH node in the list (set two Pointers P1 and p2, let p2 be k nodes faster than p1, while traversing backwards, when p2 is empty, p1 is the last KTH node **)@param head
* @paramThe KTH node from the bottom of k */
public static Node findKNode(Node head, int k) {
if (k < 1 || k > linkListLength(head))
return null;
Node p1 = head;
Node p2 = head;
// P2 is k nodes faster than P1
for (int i = 0; i < k - 1; i++)
p2 = p2.next;
// If p2 is null, p1 is the penultimate KTH node
while(p2.next ! =null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
Copy the code3.8 Deleting duplicate Linked List Data
Here there is a problem, before you to: blog.csdn.net/ifollowrive…
For reference
3.9 Querying the Middle Node of the Linked List
This algorithm is also interesting: a pointer that takes one step at a time, two steps at a time, two steps at a time, and then one step, that is the intermediate node
/** * query the middle node of the single-linked list */
public static Node searchMid(Node head) {
Node p1 = head;
Node p2 = head;
// The intermediate node is reached when the intermediate node is null
while(p2 ! =null&& p2.next ! =null&& p2.next.next ! =null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
Copy the code3.10 Output a single linked list from end to end recursively
/** * outputs a single linked list ** recursively from end to end@paramHead Indicates the head node */
public static void printListReversely(Node head) {
if(head ! =null) {
printListReversely(head.next);
if(head.data ! =null) { System.out.println(head.data); }}}Copy the code3.11 Reverse the linked list
/** * reverse the list **@paramHead The head node of the linked list */
public static Node reverseList(Node head) {
Node pre = null;
Node cur = head;
while(cur ! =null) {
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
// After flipping, use the following code to iterate:
public static void traverse4Reverse(Node head) {
// Temporary nodes, starting from the first node
Node temp = head;
while(temp ! =null) {
if(temp.data ! =null) {
System.out.println("Java3y:" + temp.data);
}
// Move on to the next onetemp = temp.next; }}Copy the code
Reverse linked list reference from:
- www.cnblogs.com/hanxue11225…
Four, the last
It’s not hard to understand linked lists, but doing them is a headache, head. Next next next next…. I’m still weak in algorithms. My brain is running out…..) This is all I’ve written in two days…
To operate a linked list, you only need to know its head pointer to do anything
- Add data to a linked list
- Iterate to find the tail node and insert (as long as
while(temp.next ! = null)And exit the loop to find the tail node.
- Iterate to find the tail node and insert (as long as
- Traversing the list
- Starting from the first node (valid node), as long as it is not null, output
- Insert a node into the linked list at the given location
- First determine if the location is valid (within the length of the list)
- Find the last node where you want to insert
- The insertion node points to the previous node instead of the previous node
- The previous node pointer field points to the node you want to insert
-
- Gets the length of the list
- Each time a node is accessed, the variable ++ operation is sufficient
- Deletes a node at a given location
- First determine if the location is valid (within the length of the list)
- Find the last node where you want to insert
- Points the previous node to the next node
-
- Sort the linked list
- The bubble algorithm is used to sort them
- Find the last KTH node in the linked list
- Set two Pointers P1 and p2, so that P2 is k nodes faster than P1 and traverses backward at the same time. When P2 is empty, p1 is the KTH node from last to last
- Delete duplicate linked list data
- The operation is similar to bubble sort, as long as it is equal, the ~ can be removed
- Query the middle node of the linked list
- This algorithm is also interesting: a pointer that takes one step at a time, two steps at a time, two steps at a time, and then one step, that is the intermediate node
- Recursively outputs a single linked list from end to end
- So as long as there’s some data down there, you go down, so recursion is going to be going back to the end.
- Reverse a linked list
- There are recursive and non-recursive ways, which I find difficult. You can check it out at the link I gave you
PS: Everyone’s implementation will be different, so some small details will inevitably have some changes, there is no fixed writing method, can achieve the corresponding function ~
References:
- www.cnblogs.com/whgk/p/6589…
- www.cnblogs.com/bywallance/…
If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y