Abstraction
使用C語言簡單的實現linked list，並用C++的std::vector實作出相同的功能作比較。Introduction
學習資料結構，第一個要學的就是linked list，本文示範最簡單的linked list實現，包含建立與顯示，可把它當成linked list的標準範本，畢竟步驟都差不多。一個基本的問題：為什麼需要linked list?若要將大量資料存到記憶體，你會想到什麼?第一個想到的就是array，但C語言是個靜態語言，array必須事先宣告大小，這樣compiler才能進行最佳化，若到時候沒用這麼多記憶體，就白白浪費記憶體了。或許你會說array可以配合malloc()變成動態array，但前提是你必須告訴malloc()要建立多大的array，若連要建立多大的陣列也不確定，而是在run-time看有多少資料就建立多大，這時連malloc()的動態array也不能用了，此時就得靠linked list。
linked list是資料結構的基礎，基本上就是靠struct如火車車廂那樣連在一起，run-time有需要時，在動態掛一個struct上去。
C語言
1 /* 2 (C) OOMusou 2008 http://oomusou.cnblogs.com 3 4 Filename : DS_linked_list_simple.c 5 Compiler : Visual C++ 8.0 6 Description : Demo how to use malloc for linked list 7 Release : 03/22/2008 1.0 8 */ 9 #include < stdio.h > 10 #include < stdlib.h > 11 #include < string .h > 12 13 #define SLEN 255 14 15 struct list { 16 int no; 17 char name[SLEN]; 18 struct list * next; 19 }; 20 21 int main() { 22 int no; 23 char s[ 255 ]; 24 25 struct list * head = NULL; 26 struct list * current = NULL; 27 struct list * prev = NULL; 28 29 while ( 1 ) { 30 printf( " No. = " ); 31 scanf( " %d " , & no); 32 33 if (no == 0 ) 34 break ; 35 36 printf( " Name = " ); 37 scanf( " %s " , s); 38 39 current = ( struct list * )malloc( sizeof ( struct list)); 40 if (current == NULL) 41 exit(EXIT_FAILURE); 42 43 current -> next = NULL; 44 45 current -> no = no; 46 strncpy(current -> name, s, SLEN - 1 ); 47 current -> name[SLEN - 1 ] = ' \0 ' ; 48 49 if (head == NULL) 50 head = current; 51 else 52 prev -> next = current; 53 54 prev = current; 55 } 56 57 // display linked list 58 current = head; 59 while (current != NULL) { 60 printf( " No. = %d, Name = %s\n " , current -> no, current -> name); 61 current = current -> next; 62 } 63 64 // free linked list 65 current = head; 66 while (current != NULL) { 67 prev = current; 68 current = current -> next; 69 free(prev); 70 } 71 }
執行結果 No. = 1 Name = clareNo. = 2 Name = jessieNo. = 0 No. = 1 , Name = clareNo. = 2 , Name = jessie
15行 struct list { int no; char name[SLEN]; struct list * next;};
linked list的基礎就是struct，所以先建立一個自訂的struct型別，因為linked list是靠struct串聯起來，所以最後要多一個struct pointer指向下一個struct。 25行
struct list * head = NULL; struct list * current = NULL; struct list * prev = NULL;
建立linked list最基本需要三個指標，head指向linked list的第一個struct，current指向目前剛建立的struct，prev則指向前一個struct，目的在指向下一個struct，對於未使用的pointer，一律指定為NULL，這是一個好的coding style，可以藉由判斷是否為NULL判斷此pointer是否被使用。 39行
current = ( struct list * )malloc( sizeof ( struct list)); if (current == NULL) exit(EXIT_FAILURE); current -> next = NULL;
每當有新資料，需要建立一個新的struct時，就用malloc()要一塊記憶體，由於malloc()傳回的是void *，所以要手動轉型成struct list *。但malloc()並不是一定會成功，若記憶體不足時，仍然會失敗，所以必須判斷是否傳回NULL。 由於一個新的node，一定是linked list最後一個node，所以將current->next接null。
45行
current -> no = no;strncpy(current -> name, s, SLEN - 1 );current -> name[SLEN - 1 ] = ' \0 ' ;
正式將輸入的資料填進struct，至於為什麼要用strncpy()而不用strcpy()呢?雖然strcpy()也可以，但strncpy()比較安全，若輸入的字串大小超過struct所定義的字串大小，則會只接受struct所接受的字串大小，而不會因為找不到'\0'而造成程式錯誤。 49行
if (head == NULL) head = current; else prev -> next = current; prev = current;
判斷若是第一個node，則將目前的node當成head，若不是第一個node，則將前一個node指向目前的node，完成linked list的連接。最後將目前的node當成前一個node，以備指向下一個node。 58行
// display linked list current = head; while (current != NULL) { printf( " No. = %d, Name = %s\n " , current -> no, current -> name); current = current -> next;}
要重新顯示linked list，所以將指標再度指向第一個node，每當顯示一個node後，就指向下一個node，直到指到NULL為止。 64行
// free linked list current = head; while (current != NULL) { prev = current; current = current -> next; free(prev);}
由於malloc()是將記憶體放在heap，而不是放在stack，所以並不會隨著function的結束而釋放，必須要手動使用free()釋放記憶體，否則會造成memory leak。 再來看C++，由於STL已內建一些容器，所以不需再重新實作linked list，有兩個選擇：std::vector或者std::list。std::vector的優點是non-sequential access超快，新增資料於後端超快，但insert和erase任意資料則超慢；std::list則剛好相反，insert和erase速度超快，但non-sequential access超慢，由於本例只有新增與non-sequential access，所以適合std::vector。不過由於STL使用泛型技術，若將來需求改變，想改用std::list也沒關係，只要將容器改掉即可，剩下的都不用改，因為STL的演算法並不挑容器，這正是泛型偉大之處。
C++
1 /* 2 (C) OOMusou 2008 http://oomusou.cnblogs.com 3 4 Filename : DS_linked_list_simple_vector_class.cpp 5 Compiler : Visual C++ 8.0 6 Description : Demo how to use vector instead of linked list 7 Release : 03/22/2008 1.0 8 */ 9 #include < iostream > 10 #include < string > 11 #include < vector > 12 13 using namespace std; 14 15 class List { 16 public : 17 int no; 18 string name; 19 }; 20 21 int main() { 22 vector < List > vec; 23 24 while ( 1 ) { 25 List list; 26 cout << " No. = " ; 27 cin >> list.no; 28 29 if (list.no == 0 ) 30 break ; 31 32 cout << " Name = " ; 33 cin >> list.name; 34 35 vec.push_back(list); 36 } 37 38 vector < List > ::iterator iter = vec.begin(); 39 for (; iter != vec.end(); ++ iter) 40 cout << " No. = " << iter -> no << " , Name = " << iter -> name << endl; 41 }
執行結果
No. = 1 Name = clareNo. = 2 Name = jessieNo. = 0 No. = 1 , Name = clareNo. = 2 , Name = jessie
15行由struct改用了class，不過若繼續使用struct亦可，至於其他的程式都很直觀，就不再多做解釋。 Conclusion
本文主要是討論使用C語言透過malloc()實現資料結構的linked list，以彌補靜態語言的不足，同時亦討論C++使用STL的替代方案與便利性，C與C++各擅勝場，你可自行決定使用C或C++。See Also