數(shù)組作鏈表 數(shù)組作鏈表有哪些優(yōu)點(diǎn)？

一般傳統(tǒng)鏈表的物理結(jié)構(gòu)，是由指針把一個一個的節(jié)點(diǎn)相互連接而成：

view sourceprint?1 struct node

2 {

3 DataType data;

4 node* previous;

5 node* next;

6 }

其特點(diǎn)是按需分配節(jié)點(diǎn)，靈活動態(tài)增長。

但是此外，還有另外一種方式是使用數(shù)組實現(xiàn)鏈表，這里所有的node都在預(yù)先分配好的數(shù)組中，不使用指針，而是用數(shù)組下標(biāo)來指向前一個、下一個元素：

view sourceprint?1 struct node

2 {

3 DataType data;

4 int previous;

5 int next;

6 }

其特點(diǎn)是預(yù)先分配節(jié)點(diǎn)，并且如果需要鏈表長度隨需增加，需要reallocation ,和vector類似。

 

下面就我自己的一些了解，談一下其優(yōu)缺點(diǎn)與應(yīng)用。

數(shù)組作鏈表有哪些優(yōu)點(diǎn)
能要省些內(nèi)存嗎？不見得；速度要快嗎？沒看出來，那么為什么要使用這種不那么直觀的方式來實現(xiàn)鏈表呢？
數(shù)組的內(nèi)存布局比較緊湊，能占些局部性原理的光 在不提供指針的語言中實現(xiàn)鏈表結(jié)構(gòu)，如vb等 進(jìn)程間通信，使用index比使用指針是要靠譜 - 一個進(jìn)程中的指針地址在另外一個進(jìn)程中是沒有意義的 對一些內(nèi)存奇缺應(yīng)用，當(dāng)其值類型為整型，且值域與數(shù)組index相符時，可以將next指針與data復(fù)用，從而節(jié)省一些內(nèi)存
實現(xiàn)與應(yīng)用
Id allocator
這里第一個例子針對上面第四點(diǎn)展開，其主要的應(yīng)用在于ID的分配與回收，比如數(shù)據(jù)庫表中的每條記錄都需要一個unique id，當(dāng)你增增減減若干次之后，然后新建一個表項，你該分配給它哪個id呢？
維持一個id，每增加一行就加1，刪行不回收id --- 這樣id會無限增加，太浪費(fèi)了 每次分配都遍歷一遍，找到最小的那個還沒被用過的id --- 這樣太浪費(fèi)時間了
一個比較合理的做法是維護(hù)一個“可用ID”的鏈表，每次增加就從鏈表中拿一個，每次刪除就把被刪的ID鏈接到鏈表中，但是，對于傳統(tǒng)鏈表結(jié)構(gòu)而言，其節(jié)點(diǎn)的定義類似于：
view sourceprint?1 struct idnode

2 {

3 int availableID;

4 idnode* next;

5 };

這里，因為鏈表的值的類型與值域都與數(shù)組的index相符，我們可以復(fù)用其值和next，從而只需一個int數(shù)組，而不是一個idnode數(shù)組，數(shù)組中某個元素的值代表的即是鏈表節(jié)點(diǎn)的值，也是鏈表的下一個節(jié)點(diǎn)下標(biāo)。下面是一個idallocator的實現(xiàn)，主要提供allocate和free兩個函數(shù)用來滿足上述要求：
view sourceprint?01 const static char LIST_END = -1;

02 template < typename integer>

03 class idallocator

04 {

05 public:

06 idallocator(int _num): num(_num)

07 {

08 array = new integer[num];

09 // Initialize the linked list. Initially, it is a full linked list with all elements linked one after another.

10 head = 0;

11 for (integer i = 0; i < num; i++)

12 {

13 array[i] = i + 1;

14 }

15 array[num-1] = LIST_END;

16 count = num;

17 }

18 ~idallocator()

19 {

20 delete [] array;

21 }

22 integer allocate() // pop_front, remove a node from the front

23 {

24 int id = head;

25 if(id != LIST_END)

26 {

27 head = array[head];

28 count--;

29 }

30 return id;

31 }

32 // push_front, add a new node to the front

33 void free(const integer& id)

34 {

35 array[id] = head;

36 count++;

37 head = id;

38 }

39 // push_front, add a new node to the front

40 bool free_s(const integer& id)

41 {

42 // make sure this id is not in the list before we add it

43 if(exist(id)) return false;

44 free(id);

45 return true;

46 }

47 size_t size()

48 {

49 return count;

50 }

51 private:

52 bool exist(const integer& id)

53 {

54 int i = head;

55 while (i != LIST_END)

56 {

57 if(i == id) return true;

58 i = array[i];

59 }

60 return false;

61 }

62 private:

63 integer* array;

64 int num;// totall number of the array

65 int count;// number in the linked list

66 int head;// index of the head of the linked list

67 };

Double linked list
用數(shù)組實現(xiàn)鏈表，大多數(shù)情況下，是與傳統(tǒng)鏈表類似的，無非是在添加、刪除節(jié)點(diǎn)后，調(diào)整previous，next域的指向。但是有一點(diǎn)，當(dāng)我在添加一個新的節(jié)點(diǎn)時，如何從數(shù)組中拿到一個還未被使用過的節(jié)點(diǎn)呢？這里有兩種方法：

如果你看懂了上面的id allocator，你也許已經(jīng)意識到，使用上面那個idallocator類就可以簡單的實現(xiàn)這個需求 另外一種方法，其實原理上也類似，就是在這個double linked list類中維護(hù)兩個鏈表，一個是已使用的，一個是未使用的
第一種因為借助于一個工具類，實現(xiàn)看起來會簡潔很多，但是idallocator會消耗額外的內(nèi)存，因此第二種方法相對來講會比較好。