package com.linkedlist;
public class LinkedListDemo {
public static void main(String[] args) {
//test
//Create node first
HeroNode heroNode1 = new HeroNode(1, "Songjiang", "Timely Rain");
HeroNode heroNode2 = new HeroNode(2, "Lu Junyi", "Jade Qilin");
HeroNode heroNode3 = new HeroNode(3, "Wu Yong", "Smart Stars");
HeroNode heroNode4 = new HeroNode(4, "Lin Chong", "Leopard Head");
//Create a linked list
SingleLinkedList singleLinkedList = new SingleLinkedList();
// //join in
// (heroNode1);
// (heroNode2);
// (heroNode3);
// (heroNode4);
//Add in order of number
singleLinkedList.addByOrder(heroNode1);
singleLinkedList.addByOrder(heroNode4);
singleLinkedList.addByOrder(heroNode2);
singleLinkedList.addByOrder(heroNode3);
singleLinkedList.list();
//Test the node modification
HeroNode newHeroNode = new HeroNode(2,"Small Road","Hmph and Ha");
singleLinkedList.update(newHeroNode);
System.out.println("Modified linked list situation");
//show
singleLinkedList.list();
//Delete a node
singleLinkedList.del(1);
System.out.println("Deleted linked list");
singleLinkedList.list();
//Test to find the number of valid single linked list
System.out.println(getLength(singleLinkedList.getHead()));
//The test gets the K-last node
HeroNode res = findLast(singleLinkedList.getHead(),4);
System.out.println(res);
//Test the inversion of single linked list
System.out.println("The original situation of the linked list--");
singleLinkedList.list();
System.out.println("Invert Single Linked List");
reversetList(singleLinkedList.getHead());
singleLinkedList.list();
}
//Method: Get the number of nodes in a single linked list (if it is a linked list with a leading node, you need not count the head nodes)
//head is the head node of the linked list
//The returned number of valid nodes
public static int getLength(HeroNode head){
if (head.next== null){
return 0;
}
int length=0;
//Define a secondary node
HeroNode cur = head.next;
while (cur!=null){
length++;
cur=cur.next;//Travel
}
return length;
}
//Method: Find the K-th until the last node in the single linked list
//The idea is as follows:
//1. Write a method to accept the head node and accept the index at the same time. The index represents the index node to the end.
//2. First, traverse the linked list from beginning to finish to get the total length of the linked list
//3. After getting the size, we start traversing (size-index) from the first of the linked list to get
//4. If it is found, return to the node, otherwise it will return to empty.
public static HeroNode findLast(HeroNode head,int index){
//Judge if the linked list is empty, return null
if (head.next == null){
return null;//Not found
}
//The first traversal gets the length of the linked list
int size = getLength(head);
//The second traversal size-index position is the K-th node we ended with.
//Do an index verification first
if (index <= 0 || index>size){
return null;
}
//Define an auxiliary variable, for loop to locate the countdown indexes
HeroNode cur = head.next;
for (int i=0;i<size-index;i++){
cur=cur.next;
}
return cur;
}
//Reverse the 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 it, just reverse it directly
if (head.next==null || head.next.next==null){
return;
}
//Define an auxiliary pointer to help us traverse the original linked list
HeroNode cur= head.next;
HeroNode next = null;//Point to the next node of the current node;
HeroNode reverseHead = new HeroNode(0,"","");
//Travel the original link table
//Travel from the beginning, each node is traversed and placed at the front end of the new node
while (cur != null){
next = cur.next;//Storely save the next node of the current node, because it will be used later
cur.next= reverseHead.next;//Point the next node of cur to the front end of the new linked list
reverseHead.next=cur;//Link cur to new link list
cur=next;//Let cur move back
}
// Will point to. Implement single linked list inversion
head.next=reverseHead.next;
}
}
//Define a singleLinkedList to manage our heroes
class SingleLinkedList{
//Initialize a head node first, do not move the head node and do not store specific data
private HeroNode head=new HeroNode(0,"","");
//Return to the header node
public HeroNode getHead(){
return head;
}
//Add node to single item 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 variable temp
HeroNode temp=head;
//Travel through the linked list and find the last one
while (true){
//Find the last of the linked list
if (temp.next == null){
break;
}
//If the last is not found, move the 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;
}
// When adding heroes, insert heroes into the specified position according to their ranking;
// 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 need an auxiliary pointer
//Because it is a single linked list, the temp we are looking for is the previous node in the added position, otherwise it will not be added
HeroNode temp = head;
boolean flag = false;//Does the number added by the flag exist? The default is false
while (true){
if (temp.next == null){//Describe temp and at the end of the linked list
break;
}
if (temp.next.no>heroNode.no){//The location is found, insert it after temp
break;
}else if (temp.next.no == heroNode.no){//Instruction The number of added heroNode already exists
flag = true;
break;
}
temp=temp.next;//Move backward, traverse the current linked table
}
//Judge the value of flag
if (flag){//Not added, it means that the number exists
System.out.println(heroNode.no+"The hero number that is ready to be inserted already exists and cannot be added");
}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 number, that is, no cannot be changed
//illustrate:
//1. Change it according to newHeroNode and no
public void update(HeroNode newHeroNode){
//Judge whether it is empty
if (head.next == null){
System.out.println("Link list is empty");
return;
}
//Find the node that needs to be modified and the number is based on the no
//Define an auxiliary variable first
HeroNode temp=head.next;
boolean flag= false;//Indicate whether the node is found
while (true){
if ( temp == null){
break;// And it's finished traversing
}
if (temp.no == newHeroNode.no){
// Found
flag = true;
break;
}
temp=temp.next;
}
//Discern whether to find the node to be modified based on the flag
if (flag){
temp.name= newHeroNode.name;
temp.nickname= newHeroNode.nickname;
}else {//Not found
System.out.printf("No node with number %d is found, cannot be modified\n",newHeroNode.name);
}
}
//Delete node
//Thoughts:
//1. The head node cannot move, so we need the previous node of the temp auxiliary node.
//2. When we compare, we compare with the nodes that need to be deleted.
public void del(int no){
HeroNode temp = head;
boolean flag = false;//Login whether to find the node to be deleted
while (true){
if (temp.next == null){//It has reached the end of the link list
break;
}
if (temp.next.no == no){
//The previous node to be deleted was found
flag = true;
break;
}
temp=temp.next;
}
if (flag = true){//turn up
temp.next=temp.next.next;
}else {
System.out.printf("The %d node to be deleted does not exist\n",no);
}
}
//Show the linked list and traverse
public void list(){
//Judge whether the linked list is empty
if (head.next == null){
System.out.println("Link list is empty");
return;
}
//Because the head node cannot move, we need an auxiliary variable
HeroNode temp=head.next;
while (true){
//Judge whether it is at the end of the linked list
if (temp == null){
break;
}
//Export node information
System.out.println(temp);
//Move temp back
temp=temp.next;
}
}
}
//Define a HeroNode, each HeroNode object is a node
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;
//Constructor
public HeroNode(int no,String name,String nickname){
this.name=name;
this.no=no;
this.nickname=nickname;
}
//To display this method, we rewrite toString
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname+
'}';
}
}
