Preface:

Singly linked lists are a common and important data structure. Over time, many algorithms have been developed for singly linked lists, such as the inversion of singly linked lists, which will be discussed in this article today.

The following will explain the data structure of the single linked list in detail with some pictures, and reverse the single linked list in three ways (recursion, double pointer method and loop traversal).

Data structure:

1. Single linked list data structure:

A singly linked list is a linear structure consisting of nodes. And each Node is composed of a data field and a pointer field.

① The structure diagram of Node is as follows:

  1. Data domain of a node: Data A data domain is generally used to store data. (Note: the data field needs to specify the type, can only store the specified type of data, can not put everything, isn’t it? So how does that work in the code? Use generics.
  2. The pointer field of a node: The next pointer field is generally a pointer to the next node; This pointer is actually a memory address, because the Node object is stored in the JVM’s heap memory, so the Node’s next pointer field is stored in the heap memory address of the next Node. In code, the memory address of an object is assigned to its reference variable, so the pointer field stores the reference variable of the next node object.

② the structure diagram of single linked list is as follows :(the following figure is a single linked list composed of three nodes)

Thoughtful, en en en…… as if the single-linked list of knowledge in my mind some clear ah; Why don’t we hurry up and get the data structure code out of the single-linked list, and then figure out how to reverse it, en en en….. Heh heh!

Code:

1, Node Node class:

Create a Node class and provide two additional methods (single linked list creation method, single linked list traversal play);

CreateLinkedList (); createLinkedList();

Extension: The insertion method of linked list nodes is also used in HashMap. In JDK 1.7, the insertion method was header and in JDK 1.8, the insertion method was tail.

/ * * *@PACKAGE_NAME: com.lyl.linklist
 * @ClassName: Node Node class *@Description: Single linked list elements: Node *@Date: the 2020-05-30 slaves * * /
public class Node<T> {
    // The data field of the node
    public T data;
    // The pointer field of the node
    public Node next;

    /** * constructor *@paramData Indicates the data field value */
    public Node(T data) {
        this.data = data;
    }
    
    
     /** * create a single linked list *@returnReturn the header */
    public static Node createLinkedList(a){
        / / head node
        Node<String> head;

        Node<String> n = new Node<String>("111");
        Node<String> n1 = new Node<String>("222");
        Node<String> n2 = new Node<String>("333");
        // Specify a header node
        head = n;
        n.next = n1;
        n1.next = n2;
        // return the header
        return head;
    }
    
    
    /** * list traversal *@param node
     */
    public static void traverse(Node node) {
        while(node ! =null) {
            System.out.print(node.data + "-- >");
            node = node.next;
        }
        System.out.print("null"); System.out.println(); }}Copy the code

2. Single linked list inversion:

① Inversion of recursion:
/ * * *@PACKAGE_NAME: com.lyl.linklist
 * @ClassName: ReverseByRecursiveTest
 * @Description: Single-linked list inversion using recursion *@Date: the 2020-05-30 17:01 * * /
public class ReverseByRecursiveTest {

    /** * Use recursion for single-linked list inversion *@paramHead The head node * of the linked list@returnReturn the inverted head */
    public static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        // Get the next node of the head node, stored as temp temporary node
        Node temp = head.next;
        // recursive call
        Node node = reverse(head.next);
        // Set the pointer field of the next node of the head node to the head node
        temp.next = head;
        // Set the pointer field of the head node to NULL
        head.next = null;
        return node;
    }

    // test
    public static void main(String[] args) {
        // Create a single linked list
        Node head = Node.createLinkedList();
        // Iterate over the newly created singly linked list
        System.out.print("Newly created single linked list:");
        Node.traverse(head);
        // Recursively invert a single linked list
        Node newHead = reverse(head);
        // Iterate over the inverted single linked list
        System.out.print("Single-linked list reversed:"); Node.traverse(newHead); }}Copy the code

Run output:

Newly created single-linked list: 111 –> 222 –> 333 –> NULL Reversed single-linked list: 333 –> 222 –> 111 –> NULL

Diagram how recursive methods are called:

(1) First pass the header node (data field is 111 nodes) into the reverse() method and push the method onto the stack:

