1. Overview of single linked list

1. The linked list is stored in the way of nodes, it is chain storage.
2. Each node contains a data domain, next domain: point to the next node.
3. The nodes of the linked list are not necessarily consecutive storage
4. The linked list with sub-header nodes and the linked list without header nodes are determined according to the actual needs.

2. Application case of single linked list

Implementing one-way list with head-lead - - the management of hero ranking of the three countries completes the operation of adding, deleting and modifying Heroes

Node code:

package com.xuwei.linkedList;

// Define node classes
public class HeroNode {
    public int no; // Hero Number
    public String name; // Hero name
    public String nickname; // Heroic nickname
    public HeroNode next; // Point to the next node

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

 

Hero Code:

package com.xuwei.linkedList;

import java.util.Stack;

// Define a single list to manage our heroes
public class SingleLinkedList {
    // Initialize the header node, the header node does not move, does not store specific data
    private HeroNode head = new HeroNode(0, "", "");

    // Add nodes to single linked list
    public void add(HeroNode heroNode) {
        // The head node does not move and requires an auxiliary variable temp
        HeroNode temp = head;
        // Traverse the list, judge the special situation, the current list is empty, you can
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        // Loop exit means finding the last node
        temp.next = heroNode;

    }

    // Insert heroes into designated positions according to ranking
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false; // Does the number added to the flag flag flag exist?
        // Find the first hero position to insert
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {
                // Location Finding
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("This number%d It already exists.,", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // Modify the node's information according to the number
    public void update(HeroNode heroNode) {
        // Judge whether it is empty
        if (head.next == null) {
            System.out.println("The list is empty.");
            return;
        }
        // Find the node to modify
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        }
    }

    // Delete Nodes
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("To delete%d Node does not exist", no);
        }
    }

