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).

The data structure

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:

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, not everything.

So how does that work in the code? Use generics.

Pointer field of a node:

The next pointer field is typically a pointer to the next node; This pointer is actually a memory address, because Node objects are stored in the JVM’s heap memory, so the next pointer field of a Node is the address of the next Node in the heap memory.

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 of single linked list is shown 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 a little clearer ah.

Well, let’s get the data structure code out of the single-linked list and figure out how to reverse it.

code

1. Node Node class

Create a Node class. The Node class also provides two additional methods (singlelist creation method, singlelist traversal play).

Note:

CreateLinkedList () createLinkedList();

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

/** * @package_name: com.lyl. Linklist * @className: Node Node class * @description: Single linked list elements: Node Node * @date: 2020-05-30 16:18 **/ public class Node<T> {// Node data domain public T data; Public Node next; Public Node(T data) {this.data = data; / / public Node(T data) {this.data = data; Public static Node createLinkedList(){public static Node createLinkedList(){public static Node createLinkedList(){ Node<String> n = new Node<String>("111"); Node<String> n1 = new Node<String>("222"); Node<String> n2 = new Node<String>("333"); // head = n; n.next = n1; n1.next = n2; // return head; } /** * @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

Recursion implementation inversion:

/** * @package_name: com.lyl. Linklist * @className: ReverseByRecursiveTest * @description: Using recursion to reverse a single list * @date: 2020-05-30 17:01 **/ Public class ReverseByRecursiveTest {/** * public class ReverseByRecursiveTest Head head Node * / public static Node reverse (head) {if (head = = null | | head. The next = = null) {return head; } // Get the next Node of the head Node, use the temp temporary Node to store Node temp = head.next; // call Node recursively 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 list of nodes head = node.createlinkedList (); System.out.print(" new list: "); Node.traverse(head); // Node newHead = reverse(head); System.out.print(" invert single list: "); 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 (111 nodes in the data field) 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, 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, the recursive call ends, and the structure of the single linked list in the heap is shown below:

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

Loop traversal + secondary space to achieve inversion

/** * @package_name: com.lyl. Linklist * @className: ReverseByTraverseTest * @description: Single linked list inversion using loop traversal + secondary space * @date: 2020-05-30 19:11 **/ Public class ReverseByTraverseTest {/** * public class ReverseByTraverseTest {/** * public class ReverseByTraverseTest {/** * public class ReverseByTraverseTest {/** * public class ReverseByTraverseTest Public static Node reverse(Node head) {// 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 list.get(list.size() -1); } // test public static void main(String[] args) {// Create a list of nodes head = node.createlinkedList (); System.out.print(" new list: "); Node.traverse(head); // Node newHead = reverse(head); System.out.print(" invert single list: "); Node.traverse(newHead); }}Copy the code

Double pointer + auxiliary temporary node to achieve inversion

/** * @PACKAGE_NAME: com.lyl.linklist * @ClassName: ReverseByDoublePointerTest * @Description: Single-linked list inversion using double Pointers + auxiliary temporary nodes * @date: The 2020-05-30 * * / michal public class ReverseByDoublePointerTest {/ * * * using double pointer + auxiliary temporary node list inversion * @ param head * @ return back into reverse */ public static Node reverse(Node head) {// Node current; // Previous pointer Node previous; // the current node pointer is initialized to the head node. // Initialize previous pointer to null previous = null; while(current ! = null){// Secondary temporary Node, next Node of current Node Node temp = current. Next; Current. Next = previous; // The next node of the current node points to the previous node pointer. // Then move the previous node pointer to previous = current; // Then move the previous node pointer to previous = current; Current = temp; // The pointer to the current node also moves forward one node, i.e. to the next node of the current node, which is the node to which the temporary node points. } // return previous; } // test public static void main(String[] args) {// Create a list of nodes head = node.createlinkedList (); System.out.print(" new list: "); Node.traverse(head); // Node newHead = reverse(head); System.out.print(" invert single list: "); Node.traverse(newHead); }}Copy the code

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

Wenyuan network, only for the use of learning, if there is infringement please contact delete.

I’ve compiled the interview questions and answers in PDF files, as well as a set of learning materials covering, but not limited to, the Java Virtual Machine, the Spring framework, Java threads, data structures, design patterns and more.

Follow the public account “Java Circle” for information, as well as quality articles delivered daily.