Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Introduction to the

Today we’re going to look at a slightly more complicated LinkedList: doublyLinkedList.

In contrast to LinkedList, nodes in doublyLinkedList have a node before a prev, in addition to next pointing to the next node. So it’s called doublyLinkedList. DoublyLinkedList is a two-way list that we can traverse forward or backward through the list.

Today we are going to look at the basic operations and concepts of doublyLinkedList.

The construction of doublyLinkedList

Like linkedList, doublyLinkedList is made up of nodes one by one. In addition to storing the data to be saved, each node also needs to store the next node and references to the previous node.

DoublyLinkedList requires a head node. Let’s look at how to build it:

public class DoublyLinkedList {

    Node head; / / the head node

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

The operation of the doublyLinkedList

Next, let’s look at some basic operations for doublyLinkedList.

Insert the head

The logic for head insertion is to make the newly inserted node the new head node and point newNode.next to the original head node.

You also need to point head.prev to the new insertion node.

Take a look at the Java code:

    // 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
        // The prev of the new node points to null
        newNode.next = head;
        newNode.prev = null;

        if(head ! =null)
            head.prev = newNode;

        // The existing head node points to the new node
        head = newNode;
    }
Copy the code

Insert the tail

The tail-insert logic is to find the last node, point next of the last node to the newly inserted node, and point prev of the newly inserted node to the last 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) {
            newNode.prev = 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;
        newNode.prev = last;
        return;
    }
Copy the code

Insert the given position

If we want to insert a node at a given location, we need to find the previous node at the insertion location, and then point next of the previous node to the new node. The prev of the new node points to the previous node.

We also need to point the next of the new node to the next node and the prev of the next node to the new node.

    // 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;
        // Point the prev of the new node to prevNode
        newNode.prev = prevNode;

        // The prev of the next node of newNode points to newNode
        if(newNode.next ! =null)
            newNode.next.prev = newNode;
    }
Copy the code

Deletes a node at the specified location

The logic for removing a node is to find the previous node and the next node to remove the node. The next of the previous node points to the next node, and the prev of the next node points to the previous node.

    // 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;
        Node prev = temp.next.prev;
        prev.prev = prev;
    }
Copy the code

The code address of this article:

learn-algorithm

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

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!