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;
		}
	}