Introduction to the

LinkedList should be a very, very simple data structure. The nodes are linked one by one to create a linkedList. Today we’ll use animation to see how linkedList is inserted and deleted.

The construction of a linkedList

LinkedList is made up of nodes one by one. Each node only needs to store the data to be saved and a reference to the next node.

LinkedList itself requires a head node, so our linkedList can be constructed like this:

public class LinkedList {

    Node head; / / the head node

    //Node represents nodes in the Linked List and contains a data and a reference to the next Node
    class Node {
        int data;
        Node next;
        //Node's constructor
        Node(intd) { data = d; }}}Copy the code

The operation of the linkedList

Let’s look at how linkedList inserts data. There are three ways to insert data: header insert, tail insert, and middle insert.

Insert the head

Let’s start with an example of header insertion:

What is the logic of header insertion?

The newly inserted node serves as the head node and then points the original head node to the next reference of the current head node.

    // Insert into the header of the linkedList
    public void push(int newData) {
        // Build the node to insert
        Node newNode = new Node(newData);
        // Next of the new node points to the current head node
        newNode.next = head;
        // The existing head node points to the new node
        head = newNode;
    }
Copy the code

Insert the tail

Look again at the tail insertion example:

What is the logic of insertion?

Find the last node, and point next of the last node to the newly inserted node.

// Insert the new node at the end of the list
    public void append(int newData) {
        // Create a node
        Node newNode = new Node(newData);
        // If the list is empty, the new node is the head node
        if (head == null) {
            head = newNode;
            return;
        }

        newNode.next = null;
        // Find the last node
        Node last = head;
        while(last.next ! =null) {
            last = last.next;
        }
        / / insert
        last.next = newNode;
        return;
    }
Copy the code

The middle insert

Look again at the example of middle insertion:

In this example, we insert a 93 at the third node.

The insertion logic is to find the second node, point next of the second node to the new node, and then point next of the new node to the original third node.

Take a look at how the Java code works:

// Insert after which element
    public void insertAfter(int index, int newData) {
        Node prevNode = head;
        for (int i = 1; i < index; i++) {
            if (prevNode == null) {
                System.out.println("Wrong index entered, please re-enter");
                return;
            }
            prevNode = prevNode.next;
        }
        // Create new nodes
        Node newNode = new Node(newData);
        // Next of the new node points to the next prevNode node
        newNode.next = prevNode.next;
        // Insert the new node after prevNode
        prevNode.next = newNode;
    }
Copy the code

Remove nodes

Let’s look at how to delete a node at a location:

In the example above, we want to delete the fifth node.

The logic for deletion is to find the fourth and sixth nodes. Then point the next of the fourth node to the sixth node.

Take a look at the corresponding Java code:

    // Delete the node at a specific location
    void deleteNode(int index)
    {
        // If it is empty, return it directly
        if (head == null)
            return;

        / / the head node
        Node temp = head;

        // Delete the head node
        if (index == 1)
        {
            head = temp.next;
            return;
        }

        // Find the previous node to delete the node
        for (int i=1; temp! =null && i<index-1; i++)
            temp = temp.next;

        // If out of range
        if (temp == null || temp.next == null)
            return;

        // temp->next specifies the node to be deleted
        Node next = temp.next.next;
        temp.next = next;
    }
Copy the code

The code address of this article:

learn-algorithm

This paper included in www.flydean.com/algorithm-l…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!