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

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

view sourceprint?1 struct node

2 {

3 DataType data;

4 node* previous;

5 node* next;

6 }

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

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

view sourceprint?1 struct node

2 {

3 DataType data;

4 int previous;

5 int next;

6 }

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

 

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

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

2 {

3 int availableID;

4 idnode* next;

5 };

這里，因?yàn)殒湵淼闹档念?lèi)型與值域都與數(shù)組的index相符，我們可以復(fù)用其值和next，從而只需一個(gè)int數(shù)組，而不是一個(gè)idnode數(shù)組，數(shù)組中某個(gè)元素的值代表的即是鏈表節(jié)點(diǎn)的值，也是鏈表的下一個(gè)節(jié)點(diǎn)下標(biāo)。下面是一個(gè)idallocator的實(shí)現(xiàn)，主要提供allocate和free兩個(gè)函數(shù)用來(lái)滿(mǎn)足上述要求：
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ù)組實(shí)現(xiàn)鏈表，大多數(shù)情況下，是與傳統(tǒng)鏈表類(lèi)似的，無(wú)非是在添加、刪除節(jié)點(diǎn)后，調(diào)整previous，next域的指向。但是有一點(diǎn)，當(dāng)我在添加一個(gè)新的節(jié)點(diǎn)時(shí)，如何從數(shù)組中拿到一個(gè)還未被使用過(guò)的節(jié)點(diǎn)呢？這里有兩種方法：

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