Node = reverse(head.next); Pass a node with a data field of 222 into the reverse() method and push the method onto the stack:

Node = reverse(head.next); Pass nodes with data field 333 into the reverse() method and push the method onto the stack; If next pointer field of data domain 333 points to next node null, then return current head (data domain 333) :

(4) When reverse(333); When the method goes off the stack, reverse(222) continues; The code that follows the recursive call continues, and when it’s done, the reverse(222) method exits the stack:

(5) When reverse(222); When the method goes off the stack, reverse(111) continues; The code that follows the recursive call continues, and when it’s done, the reverse(111) method exits the stack:

(6) When the reverse(111) ** method is off the stack, then the recursive call ends **, and the structure of the single linked list in the heap is shown in the figure:

The recursive call is finally done, the graph is too laborious, it takes too much time; The tool to draw the picture is: ProcessOn.

(2) Loop traversal + auxiliary space inversion:
/ * * *@PACKAGE_NAME: com.lyl.linklist
 * @ClassName: ReverseByTraverseTest
 * @Description: Single-linked list inversion using loop traversal + secondary space *@Date: the 2020-05-30 19:11 * * /
public class ReverseByTraverseTest {

    /** * Use traversal + secondary space for list inversion *@param head
     * @returnReturn the inverted head */
    public static Node reverse(Node head) {
        // list collection auxiliary space
        List<Node> list = new ArrayList<Node>();

        while(head ! =null) {
            list.add(head);
            head = head.next;
        }

        for (int i = list.size() - 1; i > 0; i--) {
            Node n = list.get(i);
            Node n1 = list.get(i-1);
            n.next = n1;
            n1.next = null;
        }
        // return the header
        return list.get(list.size() - 1);
    }


    // test
    public static void main(String[] args) {
        // Create a single linked list
        Node head = Node.createLinkedList();
        // Iterate over the newly created singly linked list
        System.out.print("Newly created single linked list:");
        Node.traverse(head);
        // Recursively invert a single linked list
        Node newHead = reverse(head);
        // Iterate over the inverted single linked list
        System.out.print("Single-linked list reversed:"); Node.traverse(newHead); }}Copy the code
Double pointer + auxiliary temporary node to reverse:
/ * * *@PACKAGE_NAME: com.lyl.linklist
 * @ClassName: ReverseByDoublePointerTest
 * @Description: Single-linked list inversion using double Pointers + auxiliary temporary nodes *@Date: 2020-05-30 * * / michal
public class ReverseByDoublePointerTest {

    /** * Use double Pointers + auxiliary temporary nodes for list inversion *@param head
     * @returnReturn the inverted head */
    public static Node reverse(Node head) {
        // The current node pointer
        Node current ;
        // The pointer to the previous node
        Node previous;
        // The current node pointer is initialized to point to the header
        current = head;
        // The previous node pointer is initialized to null
        previous = null;

        while(current ! =null) {// Secondary temporary node that stores the next node of the current node
            Node temp = current.next;
            // The next node of the current node points to the node pointed to by the previous node pointer
            current.next = previous;
            // Then move the previous node pointer forward one node, so that both the current node pointer and the previous node pointer point to the current node
            previous = current;
            // The pointer to the current node also moves forward one node, that is, to the next node of the current node, which is the node to which the temporary node points
            current = temp;
        }
        // return the header
        return previous;
    }


    // test
    public static void main(String[] args) {
        // Create a single linked list
        Node head = Node.createLinkedList();
        // Iterate over the newly created singly linked list
        System.out.print("Newly created single linked list:");
        Node.traverse(head);
        // Recursively invert a single linked list
        Node newHead = reverse(head);
        // Iterate over the inverted single linked list
        System.out.print("Single-linked list reversed:"); Node.traverse(newHead); }}Copy the code

This article focuses on the call process of recursion, because recursion is generally not very well understood.

Don’t forget to leave your learning footprints

All see the article not praise are “play rascal”, hey hey ヾ(◍°∇°◍) Blue! Just as a joke, move your little hands and click “like”, each of you will make more learners join in with a contribution (like + comment)! Thank you very much! ￣ ￣ omega =