# java data structure and algorithm three: linked list (single linked list)

### 1. Introduction to linked list

A linked list is an ordered list, but it is stored in memory as follows: The summary is as above:

1) The linked list is stored in the form of nodes, which is chain storage

2) Each node contains data field, next field: points to the next node

3) As shown in the figure: It is found that each node of the linked list is not necessarily stored continuously (that is, the addresses are not continuous)

4) The linked list is divided into a linked list with a head node and a linked list without a head node, which is determined according to actual needs

• The schematic diagram of the logical structure of the singly linked list (with the head node) is as follows: ### Second, the application example of singly linked list

Implemented using a singly linked list with head header - Water Margin Heroes Ranking Management Complete the operations of adding, deleting, modifying and checking heroes (delete, modify, search)

#### 1) In the first method, when adding a hero, add it directly to the end of the linked list

• First create a head header node, the function is to represent the head of the singly linked list
• Later, each time we add a node, it is directly added to the end of the linked list.

Traverse:

• Traverse through an auxiliary variable to help traverse the entire linked list

#### 2) In the second method, when adding a hero, insert the hero into the specified position according to the ranking (if there is this ranking, the addition will fail, and a prompt will be given)

It needs to be added in numbered order:

• First find the position of the newly added node, which is done through auxiliary variables (pointers) and through traversal
• new node.next = temp.next
• put temp.next = new node

#### 3) Modify the node function

Ideas:

1) First find the node, by traversing

2)

```temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
```

#### 4) delete node

Ideas:

• First find the previous node temp of the node that needs to be deleted
• temp.next = temp.next.next
• The deleted node will not have other reference guidelines and will be recycled by the garbage collection mechanism

### 3. Code Demonstration

```public class SingleLinkedListDemo {

public static void main(String[] args) {
//test
//Create a node first
HeroNode hero1 = new HeroNode(1,"Song Jiang","timely rain");
HeroNode hero2 = new HeroNode(2,"Lu Junyi","Jade unicorn");
HeroNode hero3 = new HeroNode(3,"Wu Yong","Zhiduoxing");
HeroNode hero4 = new HeroNode(4,"Lin Chong","leopard head");

//Create a linked list
//Join, add directly at the end of the linked list

//Join in order of numbers

//Test the code that modifies the node
HeroNode newHeroNode = new HeroNode(2,"Xiao Lu","Jade unicorn~~");

//delete node

}

//Method: Get the number of nodes in the singly linked list (if it is a linked list with a head node, the requirement does not count the header)
/**
*
* @return	Returns the number of valid nodes
*/
public static int getLength(HeroNode head) {
if(head.next == null) {
return 0;
}
int length = 0;
//Define an auxiliary variable, there is no statistical head node here
HeroNode cur = head.next;
while(cur != null) {
length++;
cur = cur.next;	//traverse
}
return length;
}
}

//Define SingleLinkedList to manage our heroes
//First initialize a head node, do not move the head node
private HeroNode head = new HeroNode(0,"","");

public HeroNode getHead() {
}

//Idea: When the numbering order 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 move, we need an auxiliary traversal node temp
HeroNode temp = head;
//Traverse the linked list and 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 move, we still use an auxiliary pointer (variable) to help find where to add
//Because of the singly linked list, the temp we are looking for is the previous node at the added position, otherwise it cannot be inserted
HeroNode temp = head;
boolean flag = false; 	//Whether the number added by the flag flag exists, the default is false
while(true) {
if(temp.next == null) {
//Indicates that temp is already at the end of the linked list
break;
}
if(temp.next.no > heroNode.no) {	//The position is found, and it is inserted 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 backward, traverse the current linked list
}
//Determine the value of flag
if(flag) {
//The flag is true and cannot be added, indicating that the number exists
System.out.printf("The number of the hero to be inserted%d already exists, cannot join\n",heroNode.no);
}else {
//Insert into the linked list, after temp
heroNode.next = temp.next;
temp.next = heroNode;
}
}

//Modify the information of the node and modify it according to the no number, that is, the no number cannot be changed
//illustrate
//1. You can modify it according to the no of new HeroNode
public void update(HeroNode newHeroNode) {
//Determine if it is empty
if(head.next == null) {
System.out.println("linked list is empty");
}
//Find the node that needs to be modified and number it according to no
//First define an auxiliary variable
HeroNode temp = head.next;
boolean flag = false;		//Used to indicate whether the node is found
while(true) {
if(temp == null) {
break;	//The linked list has been traversed
}
if(temp.no == newHeroNode.no) {
//find node
flag = true;
break;
}
temp = temp.next;
}
//Determine whether the node to be modified is found according to the flag
if(flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
//could not find it
System.out.printf("No number found%d node, which cannot be modified\n",newHeroNode.no);
}
}

//delete node
//ideas
//1. The head cannot move, so we need a temp auxiliary node to find the previous node of the node to be deleted
//2. Explain that when we are comparing, it is the no comparison between temp.next.no and the node that needs 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) {
//has reached the end of the linked list
break;
}
if(temp.next.no == no) {
//Find the previous node temp of the node to be deleted
flag = true;
break;
}
temp = temp.next;
}
//Judgment flag
if(flag) {
//found, can be deleted
temp.next = temp.next.next;
}else {
System.out.printf("to delete%d node does not exist\n",no);
}
}

//Display linked list (traverse)
public void list() {
//Check if the linked list is empty
if(head.next == null) {
System.out.println("linked list is empty");
return;
}
//Because the head node cannot move, we need an auxiliary variable to traverse
HeroNode temp = head.next;
while(true) {
//Determine if it is at the end of the linked list
if(temp == null) {
break;
}
//output node information
System.out.println(temp);
//move temp back
temp = temp.next;
}
}
}

//Define a HeroNode, each HeroNode, the object is a node
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;	//point to the next node

//Constructor
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}

//To show the method, we override toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}

}
```

