Linked list (linear structure)

Single chain list

A single linked list is a linked list of leading nodes

The illustration

add to

Add... In order

Delete

Code

Notes have ideas to explain ~

package com.atguigu.linkedlist;

import java.util.Stack;

//author qij
public class SingleLinkedListDemo {
    

	public static void main(String[] args) {
    
		// To test 
		// Create the node first 
		HeroNode hero1 = new HeroNode(1, " Song Jiang ", " Timely rain ");
		HeroNode hero2 = new HeroNode(2, " Jun-yi lu ", " Yu Qilin ");
		HeroNode hero3 = new HeroNode(3, " Wu Yong ", " A wise man ");
		HeroNode hero4 = new HeroNode(4, " Lin Chong ", " Leopard head ");

		// Create a list to give 
		SingleLinkedList singleLinkedList = new SingleLinkedList();


		// Join in 
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero4);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);

		// Add in order of number 
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero3);

		// Show me a 
		singleLinkedList.list();

		// Test the code to modify the node 
		HeroNode newHeroNode = new HeroNode(2, " " ", " Yu Qilin ~~");
		singleLinkedList.update(newHeroNode);

		System.out.println(" The modified linked list ~~");
		singleLinkedList.list();

		// Delete a node 
		singleLinkedList.del(1);
		singleLinkedList.del(4);
		System.out.println(" Linked list after deletion ~~");
		singleLinkedList.list();


	}

}


// Definition SingleLinkedList  Our hero in charge 
class SingleLinkedList {
    
	// Initialize a header node first ,  Don't move the head node ,  Do not store specific data 
	private HeroNode head = new HeroNode(0, "", "");
	
	
	// Return to the header node 
	public HeroNode getHead() {
    
		return head;
	}

	// add to 
	// Ideas 
	//1.  So let's create one head  Head node ,  The function is to represent the head of a single linked list 
	//2.  We will add each node later , Just join directly to   At the end of the list 
	public void add(HeroNode heroNode) {
    
		
		// because head Nodes can't move , So we need an auxiliary traversal  temp
		HeroNode temp = head;
		// Traversing the linked list , Find the last 
		while(true) {
    
			// Find the end of the list 
			if(temp.next == null) {
    //
				break;
			}
			// If you don't find the end ,  Will temp Move backward 
			temp = temp.next;
		}
		// When to exit while loop ,temp It points to the end of the list 
		// Will be the last node of next  Point to   New nodes 
		temp.next = heroNode;
	}
	