    // Display linked list
    public void list() {
        HeroNode temp = head.next;
        if (head.next == null) {
            System.out.println("The list is empty...");
            return;
        }
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    // 1. Finding the Number of Valid Nodes in a Single Link List
    public int getLength() {
        if (head.next == null) {
            return 0;
        }
        HeroNode temp = head.next;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    // 2. Finding the reciprocal k-th node in a single linked list
    public HeroNode findLastIndexNode(int k) {
        //The reciprocal k node is the positive getlength()-k node.
        if (head.next == null) {
            return null;
        }
        //Get the length of the linked list
        int size = getLength();
        //Traverse to get the k-th node, before doing a check
        if (k <= 0 || k > size) {
            return null;
        }
        //Define auxiliary variables, for loop to reciprocal k
        HeroNode temp = head.next;
        for (int i = 0;i < size - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

    // 3. Inversion of single linked list
    public void reverseList() {
        //Idea: Every time you add a list, you add it to the header to reverse it.
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode cur = head.next;
        HeroNode next = null; //Point to the next node of the current node
        HeroNode reverseHead = new HeroNode(0, "","");
        //Traveling through the original list, each time a node is traversed, it is taken out and placed at the front of the new list.
        while (cur != null) {
            //Get the next node of the current node first
            next = cur.next;
            //Point cur's next node to the front end of the new list
            cur.next = reverseHead.next;
            //Connect cur to the new list
            reverseHead.next = cur;
            //Let cur move back
            cur = next;

        }
        //Turn head.next to reverseHead.next to achieve inversion
        head.next = reverseHead.next;
    }

    // 4. Print a single list from beginning to end
    public void reversePrint() {
        if (head.next == null) {
            return;
        }
        //Create a stack to push each node onto the stack
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        //Press all nodes of the linked list onto the stack
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //Print the nodes in the stack, pop out of the stack
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
    
    // Test code
    public static void main(String[] args) {
        //Create nodes first
        HeroNode hero1 = new HeroNode(1, "Cao Cao", "Mengde");
        HeroNode hero2 = new HeroNode(2, "Liu Bei", "Xuande");
        HeroNode hero3 = new HeroNode(3, "king of Wu in the Three Kingdoms Era", "Word Zhongmou");
        HeroNode hero4 = new HeroNode(4, "Sun Ce", "Primitive Characters");
        //Create a list to be linked to
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //Add in numbered order
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);

        //Display linked list
        singleLinkedList.list();

        //Test the code of the modified node
        HeroNode newHeroNode = new HeroNode(2,"Liu Bei","Xuande Degong");
        singleLinkedList.update(newHeroNode);

        System.out.println("After modification of the linked list situation,,,,,,,,,,,");
        singleLinkedList.list();

        //Delete a node
        singleLinkedList.del(1);

        System.out.println("Deleted linked list,,,,,,,,,,,,,,,,,,,,,");
        singleLinkedList.list();

    }

}

3. Bidirectional linked list

class DoubleLinkedList {
    //Initialize a header node first. The header node does not move and does not store specific data.
    private HeroNode2 head = new HeroNode2(0,"","");

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

    //Display linked list
    public void list() {
        //Judging that the list is empty
        if (head.next == null) {
            System.out.println("The list is empty");
            return;
        }
        HeroNode2 temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //Output node information
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //Add nodes to one-way linked list
    public void add(HeroNode2 heroNode) {
        //head node does not move, requiring an auxiliary traversal temp
        HeroNode2 temp = head;
        //Go through the list and find the last
        while (true) {
            //Find the end of the list
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //Form a bi-directional list
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //Inserting heroes into designated positions according to ranking,,,,,,,,,,.
    public void addByOrder(HeroNode2 heroNode) {
        HeroNode2 temp = head;
        boolean flag = false; //Does the number added by the false flag exist?
        //We need to find the previous position of the designated position, that is, the hero number of the designated position is less than that of the hero.
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {
                //Location found, insert behind temp
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true; //Explain the number exists
            }
            temp = temp.next;
        }
        //Judging the value of flag
        if (flag) {
            System.out.printf("Prepare to add hero number%d It already exists and can't join.", heroNode.no);
        } else {
            //Insert it into the list, behind temp
            temp.next.pre = heroNode;
            heroNode.next = temp.next;
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    }

    //Modify node information according to no number
    public void update(HeroNode heroNode) {
        //Judge whether it is empty
        if (head.next == null) {
            System.out.println("The list is empty~");
            return;
        }
        //Find the node that needs to be modified
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = temp.nickname;
        } else {
            System.out.printf("No number found%d Nodes that cannot be modified\n",heroNode.no);
        }
    }

    //Delete Nodes
    public void del(int no) {
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.no == no) {
                //Find the node to delete
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("To delete %d Node does not exist\n", no);
        }
    }

4. One-way circular list

public class Demo04CircleSingleLinkedList {
    public static void main(String[] args) {
        // Test one to see if it's ok ay to build a ring list and traverse it
         CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
         circleSingleLinkedList.addBoy(125);// Join 5 child nodes
         circleSingleLinkedList.showBoy();

         //Test whether a child is out of circle correctly
         circleSingleLinkedList.countBoy(10, 3, 125); 
    }
}

// Create a ring-shaped one-way list
class CircleSingleLinkedList {
    // Create a first node, which is not currently numbered
    private Boy first = null;

    // Add child nodes and build a ring list
    public void addBoy(int nums) {
        // nums does a data validation
        if (nums < 1) {
            System.out.println("nums The value is incorrect.");
            return;
        }
        // Auxiliary pointer to help build ring list
        Boy curBoy = null;
        // Use for to create our ring list
        for (int i = 1; i <= nums; i++) {
            // Create a child node based on the number
            Boy boy = new Boy(i);
            // If it's the first child
            if (i == 1) {
                first = boy;
                first.setNext(first); // Constitutive Ring
                curBoy = first;
            } else {
                // Equivalent to the current node pointing to the next node - > curBoy. next = boy
                curBoy.setNext(boy);
                // The next node points to the first node - > boy. next = first
                boy.setNext(first);
                // Equivalent to curBoy = boy
                curBoy = boy;
            }
        }
    }

    // Traversing through the current ring list
    public void showBoy() {
        // Judging whether the list is empty
        if (first == null) {
            System.out.println("No children");
            return;
        }
        // first can't move. You need to use an auxiliary pointer to complete the traversal.
        Boy curBoy = first;
        while (true) {
            System.out.printf("Number of the child %d\n", curBoy.getNo());
            if (curBoy.getNext() == first) {// The instructions have been traversed.
                break;
            }
            curBoy = curBoy.getNext(); // curBoy moved back
        }

    }

    /**
     * According to the user's input, calculate the order of children out of the circle
     * @param startNo Represents counting from the first child.
     * @param countNum Represent several times
     * @param nums Indicates how many children were in the circle in the first place.
     */
    public void countBoy(int startNo, int countNum, int nums) {
        // Check the data first
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("The parameter input is incorrect.");
            return;
        }
        // Create an auxiliary pointer to help children out of the circle
        Boy helper = first;
        // The requirement is to create an auxiliary pointer helper, which should be pointed to the last node of the ring list beforehand.
        while (true) {
            if (helper.getNext() == first) {
                // Explain that the helper points to the last child node
                break;
            }
            helper = helper.getNext();
        }
        // Let first and helper move k-1 before the child counts, so that they move to the target mobile child.
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        // When the child counts, let the first and helper pointers move m-1 times at the same time, and then go out of the loop.
        while (true) {
            if (helper == first) {// There is only one node in the description circle.
                break;
            }
            // Let the first and helper pointers move coutnNum-1 at the same time
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            // At this point, the first point is the child node to go out of the circle.
            System.out.printf("Child %d Out of Circle\n", first.getNo());
            // At this point the firt points to the child node out of the loop
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("The last child to remain in the circle is numbered as ___________%d\n", first.getNo());
    }

}

// Create a Boy class to represent a node
class Boy {
    private int no; // number
    private Boy next; // Point to the next node, default to 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;
    }
}