In yesterday's Java implementation singleton mode, our double-check lock mechanism introduced the volatile keyword due to the instruction reordering problem. Many friends asked me, why do I need to add the volatile keyword? And what magical effect does it have?
Regarding the keyword volatile , we briefly mentioned in yesterday's explanation: shared variables modified by volatile will have the following two attributes:
Shared variable: If a variable has a copy in the working memory of multiple threads, then this variable is the shared variable of these threads.
Visibility: A thread's modification to the shared variable value can be seen by other threads in a timely manner.
For reordering, if you are not familiar with it, just Google it, so I won’t mention it here. Just remember that when operating a shared variable in multiple threads, you must remember to add volatile modification.
Due to time constraints, we still have to get to today's topic first. The keyword volatile is still easy to detect in the interview that requires concurrent programming skills. I will briefly explain it to you later.
Enter the head node of a single linked list and print out the value of each node from the end to the end.
We have many linked lists, single linked lists, two-way linked lists, ring linked lists, etc. This is the most common single-linked list mode. We usually store data in the data storage area, and then a pointer points to the next node. Although there is no concept of pointer in Java, Java references fit the problem.
When we see this question, we often quickly realize that each node has a next attribute, so it is very simple to output from beginning to end. So we will naturally think of first using a while loop to take out all nodes and store them in the array, and then traverse the array in reverse order, so that the node values of a single linked list can be printed in reverse order.
We assume that the data of the node is of int type. The implementation code is as follows:
public class Test05 { public static class Node { int data; Node next; } public static void printLinkReverse(Node head) { ArrayList<Node> nodes = new ArrayList<>(); while (head != null) { nodes.add(head); head = head.next; } for (int i = nodes.size() - 1; i >= 0; i--) { System.out.print(nodes.get(i).data + " "); } } public static void main(String[] args) { Node head = new Node(); head.data = 1; head.next = new Node(); head.next.data = 2; head.next.next = new Node(); head.next.next.data = 3; head.next.next.next.next = new Node(); head.next.next.next.data = 4; head.next.next.next.next.next = new Node(); head.next.next.next.data = 5; printLinkReverse(head); }}This method can indeed implement reverse-order printing of the linked list data, but it obviously uses two full cycles, with a time complexity of O(n²). etc! Reverse output? It seems that there is such a data structure that can perfectly solve this problem, and this data structure is the stack.
The stack is a "last in first out" data structure. The principle of the stack can better meet our requirements, so the implementation code is as follows:
public class Test05 { public static class Node { int data; Node next; } public static void printLinkReverse(Node head) { Stack<Node> stack = new Stack<>(); while (head != null) { stack.push(head); head = head.next; } while (!stack.isEmpty()) { System.out.print(stack.pop().data + " "); } } public static void main(String[] args) { Node head = new Node(); head.data = 1; head.next = new Node(); head.next.data = 2; head.next.next = new Node(); head.next.next.data = 3; head.next.next.next.next = new Node(); head.next.next.next.data = 4; head.next.next.next.next.next = new Node(); head.next.next.next.next.data = 5; printLinkReverse(head); }}Since it can be implemented using a stack, it is very easy for us to think that recursion can also solve this problem, because recursion is essentially a stack structure. To implement reverse order output link list, every time we access a node, we first recursively output the node behind it, and then output the node itself. In this way, the output result of the linked list will naturally be reversed.
The code is as follows:
public class Test05 { public static class Node { int data; Node next; } public static void printLinkReverse(Node head) { if (head != null) { printLinkReverse(head.next); System.out.print(head.data+" "); } } public static void main(String[] args) { Node head = new Node(); head.data = 1; head.next = new Node(); head.next.data = 2; head.next.next = new Node(); head.next.next.data = 3; head.next.next.next = new Node(); head.next.next.next.data = 4; head.next.next.next.next.next.next = new Node(); head.next.next.next.next.data = 5; printLinkReverse(head); }} Although the recursive code does look very neat, there is a problem: when the linked list is very long, it will definitely lead to deep levels of function calls, which may cause the function call stack overflow. Therefore, the code that displays the code based on loop is better robust.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.