	// Add in the specified order 
	//1.  First find the location of the newly added node ,  It's through auxiliary variables ( The pointer ),  Do it through traversal 
	//2.  New nodes .next = temp.next
	//3.  take temp.next =  New nodes 
	public void addByOrder(HeroNode heroNode) {
    
		// because head Nodes can't move , So we need an auxiliary traversal  temp
		HeroNode temp = head;
		//flag Mark whether the number added exists , The default is false
		boolean flag = false;
		while(true) {
    
			if(temp.next == null) {
    // explain temp It's at the end of the list 
				break; //
			} 
			if(temp.next.no > heroNode.no) {
     // Location found , It's just temp Insert after 
				break;
			} else if (temp.next.no == heroNode.no) {
    // State the name you want to add heroNode The number of already exists 
				
				flag = true; // Description number exists 
				break;
			}
			temp = temp.next; // Move backward , Traverse the current list 
		}
		// Judge flag  Value 
		if(flag) {
     // Can not 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 into the linked list , temp Behind 
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// modify 
	// according to  newHeroNode  Of  no  Just modify it 
	public void update(HeroNode newHeroNode) {
    
		// Judge whether it is empty 
		if(head.next == null) {
    
			System.out.println(" Linked list is empty. ~");
			return;
		}
		// Find the node that needs to be modified ,  according to no Number 
		// Define an auxiliary variable 
		HeroNode temp = head.next;
		boolean flag = false; // Indicates whether the node is found 
		while(true) {
    
			if (temp == null) {
    
				break; // We've finished traversing the linked list 
			}
			if(temp.no == newHeroNode.no) {
    
				// find 
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// according to flag  Determine whether to find the node to be modified 
		if(flag) {
    
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
     // Can't find 
			System.out.printf(" Can't find   Number  %d  The node of , Do not modify \n", newHeroNode.no);
		}
	}
	
	// Delete node 
	// Ideas 
	//1. Let's find   The previous node of the node to be deleted  temp
	//2.temp.next = temp.next.next
	//3. Deleted node , There will be no other references to , Will be recycled by the garbage collection mechanism 
	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) {
     // At the end of the list 
				break;
			}
			if(temp.next.no == no) {
    
				// The previous node found to be deleted temp
				flag = true;
				break;
			}
			temp = temp.next; //temp Move backward , Traverse 
		}
		// Judge flag
		if(flag) {
     // find 
			// You can delete 
			temp.next = temp.next.next;
		}else {
    
			System.out.printf(" To delete  %d  Node does not exist \n", no);
		}
	}
	
	// Traversing the linked list 
	public void list() {
    
		// Judge whether the list is empty 
		if(head.next == null) {
    
			System.out.println(" Linked list is empty. ");
			return;
		}
		// Because the head node , Don't move , So we need an auxiliary variable to traverse 
		HeroNode temp = head.next;
		while(true) {
    
			// Judge whether to the end of the list 
			if(temp == null) {
    
				break;
			}
			// Output node information 
			System.out.println(temp);
			// take temp Move backward 
			temp = temp.next;
		}
	}
}

// Definition HeroNode ,  Every HeroNode  Object is a node 
class HeroNode {
    
	public int no;
	public String name;
	public String nickname;
	public HeroNode next; // Point to next node 
	// Constructors 
	public HeroNode(int no, String name, String nickname) {
    
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
	// In order to show the method , Let's do it again toString
	@Override
	public String toString() {
    
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
	
}

Double linked list

There is a problem with the single linked list ：

1. One way linked list , The search direction can only be one direction , The two-way linked list can Look forward or backward
2. One way linked list cannot delete itself , Need to rely on auxiliary nodes , And double linked list , Then you can Self delete , So when we delete a single linked list, the node , Always find temp,temp Is the previous node of the node to be deleted

The illustration

Code

Notes have ideas to explain ~

package com.atguigu.linkedlist;

//author qij
public class DoubleLinkedListDemo {
    

	public static void main(String[] args) {
    
		//  test 
		System.out.println(" Two way linked list test ");
		//  Create the node first 
		HeroNode2 hero1 = new HeroNode2(1, " Song Jiang ", " Timely rain ");
		HeroNode2 hero2 = new HeroNode2(2, " Jun-yi lu ", " Yu Qilin ");
		HeroNode2 hero3 = new HeroNode2(3, " Wu Yong ", " A wise man ");
		HeroNode2 hero4 = new HeroNode2(4, " Lin Chong ", " Leopard head ");
		//  Create a double linked list 
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);
		doubleLinkedList.add(hero4);
		
		doubleLinkedList.list();
		
		//  modify 
		HeroNode2 newHeroNode = new HeroNode2(4, " Gongsun Sheng ", " Into the clouds ");
		doubleLinkedList.update(newHeroNode);
		System.out.println(" The modified linked list ");
		doubleLinkedList.list();
		
		//  Delete 
		doubleLinkedList.del(3);
		System.out.println(" Linked list after deletion ~~");
		doubleLinkedList.list();
		
		
		
	}

}

//  Create a two-way linked list class 
class DoubleLinkedList {
    

	//  Initialize a header node first ,  Don't move the head node ,  Do not store specific data 
	private HeroNode2 head = new HeroNode2(0, "", "");

	//  Return to the header node 
	public HeroNode2 getHead() {
    
		return head;
	}