### Four, single-chain surface test questions

Common interview questions about singly linked lists are as follows:

#### 1) Find the number of valid nodes in the singly linked list

```	//Method: Get the number of nodes in the singly linked list (if it is a linked list with a head node, the requirement does not count the header)
/**
*
* @return	Returns the number of valid nodes
*/
public static int getLength(HeroNode head) {
if(head.next == null) {
return 0;
}
int length = 0;
//Define an auxiliary variable, there is no statistical head node here
HeroNode cur = head.next;
while(cur != null) {
length++;
cur = cur.next;	//traverse
}
return length;
}
```

#### 2) Find the k-th node from the bottom in the singly linked list [Sina interview questions]

```	//Find the k-th last node in a singly linked list [Sina interview]
//ideas
//1. Write a method to receive the head node and receive an index at the same time
//2. index represents the last index node
//3. First traverse the linked list from beginning to end to get the total length of the linked list getLength
//4. After getting the size, we traverse (size-index) from the first one of the linked list, and we can get
//5. If found, return the node, otherwise return null
public static HeroNode findLastIndexNode(HeroNode head, int index) {
//If the linked list is empty, return null
if(head.next == null) {
return null;	//could not find it
}
//The first traversal gets the length of the linked list (number of nodes)
int size = getLength(head);
//The second traversal size-index The position is our last K-th node
//Do an index check first
if(index <= 0 || index > size) {
return null;
}
//Define an auxiliary variable, the for loop is positioned to the reciprocal index
HeroNode cur = head.next;	//3
for(int i = 0 ; i< size -index; i++) {
cur = cur.next;
}
return cur;
}
```

#### 3) Inversion of singly linked list [Tencent interview questions]

```	//Reverse the singly linked list [Tencent interview questions]
public static void reversetList(HeroNode head) {
//If the current linked list is empty, or there is only one node, return directly without reversing
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;	//point to the next node of the current node [cur]
HeroNode reverseHead = new HeroNode(0, "","");
//Traverse the original linked list
//Every time a node is traversed, it is taken out and placed at the forefront of the new linked list reverseHead
while(cur != null) {
next = cur.next;	//First temporarily save the next node of the current node, 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;	//let cur move back
}
//Point head.next to reverseHead.next to reverse the singly linked list
}
```

#### 4) Print the singly linked list from the end to the beginning [Baidu interview questions, method 1: reverse traversal; method 2: Stack stack]

Ideas:

• Method 1: Reverse the singly linked list first, and then traverse it. The problem with this is that it will destroy the structure of the original singly linked list. It is not recommended
• Method 2: You can use the stack data structure to push each node into the stack, and then use the first-in-last-out feature of the stack to achieve the effect of reverse order printing

An example of using the stack Stack:

```//Demonstrate the basic use of stack stack
public class TestStack {

public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
//push onto the stack
//pop
//smith,tom,jack
while(stack.size() > 0) {
System.out.println(stack.pop());	//pop is to remove the data from the top of the stack
}

}
}
```

Use the stack to print in reverse order:

```	//Using the data structure of the stack, each node is pushed into the stack, and then the effect of reverse order printing is realized by using the advanced and last-entry characteristics of the stack [Baidu]
public static void reversePrint(HeroNode head) {
if(head.next == null) {
return;	//Empty linked list, cannot print
}
//Create a stack and push each node onto the stack
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
//Push all nodes in the linked list onto the stack
while(cur != null) {
stack.push(cur);
cur = cur.next;	//cur moves backwards so that the next node can be pushed
}
//Print the node in the stack and pop it from the stack
while(stack.size() > 0) {
System.out.println(stack.pop());	//The feature of stack is first-in, last-out
}
}
```

#### 5) Merge two ordered singly linked lists, the linked list after merging is still in order [After-school exercise]

Ideas:

Using the idea of ​​recursion, recursively returns nodes with small numbers

Code:

```	//Merge two ordered singly linked lists, the linked list after merging is still in order [exercise]
public static HeroNode mergeTwoLists(HeroNode head1,HeroNode head2) {
if(head1 == null) {
}
if(head2 == null) {
}
HeroNode mergeHead = null;
if(head1.no == 0 && head2.no == 0) {
}else {
}
}else {
}else {
}
}

}

//Print linked list based on head node
//The linked list is empty and does not print
if(head.next == null) {
return;
}
HeroNode cur = head.next;
while(cur != null) {
System.out.println(cur);
cur = cur.next;
}
}
```

Tags: Java data structure

Posted by Mr Camouflage on Wed, 25 May 2022 02:04:36 +0300