Complete effect: add, delete, change single linked list

What is a linked list

A singly linked list is a chain-access data structure that uses a set of arbitrarily addressed storage cells to store data elements in a linear list. The data in the linked list is represented by nodes, and each node is composed of elements (image of data elements) + Pointers (indicating the storage location of subsequent elements). Elements are the storage units for storing data, and Pointers are the address data connected to each node.

Baidu encyclopedia

Features: Not continuous in memory, slow search (search from the beginning) add and delete elements fast

Illustration:

HeroNode class analysis

// Each HeroNode is a node
public class HeroNode {
    public int id;
    public String name;
    public String nickName;

    // point to the next node
    public HeroNode next;

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

    @Override
    public String toString(a) {
        return "HeroNode{" +
                "no=" + id +
                ", name='" + name + '\' ' +
                ", nickName='" + nickName + '\' ' +
                '} '; }}Copy the code

This class is easy to understand as a singly linked list bean class

The most important of these are the ID and next parameters, and the rest are HeroNode parameters

Add elements

public class SingleLinkedList {
     // this header does not store data
    public HeroNode head = new HeroNode(0.""."");


    // Add a node
    public void add(HeroNode heroNode) {

        // The header cannot be moved, so a temporary variable is used to hold it
        HeroNode temp = head;

        // When temp. Next always! =null, indicating not the last element
        // If temp. Next == null then the while automatically ends and executes the following code
        while(temp.next ! =null) {
            / / ward temp
            temp = temp.next;
        }

        // When exiting while,temp points to the last position in the list
        // Then point temp.next to the new element
        temp.next = heroNode;
    }
    
    
     // Display all data in the linked list
    public void show(a) {
        if (head.next == null) {
            System.out.println("Linked list is empty");
            return;
        }

        // The header cannot move
        HeroNode temp = head.next;

        / / if the temp! =null indicates that this is not the last loop
        while(temp ! =null) {
            System.out.println(temp);

            // Move temp aftertemp = temp.next; }}}Copy the code

Use:

linkedList.add(new HeroNode(1."Sung river"."Timely rain"));
linkedList.add(new HeroNode(5."Qin Ming"."Thunderfire"));
linkedList.add(new HeroNode(6."Wood into"."Little cyclone"));
linkedList.add(new HeroNode(3."吴用"."Resourceful"));
linkedList.add(new HeroNode(2."李逵".Black Tornado));
linkedList.add(new HeroNode(4."Lin"."Leopard head"));

System.out.println("Normal add ~");
linkedList.show();
Copy the code

The running results are as follows:

HeroNode{no=1, name=' booty '} HeroNode{no=1, name=' booty '} HeroNode{no=1, name=' booty '} NickName = 'small whirlwind'} HeroNode {no = 3, name = 'with wu, nickName =' ass '} HeroNode {no = 2, name = 'li', nickName = 'black whirlwind'}Copy the code

Analysis: In the single list, the core is the following code:

(Add, delete, modify are all iterated with while)

// When temp. Next always! =null, indicating not the last element
// If temp. Next == null then the while automatically ends and executes the following code
while(temp.next ! =null) {
       / / ward temp
       temp = temp.next;
}
Copy the code

In a singly linked list, the element is added from the very end, so we need while to the last position, next == null for the last position, so when the while loop ends, that’s the position of the last element.

Illustration:

Increments elements by ID from small to large

Code first, then analysis:

    /** * Add nodes to sort by ID */
    public void addID(HeroNode heroNode) {

        // The header cannot be moved, so a temporary variable is used to traverse
        HeroNode temp = head;

        // Whether the heroNode number saved exists
        boolean flag = false;

        //temp.next ! = null keeps the loop going
        while(temp.next ! =null) {
            // Current node > incoming node
            if (temp.next.id > heroNode.id) {
                /* * If temp. Next = 6 * heronode. no = 3 * * then heronode. no should be added between temp and temp.next */
                break;
            } else if (temp.next.id == heroNode.id) {
                // The added number exists
                flag = true;
                break;
            }
            / / temp
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("%d already exists with the name :%s\n", heroNode.id, heroNode.name);
            return;
        }
        // Join the list when exiting the while
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
Copy the code

Use:

        linkedList.addID(new HeroNode(1."Sung river"."Timely rain"));
        linkedList.addID(new HeroNode(5."Qin Ming"."Thunderfire"));
        linkedList.addID(new HeroNode(5."Qin Ming"."Thunderfire"));
        linkedList.addID(new HeroNode(6."Wood into"."Little cyclone"));
        linkedList.addID(new HeroNode(3."吴用"."Resourceful"));
        linkedList.addID(new HeroNode(2."李逵".Black Tornado));
        linkedList.addID(new HeroNode(4."Lin"."Leopard head"));

        System.out.println("Add ~ by ID");
        linkedList.show();
Copy the code

The running results are as follows:

5The ID already exists and the name is: Qin Ming Add ~ HeroNode{no= according to the ID1, name='sung river', nickName='Timely rain'}
HeroNode{no=2, name='李逵', nickName=Black Cyclone}
HeroNode{no=3, name='with wu', nickName=Resourcefulness}
HeroNode{no=4, name='Lin', nickName='Leopard head'}
HeroNode{no=5, name='qin Ming', nickName='Thunderfire'}
HeroNode{no=6, name='wood into', nickName='Little cyclone'}
Copy the code

There are two cases of sorting by ID:

• Current ID exists (cannot be added)
• Current ID does not exist, increment to appropriate location

Given that the current singly linked list element id is (1,4,7,9,11) and the newly added element id is 5, 5 should be increased between 4 and 7

Illustration:

This part is not easy to understand, if you don’t understand, watch the video

Let’s explain the two sentences of assignment:

// Join the list when exiting the while
heroNode.next = temp.next;
temp.next = heroNode;
Copy the code

Illustration:

Modify the element

/* * Change the id based on the id */
    public void upData(HeroNode heroNode) {

        HeroNode temp = head;

        //false: cannot be changed without the same ID
        boolean flag = false;

        // If not null, loop through
        while(temp.next ! =null) {
            if (temp.id == heroNode.id) {
                // If temp. Id == heronode.id then it can be changed
                flag = true;
                break;
            }
            Mobile after / / temp
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        } else {
            System.out.printf("Hero with id :%d and name :%s cannot be changed \n", heroNode.id, heroNode.name); }}Copy the code

Use:

        linkedList.addID(new HeroNode(1."Sung river"."Timely rain"));
        linkedList.addID(new HeroNode(5."Qin Ming"."Thunderfire"));
        linkedList.addID(new HeroNode(6."Wood into"."Little cyclone"));
        linkedList.addID(new HeroNode(3."吴用"."Resourceful"));
        linkedList.addID(new HeroNode(2."李逵".Black Tornado));

        // Test the same id
        linkedList.addID(new HeroNode(1."李逵".Black Tornado));

        // Test different ids
        linkedList.upData(new HeroNode(8."李逵".Black Tornado));

        System.out.println("Modify number ~");
        linkedList.show();
Copy the code

The running results are as follows:

1No. : Li Kui No. :8The hero whose name is li Kui cannot be changed ~ HeroNode{no=1, name='sung river', nickName='Timely rain'}
HeroNode{no=2, name='李逵', nickName=Black Cyclone}
HeroNode{no=3, name='with wu', nickName=Resourcefulness}
HeroNode{no=5, name='qin Ming', nickName='Thunderfire'}
HeroNode{no=6, name='wood into', nickName='Little cyclone'}
Copy the code

Analysis: An element can be modified only if it exists in the linked list

• Determines whether the same element exists in the current linked list based on the ID

  • If yes, you can modify it
  • If they are different, they cannot be modified

• The values that need to be modified are passed in the method

• When modifying an element, find the location of the element and then modify it

Illustration:

Remove elements

Delete element code:

    /** ** delete */ according to the number
    public void remove(int removeId) {

        HeroNode temp = head;

        //true indicates a number that can be deleted
        boolean flag = false;
        while(temp.next ! =null) {

            // Deleting elements is touched by the next value
            // If the next id is the same as the id passed in, delete it
            if (temp.next.id == removeId) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        //true has the same ID and can be deleted
        if (flag) {
            // Go straight to the next element.
            temp.next =  temp.next.next;
        }else{
            System.out.printf("Hero with id :%d does not exist, cannot be deleted \n",removeId); }}Copy the code

Use:

// Delete a node
    private static void initRemove(SingleLinkedList linkedList) {
        linkedList.addID(new HeroNode(1."Sung river"."Timely rain"));
        linkedList.addID(new HeroNode(5."Qin Ming"."Thunderfire"));
        linkedList.addID(new HeroNode(6."Wood into"."Little cyclone"));
        linkedList.addID(new HeroNode(3."吴用"."Resourceful"));
        linkedList.addID(new HeroNode(2."李逵".Black Tornado));

        linkedList.remove(1);
        linkedList.remove(2);
        linkedList.remove(3);
        linkedList.remove(4);
        linkedList.remove(5);
        System.out.println("Delete node ~");
        linkedList.show();
    }
Copy the code

The running results are as follows:

Numbers for:4, hero does not exist, cannot delete delete node ~ HeroNode{no=6, name='wood into', nickName='Little cyclone'}
Copy the code

If you want to delete an element, you need to locate the deleted location according to its ID, and then point the current location to the next location

If you want to delete element 2, you just want next with id = 1 to point to id = 3 (hero.next = hero.next-next).

The complete code

What do you like?

Data structures and algorithms directory

Blogger page

Original is not easy, your praise plus is the biggest support for me!