C++資料結構與演算法: 單向鏈結串列(上)

在上一篇主要解釋如何使用指標，而這篇將建立含有字串資料型態的單向鏈結串列，如圖一所示．換句話說，這次範例將實作類似Qt的QStringList，在官方文件指出QStringList繼承QList<T>，然而我使用類似QLinkedList<T>實作字串串列(a list of strings)，因此實作範例將與QStringList有所不同．

圖一．字串型態的連結串列

下表描述QList<T>和QLinkedList<T>的差別性，基本上新增項目時(item)，QLinkList是最快速的，但存取資料比較不方便．

	QList<T>	QLinkedList<T>
特性	基於索引值存取(index-based access)所要的資料	基於迭代器存取(iterator -based access)所要的資料
	利用索引值直接存取任一項目(item)	存取任一項目(item)時，可能需要走訪所有項目
	具有陣列(Array)的特性, 因此插入或刪除資料，需要搬動其他項目	可快速在特定位置插入資料
存取	易存取資料	不易存取資料
	時間複雜度
插入	O(n)	O(1)
Prepending	Amort. O(1)	O(1)
Appending	Amort. O(1)	O(1)

我們先定義新的資料類型結構strNode，結構成員data為Qt的QString，而next為指向結構strNode的指標變數．typedef主要給資料型態定義新的名稱，而這裡不但將struct strNode命名為nodeptr，而且nodeptr為指向結構strNode的指標變數．

typedef struct strNode
{
  QString data;
  strNode *next;
}*nodeptr;

例如，我們直接使用nodeptr宣告指向結構strNode的指標變數head．

nodeptr head;

---

作者有話要說：　
下一篇將利用類別來實作如何在串列後面加入(append)項目.