Introduction to linked list
1 linked list is stored in the form of nodes, which is chain storage
2. Each node contains data field and next field: points to the next node
As shown in the figure: it is found that each node of the linked list is not necessarily stored continuously
4 the linked list is divided into the linked list with the leading node and the linked list without the head node, which is determined according to the actual needs
1, One way linked list code implementation
public class SingleLinkedListDemo {
class SingleLinkedList {
//First initialize a head node. The head node does not move and does not store specific data
private HeroNode head = new HeroNode(0, "", "");
//Return header node
public HeroNode getHead() {
return head;
}
//Add node to one-way linked list
//Train of thought, when the numbering sequence is not considered
//1. Find the last node of the current linked list
//2. Point the next of the last node to the new node
public void add(HeroNode heroNode) {
//Because the head node cannot be moved, we need an auxiliary node to traverse temp
HeroNode temp = head;
//Traverse the linked list to find the last
while(true) {
//Find the end of the linked list
if(temp.next == null) {//
break;
}
//If the last is not found, move temp back
temp = temp.next;
}
//When exiting the while loop, temp points to the end of the linked list
//Point the next of the last node to the new node
temp.next = heroNode;
}
//The second way is to insert the hero into the specified position according to the ranking when adding the hero
//(if there is this ranking, the addition fails and a prompt is given)
public void addByOrder(HeroNode heroNode) {
//Because the head node cannot be moved, we still use an auxiliary pointer (variable) to help find the added position
//Because of the single linked list, because the temp we are looking for is the previous node in the add location, otherwise it cannot be inserted
HeroNode temp = head;
boolean flag = false; // Whether the number added by flag flag exists. The default is false
while(true) {
if(temp.next == null) {//Note that temp is at the end of the linked list
break; //
}
if(temp.next.no > heroNode.no) { //If the location is found, insert it after temp
break;
} else if (temp.next.no == heroNode.no) {//Indicates that the number of the heroNode you want to add already exists
flag = true; //Description number exists
break;
}
temp = temp.next; //Move back and traverse the current linked list
}
//Judge the value of flag
if(flag) { //Cannot add, description number exists
System.out.printf("The number of the hero to insert %d It already exists, Can't join\n", heroNode.no);
} else {
//Insert it into the linked list, after temp
heroNode.next = temp.next;//Pass the next node pointed to by the original node to the newly added node
temp.next = heroNode;//Then let the original node point to the newly added node, so that an insertion is completed
}
}
//Modify the node information according to the no number, that is, the no number cannot be changed
//explain
//1. Modify according to the no of newHeroNode
public void update(HeroNode newHeroNode) {
//Judge whether it is empty
if(head.next == null) {
System.out.println("The linked list is empty~");
return;
}
//Find the node to be modified and number it according to no
//Define an auxiliary variable
HeroNode temp = head.next;
boolean flag = false; //Indicates whether the node is found
while(true) {
if (temp == null) {
break; //The linked list has been traversed
}
if(temp.no == newHeroNode.no) {
//find
flag = true;
break;
}
temp = temp.next;
}
//Judge whether to find the node to be modified according to the flag
if(flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else { //Can't find
System.out.printf("No number found %d The node cannot be modified\n", newHeroNode.no);
}
}
//Delete node
//thinking
//1. The head cannot be moved, so we need a temp auxiliary node to find the previous node of the node to be deleted
//2. Explain that when we compare, it is temp next. Comparison between NO and no of the node to be deleted
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // Flag whether the node to be deleted is found
while(true) {
if(temp.next == null) { //It has reached the end of the linked list
break;
}
if(temp.next.no == no) {
//Found the previous node temp of the node to be deleted
flag = true;
break;
}
temp = temp.next; //temp backward, traversal
}
//Judge flag
if(flag) { //find
//Can delete
temp.next = temp.next.next;
}else {
System.out.printf("To delete %d Node does not exist\n", no);
}
}
//Display linked list [traversal]
public void list() {
//Determine whether the linked list is empty
if(head.next == null) {
System.out.println("The linked list is empty");
return;
}
//Because the head node cannot be moved, we need an auxiliary variable to traverse
HeroNode temp = head.next;
while(true) {
//Judge whether to reach the end of the linked list
if(temp == null) {
break;
}
//Output node information
System.out.println(temp);
//Move temp backward. Be careful
temp = temp.next;
}
}
}
//Define a HeroNode. Each HeroNode object is a node
static class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next; //Point to next node
//constructor
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
//To display the method, we re toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
}
2, Single chain surface test
Find the number of effective nodes in the single linked list
//Method: obtain the number of nodes in the single linked list (if it is the linked list of the leading node, the head node shall not be counted)
/**
*
* @param head Head node of linked list
* @return Returns the number of valid nodes
*/
public static int getLength(HeroNode head) {
if(head.next == null) { //Empty linked list
return 0;
}
int length = 0;
//Define an auxiliary variable. Here we do not have a statistical header node
HeroNode cur = head.next;
while(cur != null) {
length++;
cur = cur.next; //ergodic
}
return length;
}
Find the penultimate node in the single lin k ed list [Sina interview question]
//Find the penultimate node in the single lin k ed list [Sina interview question]
//thinking
//1. Write a method to receive the head node and an index at the same time
//2. index indicates the penultimate node
//3. Traverse the linked list from beginning to end to get the total length of the linked list getLength
//4. After getting the size, we can get it by traversing the first size index in the linked list
//5. If it is found, the node will be returned; otherwise, nulll will be returned
public static HeroNode findLastIndexNode(HeroNode head, int index) {
//Judge if the linked list is empty, return null
if(head.next == null) {
return null;//Can't find
}
//The first traversal obtains the length of the linked list (number of nodes)
int size = getLength(head);
//The second time we traverse the size index position is the K-th node from the bottom
//First do an index check
if(index <=0 || index > size) {
return null;
}
//Defined to the auxiliary variable, the for loop locates the index of the reciprocal
HeroNode cur = head.next; //3 // 3 - 1 = 2
for(int i =0; i< size - index; i++) {
cur = cur.next;
}
return cur;
}
Reversal of single linked list [Tencent interview question]
Method 1: create a new linked list to save data
- First define a node reverseHead = new HeroNode();
- Traverse the original linked list from beginning to end. Take out each node and put it at the front of the new linked list reverseHead
- The head of the original linked list next = reverseHead. next
//Reverse single linked list
public static void reversetList(HeroNode head) {
//If the current linked list is empty or there is only one node, there is no need to reverse and return directly
if(head.next == null || head.next.next == null) {
return ;
}
//Define an auxiliary pointer (variable) to help us traverse the original linked list
HeroNode cur = head.next;
HeroNode next = null;// Points to the next node of the current node [cur]
HeroNode reverseHead = new HeroNode(0, "", "");
//Traverse the original linked list. Every time you traverse a node, take it out and put it at the front of the new linked list reverseHead
//Use your head
while(cur != null) {
next = cur.next;//First save the next node of the current node temporarily, because it needs to be used later
cur.next = reverseHead.next;//Point the next node of cur to the front of the new linked list
reverseHead.next = cur; //Connect cur to the new linked list
cur = next;//Move cur back
}
//Put head Next points to reversehead Next, realize the inversion of single linked list
head.next = reverseHead.next;
}
Method 2: use the data structure of stack
//You can use the data structure of stack to press each node into the stack, and then use the first in and last out characteristics of stack to realize the effect of reverse order printing
public static void reversePrint(HeroNode head) {
if(head.next == null) {
return;//Empty linked list, cannot print
}
//To create a stack, press each node into the stack
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
//Push all nodes of the linked list onto the stack
while(cur != null) {
stack.push(cur);
cur = cur.next; //cur moves backward so that the next node can be pushed in
}
//Print the nodes in the stack and pop them out of the stack
while (stack.size() > 0) {
System.out.println(stack.pop()); //stack is characterized by first in and last out
}
}
Print the single linked list from end to end [Baidu, requires method 1: reverse traversal. Method 2: Stack]
- The requirement of the above question is to print the single linked list in reverse order
- Method 1: first reverse the single linked list and then traverse it. The problem with this is that it will destroy the structure of the original single linked list. It is not recommended
- Method 2: you can use the data structure of stack to press each node into the stack, and then use the first in and last out characteristics of stack to realize the effect of reverse order printing
An example demonstrates the use of Stack
//You can use the data structure of stack to press each node into the stack, and then use the first in and last out characteristics of stack to realize the effect of reverse order printing
public static void reversePrint(HeroNode head) {
if(head.next == null) {
return;//Empty linked list, cannot print
}
//To create a stack, press each node into the stack
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
//Push all nodes of the linked list onto the stack
while(cur != null) {
stack.push(cur);
cur = cur.next; //cur moves backward so that the next node can be pushed in
}
//Print the nodes in the stack and pop them out of the stack
while (stack.size() > 0) {
System.out.println(stack.pop()); //stack is characterized by first in and last out
}
}
3, Bidirectional linked list
For one-way linked list, the search direction can only be one direction, while the two-way linked list can search forward or backward.
A one-way linked list cannot be deleted by itself and needs to rely on auxiliary nodes, while a two-way linked list can be deleted by itself. Therefore, when we delete a single linked list, we always find temp, which is the previous node of the node to be deleted
Analyze the operation ideas of traversal, addition, modification and deletion of two-way linked list = = > code implementation
- The traversal party is the same as the single linked list, but it can be searched forward or backward
- Add (added to the end of the bidirectional linked list by default)
(1) First find the last node of the two-way linked list
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp; - The modification idea is the same as the original one-way linked list
- delete
(1) Because it is a two-way linked list, we can delete a node by ourselves
(2) Directly find the node to be deleted, such as temp
(3) temp.pre.next = temp.next / / point the next of the node on temp to the next node of temp, which is equivalent to skipping temp directly
(4) temp.next.pre = temp.pre; // Similarly, point the pre of the node under temp to the previous node of temp
// Create a class of two-way linked list
static class DoubleLinkedList {
// First initialize a head node. The head node does not move and does not store specific data
private HeroNode2 head = new HeroNode2(0, "", "");
// Return header node
public HeroNode2 getHead() {
return head;
}
// Method of traversing bidirectional linked list
// Display linked list [traversal]
public void list() {
// Because the head node cannot be moved, we need an auxiliary variable to traverse
HeroNode2 temp = head.next;
while (true) {
if (temp == null) {
break;
}
// Output node information
System.out.println(temp);
// Move temp backward. Be careful
temp = temp.next;
}
}
// Add a node to the end of the bidirectional linked list
public void add(HeroNode2 heroNode) {
HeroNode2 temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
// When exiting the while loop, temp points to the end of the linked list
// Form a two-way linked list
temp.next = heroNode;
heroNode.pre = temp;
}
//The second way is to insert the hero into the specified position according to the ranking when adding the hero
//(if there is this ranking, the addition fails and a prompt is given)
public void addByOrder(HeroNode2 heroNode) {
//Because the head node cannot be moved, we still use an auxiliary pointer (variable) to help find the added position
HeroNode2 temp = head;
boolean flag = false; // Whether the number added by flag flag exists. The default is false
while(true) {
if(temp.next == null) {//Note that temp is at the end of the linked list
break; //
}
if(temp.next.no > heroNode.no) { //Location found
break;
} else if (temp.next.no == heroNode.no) {//Indicates that the number of the heroNode you want to add already exists
flag = true; //Description number exists
break;
}
temp = temp.next; //Move back and traverse the current linked list
}
//Judge the value of flag
if(flag) { //Cannot add, description number exists
System.out.printf("The number of the hero to insert %d It already exists, Can't join\n", heroNode.no);
} else {
heroNode.next=temp.next;
temp.next.pre=heroNode;
temp.next = heroNode;
heroNode.pre = temp;
}
}
// When modifying the content of a node, you can see that the node content modification of the two-way linked list is the same as that of the one-way linked list
public void update(HeroNode2 newHeroNode) {
// Judge whether it is empty
if (head.next == null) {
System.out.println("The linked list is empty~");
return;
}
// Find the node to be modified and number it according to no
// Define an auxiliary variable
HeroNode2 temp = head.next;
boolean flag = false; // Indicates whether the node is found
while (true) {
if (temp == null) {
break;
}
if (temp.no == newHeroNode.no) {
// find
flag = true;
break;//Exit the loop directly
}
temp = temp.next;
}
// Judge whether to find the node to be modified according to the flag
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else { // Can't find
System.out.printf("No number found %d The node cannot be modified\n", newHeroNode.no);
}
}
// Delete a node from the two-way linked list,
// explain
// For a two-way linked list, we can directly find the node to be deleted
// 2. After finding it, delete it by yourself
public void del(int no) {
// Judge whether the current linked list is empty
if (head.next == null) {// Empty linked list
System.out.println("The linked list is empty and cannot be deleted");
return;
}
HeroNode2 temp = head.next; // Auxiliary variable (pointer)
boolean flag = false; // Flag whether the node to be deleted is found
while (true) {
if (temp == null) {
break;
}
if (temp.no == no) {
flag = true;
break;
}
temp = temp.next;
}
// Judge flag
if (flag){
temp.pre.next = temp.next;
// What's wrong with our code here?
// If it is the last node, you do not need to execute the following sentence, otherwise a null pointer will appear
if (temp.next != null) {
temp.next.pre = temp.pre;
}else {
System.out.printf("To delete %d Node does not exist\n", no);
}
}
}
}
// Define HeroNode2. Each HeroNode object is a node
static class HeroNode2{
public int no;
public String name;
public String nickname;
public HeroNode2 next;// Point to the next node, which is null by default
public HeroNode2 pre;//Point to the previous node, which is null by default
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
// To display the method, we re toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
4, Unidirectional ring linked list and Joseph problem
Joseph problem description
Josephu's problem is: let n people with numbers 1, 2,... N sit around. It is agreed that the person with number k (1 < = k < = n) will count from 1, and the person who counts to m will be listed. Its next person will count from 1, and the person who counts to m will be listed again, and so on until everyone is listed, resulting in a sequence of out of line numbers.
Tip: use a circular linked list without leading nodes to deal with the Josephu problem: first form a single circular linked list with n nodes, and then count from 1 from node k. when m is counted, the corresponding node is deleted from the linked list, and then count from 1 from the next node of the deleted node until the last node is deleted from the linked list. The algorithm ends.
Circular linked list
The idea of constructing a one-way circular linked list
- First create the first node, let the first point to the node, and form a ring
- Later, when we create a new node, we can add the node to the existing ring linked list
Traverse circular linked list
- First, let an auxiliary pointer (variable) curBoy point to the first node
- Then go through the circular linked list through a while loop to curboy Next = = first end
According to the user's input, generate the order of a child out of the circle
n = 5, that is, there are 5 people
k = 1, counting off from the first person
m = 2, number 2
- You need to create an auxiliary pointer (variable) helper, which should point to the last node of the ring linked list in advance
Add: let the first and helper move k - 1 time before the child counts off - When the child counts off, let the first and helper pointers move m - 1 times at the same time
- At this time, the child node pointed to by first can be circled
first = first .next
helper.next = first
The node pointed to by first has no reference and will be recycled
Order of out circle
2->4->1->5->3
code implementation
public class Josepfu {
public static void main(String[] args) {
CircleSingleLinkedList c = new CircleSingleLinkedList();
c.addBoy(2);
}
}
// Create a circular one-way linked list
class CircleSingleLinkedList{
// Create a first node, which currently has no number
private Boy first = null;
// Add child nodes to build a circular linked list
public void addBoy(int nums){
if (nums < 1){
System.out.println("nums The value of is incorrect");
return;
}
Boy curBoy = null; // Auxiliary pointer to help build a circular linked list
// Use for to create our circular linked list
for (int i = 1; i <= nums; i++) {
// Create a child node according to the number
Boy boy = new Boy(i);
if (i == 1){
first = boy;
boy.setNext(first);// Constituent ring
curBoy = first; // Let curBoy point to the first child
System.out.println(curBoy == first);
}else {
//The idea of double pointers is used here. The head pointer frist and the tail pointer curBoy (auxiliary pointer), but curBoy will move back with the new node
//curBoy = boy is this line of code, which keeps curBoy pointing to the end. For curBoy Setnext (boy) is a wonderful line of code
//Question: what might the pointer to the next node point to? This is because curBoy = boy
//When this line of code assigns boy to curBoy, it actually assigns the address and the assignment between objects. Therefore, the pointer at this time represents the object of boy
//When the auxiliary pointer points to the next node, the boy object will also point to the next boy node. System.out.println(curBoy == first)
//The result of this line of code is true, which means that curBoy and first point to the same address
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
// Traverse the current circular linked list
public void showBoy() {
// Determine whether the linked list is empty
if (first == null) {
System.out.println("There are no children~~");
return;
}
// Because first cannot move, we still use an auxiliary pointer to complete the traversal
Boy curBoy = first;
while (true) {
System.out.printf("Child's number %d \n", curBoy.getNo());
if (curBoy.getNext() == first) {// Description: the traversal has been completed
break;
}
curBoy = curBoy.getNext(); // curBoy move back
}
}
// According to the user's input, calculate the order of the child's circle
/**
*
* @param startNo
* It means counting from the first child
* @param countNum
* It means counting
* @param nums
* Indicates how many children were in the circle at first
*/
public void countBoy(int startNo, int countNum, int nums){
// Check the data first
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("Error in parameter input, please re-enter");
return;
}
// Create an auxiliary pointer to help the child out of the circle, that is, point to the tail. When the child out of the circle, this auxiliary pointer is equal to temp in the single linked list
//Pointer, and then use it in the auxiliary pointer to delete the node, which is the work of children out of the circle
Boy helper = first;
// You need to create an auxiliary pointer (variable) helper, which should point to the last node of the ring linked list in advance
while (true) {
if (helper.getNext() == first) { // Note the helper points to the last child node
break;
}
helper = helper.getNext();
}
//Before the child counts off, let the first and helper move startNo - 1 time, because it is not guaranteed to count off from the first child
//First move to startNo, because the node actually starts from 0, so you need to subtract one. In addition, the helper is the one before the first
for(int j = 0; j < startNo - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
//When the child counts off, let the first and helper pointers move m - 1 times at the same time, and then make a circle
//Here is a loop operation, knowing that there is only one node in the circle
while (true){
if (first == helper){//There is only one node left
break;
}
//Let the first and helper pointers move countNum - 1 at the same time
for(int j = 0; j < countNum - 1; j++){
first = first.getNext();
helper = helper.getNext();
}
//At this time, the node first points to is the child node to be circled
System.out.printf("child%d Out of circle\n", first.getNo());
first = first.getNext();//Point the first pointer to the next node
helper.setNext(first);//Point the node represented by the helper to first, so that the node out of the circle can be deleted
}
System.out.printf("Number of the last child left in the circle%d \n", first.getNo());
}
}
// Create a Boy class to represent a node
class Boy {
private int no;// number
private Boy next; // Point to the next node, null by default
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}