昨天的 java 實現單例模式 中，我們的雙重檢驗鎖機制因為指令重排序問題而引入了 volatile 關鍵字，不少朋友問我，到底為啥要加 volatile 這個關鍵字呀，而它，到底又有什么神奇的作用呢？
對 volatile 這個關鍵字，在昨天的講解中我們簡單說了一下：被 volatile 修飾的共享變量，都會具有下面兩個屬性：
- 保證不同線程對該變量操作的內存可見性。
- 禁止指令重排序。
共享變量：如果一個變量在多個線程的工作內存中都存在副本，那么這個變量就是這幾個線程的共享變量。
可見性：一個線程對共享變量值的修改，能夠及時地被其它線程看到。
對于重排序，不熟悉的建議直接 google 一下，這里也就不多提了。只需要記住，在多線程中操作一個共享變量的時候，一定要記住加上 volatile 修飾即可。
由于時間關系，我們還是得先進入今天的正題，對于 volatile 關鍵字，在要求并發編程能力的面試中還是很容易考察到的，后面我也會簡單給大家講解。
輸入一個單鏈表的頭結點，從尾到頭打印出每個結點的值。
我們的鏈表有很多，單鏈表，雙向鏈表，環鏈表等。這里是最普通的單鏈表模式，我們一般會在數據存儲區域存放數據，然后有一個指針指向下一個結點。雖然 java 中沒有指針這個概念，但 java 的引用恰如其分的填補了這個問題。
看到這道題，我們往往會很快反應到每個結點都有 next 屬性，所以要從頭到尾輸出很簡單。于是我們自然而然就會想到先用一個 while 循環取出所有的結點存放到數組中，然后再通過逆序遍歷這個數組，即可實現逆序打印單鏈表的結點值。
我們假定結點的數據為 int 型的。實現代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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 = new node(); head.next.next.next.data = 4; head.next.next.next.next = new node(); head.next.next.next.next.data = 5; printlinkreverse(head); }} |
這樣的方式確實能實現逆序打印鏈表的數據，但明顯用了整整兩次循環，時間復雜度為 o(n²)。等等！逆序輸出？似乎有這樣一個數據結構可以完美解決這個問題，這個數據結構就是棧。
棧是一種「后進先出」的數據結構，用棧的原理更好能達到我們的要求，于是實現代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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 = new node(); head.next.next.next.data = 4; head.next.next.next.next = new node(); head.next.next.next.next.data = 5; printlinkreverse(head); }} |
既然可以用棧來實現，我們也極容易想到遞歸也能解決這個問題，因為遞歸本質上也就是一個棧結構。要實現逆序輸出鏈表，我們每訪問一個結點的時候，我們先遞歸輸出它后面的結點，再輸出該結點本身，這樣鏈表的輸出結果自然也是反過來了。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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 = new node(); head.next.next.next.next.data = 5; printlinkreverse(head); }} |
雖然遞歸代碼看起來確實很整潔，但有個問題：當鏈表非常長的時候，一定會導致函數調用的層級很深，從而有可能導致函數調用棧溢出。所以顯示用棧基于循環實現的代碼，健壯性還是要好一些的。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://www.jianshu.com/p/65e4df545410
