不帶哨兵節(jié)點(diǎn)的雙向鏈表即一般的雙向鏈表，有一個(gè)頭指針指向第一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有key值和兩個(gè)指針next和pre，分別指向前后相鄰的節(jié)點(diǎn)，頭結(jié)點(diǎn)的pre=NULL，尾節(jié)點(diǎn)的next=NULL，比較明了，但是也有麻煩的地方：在做查找刪除節(jié)點(diǎn)等操作的時(shí)候，免不了要判斷邊界條件，比如node==NULL等。先來看看這種鏈表的代碼：

/*

* 實(shí)現(xiàn)沒有哨兵節(jié)點(diǎn)的雙向鏈表，需要自己判斷邊界條件

*/

#include

using namespace std;

class list {

struct node {

int key;

node* next;

node* pre;

node(int k) :

key(k), next(NULL), pre(NULL) {

}

};

public:

node* head;

int len;

list() :

head(NULL), len(0) {

}

~list() {

node* tmp1 = head, *tmp2;

while (tmp1 != NULL) {

tmp2 = tmp1->next;

delete tmp1;

len--;

cout << "len=" << len << endl;

tmp1 = tmp2;

}

}

/*

* 在頭處插入節(jié)點(diǎn)

*/

void insertHead(int k) {

node* n = new node(k);

n->next = head;

head = n;

if (n->next != NULL) {

n->next->pre = n;

}

len++;

}

/*

* 刪除指針指向的節(jié)點(diǎn)

*/

int del(node* n) {

if (n == NULL) {

return -1;

}

if (n->pre != NULL) {

n->pre->next = n->next;

} else {

head = n->next;

}

if (n->next != NULL) {

n->next->pre = n->pre;

}

delete n;

len--;

return n->key;

}

/*

* 查找具有某個(gè)key值的節(jié)點(diǎn)

*/

node* searchList(int k) {

if (len == 0) {

return NULL;

}

node* tmp = head;

while (tmp != NULL) {

if (tmp->key == k) {

break;

}

tmp = tmp->next;

}

return tmp;

}

/*

* 遍歷list

*/

void travelList() {

node* tmp = head;

while (tmp != NULL) {

cout << tmp->key << ' ';

tmp = tmp->next;

}

cout << endl;

}

};

int main() {

list* l = new list();

l->insertHead(5);

l->insertHead(4);

l->insertHead(3);

l->travelList();

l->del(l->head->next);

l->travelList();

delete l;

return 0;

}

每次判斷邊界條件，雖然不會(huì)從根本上增加時(shí)間復(fù)雜度，但是對其常數(shù)項(xiàng)還是有影響的；而如果使用帶哨兵節(jié)點(diǎn)構(gòu)成的雙向循環(huán)鏈表，則可以省去這些問題。我們使用一個(gè)“啞的”NIL節(jié)點(diǎn)來代替之前的head頭指針，NIL節(jié)點(diǎn)的key值沒有實(shí)際的意義，主要關(guān)注它的next和pre，初始的時(shí)候，鏈表只有一個(gè)NIL節(jié)點(diǎn)，NIL.next指向自己，NIL.pre也指向自己。當(dāng)添加了若干個(gè)節(jié)點(diǎn)之后，NIL.next指向頭節(jié)點(diǎn)，而NIL.pre則指向尾節(jié)點(diǎn)；而同樣的，這時(shí)頭節(jié)點(diǎn)的pre不再是NULL而是指向NIL，尾節(jié)點(diǎn)的next也不再是NULL，也是指向NIL。

這樣的好處在于，我們判斷邊界條件的時(shí)候，不需要再判斷是否為空，尤其在刪除節(jié)點(diǎn)的時(shí)候，只需要寫兩句即可。但是這樣也帶來一些問題，就是要額外分配空間來存儲(chǔ)NIL節(jié)點(diǎn)，如果對于多個(gè)比較短的鏈表而言，這樣可能會(huì)代碼比較大的冗余空間。

代碼如下：

/*

* 實(shí)現(xiàn)帶哨兵是雙向循環(huán)鏈表

*/

#include

using namespace std;

class list {

struct node {

int key;

node* next;

node* pre;

node(int k) :

key(k), next(NULL), pre(NULL) {

}

};

//node* head;

public:

node* nil; //哨兵節(jié)點(diǎn)

int len;

list() :

nil(), len(0) {

nil = new node(0); //初始化哨兵節(jié)點(diǎn)

//讓鏈表循環(huán)起來

nil->next = nil;

nil->pre = nil;

}

~list() {

//析構(gòu)的時(shí)候要delete掉還存在于list中的節(jié)點(diǎn)

if (len == 0) {

delete nil;

return;

}

node* n1 = nil->next;

node* n2 = NULL;

while (n1 != NULL && n1 != nil) {

n2 = n1->next;

delete n1;

len--;

n1 = n2;

}

delete nil;

}

/*

* 在頭部插入節(jié)點(diǎn)

*/

void insertHead(int k) {

node* n = new node(k);

n->next = nil->next;

n->pre = nil;

nil->next = n;

//這一句不要丟了

n->next->pre = n;

len++;

}

/*

* 刪除節(jié)點(diǎn)，這里刪除的操作只需要寫兩句，比不帶哨兵的鏈表操作要簡潔的多

*/

void del(node* n) {

n->pre->next = n->next;

n->next->pre = n->pre;

delete n;

len--;

}

node* searchList(int k) {

node* tmp = nil->next;

//讓nil的key值永遠(yuǎn)不可能等于k

//nil->key = k + 1;

//while (tmp->key != k) {

while (tmp != nil && tmp->key != k) {

tmp = tmp->next;

}

if (tmp != nil) {

return tmp;

} else {

return NULL;

}

}

/*

* 從next指針方向遍歷鏈表

*/

void travelClockwise() {

node* tmp = nil->next;

while (tmp != nil) {

cout << tmp->key << ' ';

tmp = tmp->next;

}

cout << endl;

}

/*

* 從pre指針方向遍歷鏈表

*/

void travelAnticlockwise() {

node* tmp = nil->pre;

while (tmp != nil) {

cout << tmp->key << ' ';

tmp = tmp->pre;

}

cout << endl;

}

};

int main() {

list* l = new list();

l->insertHead(5);

l->insertHead(4);

l->insertHead(3);

l->travelClockwise();

l->del(l->nil->pre);

//l->travelClockwise();

l->travelAnticlockwise();

return 0;

}