	//  Traversing two-way list method 
	//  Show list [ Traverse ]
	public void list() {
    
		//  Judge whether the list is empty 
		if (head.next == null) {
    
			System.out.println(" Linked list is empty. ");
			return;
		}
		//  Because the head node , Don't move , So we need an auxiliary variable to traverse 
		HeroNode2 temp = head.next;
		while (true) {
    
			//  Judge whether to the end of the list 
			if (temp == null) {
    
				break;
			}
			//  Output node information 
			System.out.println(temp);
			//  take temp Move backward ,  Be careful 
			temp = temp.next;
		}
	}

	//  Add a node to the end of the bidirectional list .
	public void add(HeroNode2 heroNode) {
    

		//  because head Nodes can't move , So we need an auxiliary traversal  temp
		HeroNode2 temp = head;
		//  Traversing the linked list , Find the last 
		while (true) {
    
			//  Find the end of the list 
			if (temp.next == null) {
    //
				break;
			}
			//  If you don't find the end ,  Will temp Move backward 
			temp = temp.next;
		}
		//  When to exit while loop ,temp It points to the end of the list 
		//  Form a two-way linked list 
		temp.next = heroNode;
		heroNode.pre = temp;
	}

	//  Modify the content of a node ,  You can see that the node content modification of a two-way linked list is the same as that of a one-way linked list 
	//  It's just   Change the node type to  HeroNode2
	public void update(HeroNode2 newHeroNode) {
    
		//  Judge whether it is empty 
		if (head.next == null) {
    
			System.out.println(" Linked list is empty. ~");
			return;
		}
		//  Find the node that needs to be modified ,  according to no Number 
		//  Define an auxiliary variable 
		HeroNode2 temp = head.next;
		boolean flag = false; //  Indicates whether the node is found 
		while (true) {
    
			if (temp == null) {
    
				break; //  We've finished traversing the linked list 
			}
			if (temp.no == newHeroNode.no) {
    
				//  find 
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//  according to flag  Determine whether to find the node to be modified 
		if (flag) {
    
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
     //  Can't find 
			System.out.printf(" Can't find   Number  %d  The node of , Do not modify \n", newHeroNode.no);
		}
	}

	//  Remove a node from a two-way list ,
	//  explain 
	// 1  For a two-way linked list , We can find the node to delete directly 
	// 2  After finding , Just delete yourself 
	public void del(int no) {
    

		//  Determine whether the current list is empty 
		if (head.next == null) {
    //  Empty list 
			System.out.println(" Linked list is empty. , Cannot delete ");
			return;
		}

		HeroNode2 temp = head.next; //  Auxiliary variable ( The pointer )
		boolean flag = false; //  Flag whether the node to be deleted is found 
		while (true) {
    
			if (temp == null) {
     //  At the end of the list 
				break;
			}
			if (temp.no == no) {
    
				//  The previous node found to be deleted temp
				flag = true;
				break;
			}
			temp = temp.next; // temp Move backward , Traverse 
		}
		//  Judge flag
		if (flag) {
     //  find 
			//  You can delete 
			// temp.next = temp.next.next;[ One way linked list ]
			temp.pre.next = temp.next;
			// This judgment ： If it's the last node , There is no need to execute the following sentence , Otherwise, a null pointer appears 
			if (temp.next != null) {
    
				temp.next.pre = temp.pre;
			}
		} else {
    
			System.out.printf(" To delete  %d  Node does not exist \n", no);
		}
	}

}

//  Definition HeroNode2 ,  Every HeroNode  Object is a node 
class HeroNode2 {
    
	public int no;
	public String name;
	public String nickname;
	public HeroNode2 next; //  Point to next node ,  The default is null
	public HeroNode2 pre; //  Point to previous node ,  The default is null
	//  Constructors 

	public HeroNode2(int no, String name, String nickname) {
    
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	//  In order to show the method , Let's do it again toString
	@Override
	public String toString() {
    
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}

}

Circular list

Josephu problem

Set the number to 1,2,… n Of n I'll sit around , The contract number is k（1<=k<=n） People from 1 Start counting , Count to m The man of , It's next from 1 Start counting , Count to m And the man of , By analogy , Until everyone is on the line , This produces a sequence of queue numbers .

• n = 5 , That is to say 5 personal
• k = 1, Count from the first person
• m = 2, Count 2 Next

The illustration

Code

Notes have ideas to explain ~

package com.atguigu.linkedlist;

//author qij
public class Josepfu {
    

	public static void main(String[] args) {
    
		// Test to see how to build a circular list , And traversal whether ok
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);//  Join in 5 A child node 
		circleSingleLinkedList.showBoy();

		// Out of circle 
		circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
	}

}

//  Create a circular one-way list 
class CircleSingleLinkedList {
    
	//  Create a first node , There is currently no number 
	private Boy first = null;

	//  Add child nodes , Build a circular list 
	public void addBoy(int nums) {
    
		// nums  Do a data check 
		if (nums < 1) {
    
			System.out.println("nums The value of is not correct ");
			return;
		}
		Boy curBoy = null; //  Auxiliary pointer , Help build a circular list 
		//  Use for To create our circular list 
		for (int i = 1; i <= nums; i++) {
    
			//  According to the number , Create child nodes 
			Boy boy = new Boy(i);
			//  If it's the first child 
			if (i == 1) {
    
				first = boy;
				first.setNext(first); //  To form a ring 
				curBoy = first; //  Give Way curBoy Point to the first child 
			} else {
    
				curBoy.setNext(boy);//
				boy.setNext(first);//
				curBoy = boy;
			}
		}
	}

	//  Traverse the current circular list 
	public void showBoy() {
    
		//  Judge whether the list is empty 
		if (first == null) {
    
			System.out.println(" No kids ~~");
			return;
		}
		//  because first Don't move , So we still use a helper pointer to do the traversal 
		Boy curBoy = first;
		while (true) {
    
			System.out.printf(" The child's number  %d \n", curBoy.getNo());
			if (curBoy.getNext() == first) {
    //  The description has been traversed 
				break;
			}
			curBoy = curBoy.getNext(); // curBoy Move backward 
		}
	}

	//  According to the user's input , Work out the order in which the children come out of the circle 
	/** * * @param startNo *  Count from the first few children  * @param countNum *  A few times  * @param nums *  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(" Wrong parameter input ,  Please re-enter ");
			return;
		}

		//  Create to give auxiliary pointer helper, Help the children out of the circle 
		Boy helper = first;
		//  You should point to the last node of the ring list in advance 
		while (true) {
    
			if (helper.getNext() == first) {
     //  explain helper Point to the last child node 
				break;
			}
			helper = helper.getNext();
		}

		// Before the children count off , First, let  first  and  helper  Move  k - 1 Time 
		for(int j = 0; j < startNo - 1; j++) {
    
			first = first.getNext();
			helper = helper.getNext();
		}

		// When the child counts off , Give Way first  and  helper  The pointer is at the same time   The movement of the  m - 1  Time ,  And then out in circles 
		while(true) {
    
			if(helper == first) {
     // There is only one node in the description circle 
				break;
			}
			// Give Way  first  and  helper  The pointer is at the same time   The movement of the  countNum - 1
			for(int j = 0; j < countNum - 1; j++) {
    
				first = first.getNext();
				helper = helper.getNext();
			}
			// At this time first Node to , Is the child node to be out of the circle 
			System.out.printf(" The child %d Out of circle \n", first.getNo());
			// This will be first Point to the child node out of the circle 
			first = first.getNext();
			helper.setNext(first);
		}

		System.out.printf(" The last child left in the circle is numbered %d \n", first.getNo());
		
	}
}

//  Create a Boy class , Represents a node 
class Boy {
    
	private int no;//  Number 
	private Boy next; //  Point to next node , Default null

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

}