[資結] Linked List 和 Array 的選擇

Linked List 和 Array 都是在程式中用來儲存資料的,
如果經過封裝,例如說 Java 的 LinkedListArrayList
C++ 的 std::liststd::vector
就光看方法 (methods) 的調用,是看不出來兩者的區別的,
但有上過資結的老師一定都會說,

如果有需要大量的插入和刪除就用 Linked List ,
否則使用 Array

類似的話大家應該都有聽過,
由於 Linked List 每插入一個 node 都只要接在整個鏈結的最後面,
刪除只要把鏈結斷開就好,
Array List 則是要先新建一個新的更大的陣列,
把舊的資料複製過去,在最後一個再放新的資料,
久了之後大家只要遇到需要連續輸入資料,
就會毫不猶豫地選擇 Linked List 。

話是這樣說沒錯,
但是使用還是要看實際的狀況,

同樣都是需要連續的新增資料,
但是如果新增的位置不是隨機的,
而只是單純地把資料放在最後面,
這種情況選擇 Array List 反而比較好,
通常在實作 Array List 的時候,
並不會每要插入一個資料,
就重新向系統要一塊新的記憶體,
而是一要就要好幾個,用完了再要新的,

例如說現在有一個 Array 長度為 5 ,且剛好用完,
現在要插入新的資料,
實作的時候並不會向作業系統要一塊 6 格大小的 array ,
可能會要 10 格之類的,
當然也不會為了節省記憶體,每刪除一個元素,
就要一個更小的記憶體,
通常都是會有一個緩衝空間來提升性能。

下面是 C++ 對 vector 和 list 做 push_back() 的測試

#include <iostream>
#include <list>
#include <vector>
#include <chrono>
#include <thread>
#include <iomanip>

using namespace std;

int main()
{
  int i;
  const int COUNT = 100000000;

  chrono::time_point<chrono::system_clock> start, end;
  chrono::duration<double> duration{};

  vector<int> v;
  list<int> l;

  cout.precision(5);

  // std::vector::push_back() start
  start = chrono::system_clock::now();
  for (i = 0; i < COUNT; ++i) v.push_back(i);
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "std::vector::push_back():\t" << duration.count() << "\ts" << endl;
  // end

  // std::list::push_back() start
  start = chrono::system_clock::now();
  for (i = 0; i < COUNT; ++i) l.push_back(i);
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "std::list::push_back():\t\t" << duration.count() << "\ts" << endl;
  // end

  // vector iter test
  start = chrono::system_clock::now();
  for (auto iter = v.begin(); iter != v.end(); ++iter) *iter = 1;
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "vector iter test:\t\t" << duration.count() << "\ts" << endl;
  // end

  // list iter test
  start = chrono::system_clock::now();
  for (auto iter = l.begin(); iter != l.end(); ++iter) *iter = 1;
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "list iter test:\t\t\t" << duration.count() << "\ts" << endl;
  // end

  // vector iter test2
  start = chrono::system_clock::now();
  for (auto& e : v) e = 2;
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "vector iter test2:\t\t" << duration.count() << "\ts" << endl;
  // end

  // list iter test2
  start = chrono::system_clock::now();
  for (auto& e : l) e = 2;
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "list iter test2:\t\t" << duration.count() << "\ts" << endl;
  // end

  // std::vector::pop_back start
  start = chrono::system_clock::now();
  for (i = 0; i < COUNT; ++i) v.pop_back();
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "std::vector::pop_back():\t" << duration.count() << "\ts" << endl;
  // end

  // std::list::pop_back start
  start = chrono::system_clock::now();
  for (i = 0; i < COUNT; ++i) l.pop_back();
  end = chrono::system_clock::now();
  duration = end - start;
  cout << "std::list::pop_back():\t\t" << duration.count() << "\ts" << endl;
  // end

  return 0;
}

output

std::vector::push_back():       1.394   s
std::list::push_back():         9.7314  s
vector iter test:               1.1231  s
list iter test:                 1.827   s
vector iter test2:              0.82924 s
list iter test2:                1.643   s
std::vector::pop_back():        0.49952 s
std::list::pop_back():          6.6248  s

從結果中可以看到,
push_back() 這個動作,
std::vector 明顯比 std::list 快得多,
所以下次不要只要看到好像要做大量的輸入資料,
就盲目的使用 Linked List 囉。

Show Comments