Linked List: Singly 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
Add to:
- 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 SingleLinkedList singleLinkedList = new SingleLinkedList(); //Join, add directly at the end of the linked list // singleLinkedList.add(hero1); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); // singleLinkedList.add(hero4); //Join in order of numbers singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); //show linked list System.out.println("print linked list----"); singleLinkedList.list(); //show linked list System.out.println("print linked list----"); singleLinkedList2.list(); //Test the code that modifies the node HeroNode newHeroNode = new HeroNode(2,"Xiao Lu","Jade unicorn~~"); singleLinkedList.update(newHeroNode); System.out.println("Modified linked list---------"); //show linked list singleLinkedList.list(); //delete node singleLinkedList.del(1); singleLinkedList.del(4); System.out.println("Deleted linked list"); singleLinkedList.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) /** * * @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, 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 class SingleLinkedList { //First initialize a head node, do not move the head node private HeroNode head = new HeroNode(0,"",""); //return head node public HeroNode getHead() { return head; } //Add node to singly linked list //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) /** * * @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, 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 head.next = reverseHead.next; }
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 stack.add("jack"); stack.add("tom"); stack.add("smith"); //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) { return head2; } if(head2 == null) { return head1; } HeroNode mergeHead = null; if(head1.no == 0 && head2.no == 0) { if(head1.next.no <= head2.next.no) { mergeHead = head1; }else { mergeHead = head2; } mergeHead.next = mergeTwoLists(head1.next, head2.next); }else { if(head1.no <= head2.no) { mergeHead = head1; mergeHead.next = mergeTwoLists(head1.next, head2); }else { mergeHead = head2; mergeHead.next = mergeTwoLists(head1, head2.next); } } return mergeHead; } //Print linked list based on head node public static void printListByHead(HeroNode head) { //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; } }