連結串列(linked lists)是一種線性資料結構。不同於陣列資料是在記憶體內連續的儲存，連結串列的資料可能會散在記憶體各處。連結串列中，各元素則是以指標(pointers)串聯起來。

為何要用連結串列?

陣列本身可以儲存同型態的線性資料，但是具有以下的限制:

1. 陣列大小是固定的，所以我們必須事先知道儲存資料數量的上限。同時在宣告時候所需要的記憶體通常就是資料數量的上限，與使用度無關。

2. 在陣列中要插入一個元素是很耗費計算能量的，因為需要先創造一個空間給他。這個動作等同要把後面的元素都進行位移的動作。如假設有個陣列id[]，

   id[] = [1000, 1010, 1050, 2000, 2040]

如果要在id[]中放入一個元素1005並且保持著由小至大的排序狀態我們必須做以下的動作:

1. 將1000之後的元素往後移動，建立出一個空間。

   id[] = [1000, , 1010, 1050, 2000, 2040]

2. 然後將1005放入新的空間。

   id[] = [1000, 1005, 1010, 1050, 2000, 2040]

而不只插入元素很花費計算能量，刪除元素亦然。例如將1010重陣列中刪除後，其後的元素必須往前挪。

與陣列相比，連結串列有以下的優點:

1. 可動態調整大小
2. 插入與刪除元素簡單

而缺點是:

1. 隨機存取其中的元素不易，必須從頭開始循序的搜尋。單純以連結串列結構而言，要進行二分搜尋法(binary search)並沒有很有效率的做法。
2. 每個元素要靠一個指標指到下一個元素，所以需要額外的記憶體空間來儲存指標。
3. 快取(cache)無法發揮最大效率，因為元素並非連續存於記憶體內，而通常快取都是以連續的記憶體區塊來記錄存取。

連結串列表示方法:

連結串列的開頭是由一個指標指向第一個元素。第一個元素稱作為head。如果連結串列是空的(empty)話，則head的值則是NULL。 每一個節點至少有兩個部分:

1. 資料內容
2. 指標(或是參照)到下一個節點

在C語言內我們可用structure來表示一個連結串列的節點，如下方的例子是一個儲存整數的連結串列:

// A linked list node 
struct Node 
{ 
  int data; 
  struct Node *next; 
};

在C++/C#/Java則可以使用類別來實作。

下方是一個含有3個節點的連結串列:

// A simple C program to introduce 
// a linked list 
#include<stdio.h> 
#include<stdlib.h> 

struct Node  
{ 
  int data; 
  struct Node *next; 
}; 

// Program to create a simple linked  
// list with 3 nodes 
int main() 
{ 
  struct Node* head = NULL; 
  struct Node* second = NULL; 
  struct Node* third = NULL; 

  // allocate 3 nodes in the heap   
  head = (struct Node*)malloc(sizeof(struct Node));  
  second = (struct Node*)malloc(sizeof(struct Node)); 
  third = (struct Node*)malloc(sizeof(struct Node)); 

  /* Three blocks have been allocated  dynamically.  
     We have pointers to these three blocks as first, 
     second and third      
       head           second           third 
        |                |               | 
        |                |               | 
    +---+-----+     +----+----+     +----+----+ 
    | #  | #  |     | #  | #  |     |  # |  # | 
    +---+-----+     +----+----+     +----+----+ 

   # represents any random value. 
   Data is random because we haven’t assigned  
   anything yet  */

  head->data = 1; //assign data in first node 
  head->next = second; // Link first node with  
                       // the second node 

  /* data has been assigned to data part of first 
     block (block pointed by head).  And next 
     pointer of first block points to second.   
     So they both are linked. 

       head          second         third 
        |              |              | 
        |              |              | 
    +---+---+     +----+----+     +-----+----+ 
    | 1  | o----->| #  | #  |     |  #  | #  | 
    +---+---+     +----+----+     +-----+----+     
  */  

  // assign data to second node  
  second->data = 2;  

  // Link second node with the third node 
  second->next = third; 

  /* data has been assigned to data part of second 
     block (block pointed by second). And next 
     pointer of the second block points to third  
     block. So all three blocks are linked. 

       head         second         third 
        |             |             | 
        |             |             | 
    +---+---+     +---+---+     +----+----+ 
    | 1  | o----->| 2 | o-----> |  # |  # | 
    +---+---+     +---+---+     +----+----+      */    

  third->data = 3; //assign data to third node 
  third->next = NULL; 

  /* data has been assigned to data part of third 
    block (block pointed by third). And next pointer 
    of the third block is made NULL to indicate 
    that the linked list is terminated here. 

     We have the linked list ready.   

           head     
             | 
             |  
        +---+---+     +---+---+       +----+------+ 
        | 1  | o----->|  2  | o-----> |  3 | NULL | 
        +---+---+     +---+---+       +----+------+        

    Note that only head is sufficient to represent  
    the whole list.  We can traverse the complete  
    list by following next pointers.    */      

  return 0; 
}

任務

上面的程式產生了一個簡單的連結串列，請在上述的程式碼中加入一個涵式printList將該連結串列輸出，一個數字印一行。涵式宣告如下

// printList可將連結串列的內容從某個節點開始循序列出
void printList(struct Node *n)
{
  // 請在這邊設計程式碼
}