由LintCode問題子集出發，淺析ArrayList的拷貝問題

在做LintCode上的遞歸類題目子集時，我一開始的想法是遞歸到最后一層即單元素時然后開始逐層返回，產生相應的每層的子集并添加到最終的結果中去。于是乎有了以下代碼：

public List<List<Integer>> findSolution(int[] nums, int begin, int end){List<List<Integer>> result = new ArrayList<>();List<List<Integer>> pre_result = new ArrayList<>();List<Integer> temp = new ArrayList<>();temp.add(nums[end]);if(begin==end){result.add(temp);return result;}end--;pre_result = findSolution(nums,begin,end);result = new ArrayList<>(pre_result);end++;for(List<Integer> list:pre_result){list.add(nums[end]);Collections.sort(list);result.add(list);}result.add(temp);return result;}public List<List<Integer>> subsets(int[] nums) {// write your code hereList<List<Integer>> result = new ArrayList<>();if(nums.length>0){result = findSolution(nums,0,nums.length-1);}List<Integer> temp = new ArrayList<>();result.add(temp);return result;}

算法似乎很正確，每層返回處理的時候有一個pre_result和result兩個List，其中result由new ArrayList<>(pre_result)進行復制。然后對pre_result進行遍歷，將其中每個List的元素加上當前層的元素后加入到result中得到結果并返回。看起來似乎毫無破綻,然后我放心的在遍歷pre_result時對其中的元素進行修改，但在提交的時候出現了問題，WA。然后我進行調試處理，以[1,2,3]為樣例進行輸入，在遍歷的時候輸出result和list，以下為輸出結果：

list [1, 2]
result [[1, 2], [1, 2]]
list [1, 2, 3]
result [[1, 2, 3], [1, 2, 3], [2], [1, 2, 3]]
list [1, 2, 3, 3]
result [[1, 2, 3, 3], [1, 2, 3, 3], [2], [1, 2, 3, 3], [1, 2, 3, 3]]
list [2, 3]
result [[1, 2, 3, 3], [1, 2, 3, 3], [2, 3], [1, 2, 3, 3], [1, 2, 3, 3], [2, 3]]

對結果進行分析：在改變pre_result中的元素時，如果按之前的想法走，result中的元素不可能出現修改，也就是第一個result應該是?[[1], [1, 2]]，但是結果卻是[[1, 2], [1, 2]]。這極有可能是因為修改pre_result中的元素的時候result中的元素也跟著被修改掉了。這就說明new ArrayList<>()的拷貝是淺拷貝類型的，它只是一個引用的拷貝而非真正的對象的拷貝。當list在修改對象中內容的時候，result的值當然會發生變化。因此我對遍歷這一過程的代碼進行修改，以下為重寫代碼：

for(List<Integer> list:pre_result){List<Integer> temp_list = new ArrayList<>(list);temp_list.add(nums[end]);System.out.println("list "+list);System.out.println("temp_list "+temp_list);Collections.sort(temp_list);result.add(temp_list);System.out.println("result "+result);}

新建一個temp_list = new ArrayList<>(list)，原以為以這種方式拷貝List也只是徒勞無功，修改了temp_list后list也會跟著改變。但沒想到在測試的時候AC了，這就說明了list并未隨著temp_list的元素增加而增加。然后我在遍歷中輸出temp_list和list這兩個List，以下為結果：

list [1]
temp_list [1, 2]
result [[1], [1, 2]]
list [1]
temp_list [1, 3]
result [[1], [1, 2], [2], [1, 3]]
list [1, 2]
temp_list [1, 2, 3]
result [[1], [1, 2], [2], [1, 3], [1, 2, 3]]
list [2]
temp_list [2, 3]
result [[1], [1, 2], [2], [1, 3], [1, 2, 3], [2, 3]]

果然和我的猜測一致。但是從這一測試結果看仿佛ArrayList又不是簡簡單單的淺拷貝了，當temp_list在添加元素的時候并不對list造成影響。為了測試當list添加元素時會不會對temp_list造成影響我又在拷貝這一語句后加上了list.add(999)，結果有以下輸出：

list [1, 999]
temp_list [1, 2]
result [[1, 999], [1, 2]]
list [1, 999, 999]
temp_list [1, 999, 3]
result [[1, 999, 999], [1, 2], [2], [1, 3, 999]]
list [1, 2, 999]
temp_list [1, 2, 3]
result [[1, 999, 999], [1, 2, 999], [2], [1, 3, 999], [1, 2, 3]]
list [2, 999]
temp_list [2, 3]
result [[1, 999, 999], [1, 2, 999], [2, 999], [1, 3, 999], [1, 2, 3], [2, 3]]

這就說明了list元素的添加也不對temp_list造成影響。從以上的分析就可以得出對ArrayList拷貝類型的結論了：其應當介于淺拷貝與深拷貝之間。當用List<Integer> temp_list = new ArrayList<>(list)這一方式進行拷貝時，當前在list中的元素的拷貝方式為淺拷貝，只是拷貝一個引用而已。無論是在temp_list還是list中對這些舊元素進行操作時，兩者均會受到影響，這是淺拷貝的概念；而在list或temp_list中添加或刪除新元素時，它們兩者互不干擾，這是深拷貝的概念。