上一篇介紹了一維數(shù)據(jù)結(jié)構(gòu)的關(guān)系，算是開(kāi)篇了數(shù)據(jù)結(jié)構(gòu)這個(gè)系列。這篇詳細(xì)說(shuō)一下鏈表的實(shí)現(xiàn)。
鏈表實(shí)現(xiàn)也是我面試時(shí)喜歡出的一道題，因?yàn)橛袑哟危芴岈F(xiàn)區(qū)分度?？此坪?jiǎn)單的三個(gè)操作，需要處理的異常和邊界情況并不少，能一次完美寫(xiě)對(duì)并不容易。
而且這里還有一個(gè)哨兵的概念，合理運(yùn)用能減少邊界處理，是一個(gè)遞進(jìn)的層次，可為候選人增加區(qū)分度。

鏈表的操作：
（1）SEARCH(x)：鏈表的搜索
（2）INSERT(i,x)：鏈表的插入，在第i個(gè)位置插入x
（3）DELETE（x）:鏈表的刪除

哨兵（sentinel）：
為了減少邊界條件的判斷（是否為空鏈表等等），引入哨兵，使得鏈表永遠(yuǎn)不為“空”。

下面就細(xì)講一下鏈表實(shí)現(xiàn)

插入

上面說(shuō)了為了減少邊界，我們使用了一個(gè)哨兵的概念，那么都有哪些邊界呢？

1.不用哨兵

插入的核心操作如下：

// pre: 前置節(jié)點(diǎn); p: 當(dāng)前第i個(gè)節(jié)點(diǎn)
// item: 待插入節(jié)點(diǎn)
pre.next -> item;
item.next -> p;

進(jìn)行插入，就需要知道兩個(gè)節(jié)點(diǎn)指針，這時(shí)就出現(xiàn)了兩個(gè)邊界情況，是不存在前置節(jié)點(diǎn)的：

• 鏈表為空
• 插入位置是0

需要對(duì)兩種情況做特殊處理，直接看代碼

void insert(i,item) {
  // 空鏈表的處理
  if (head == NULL) {
    head == item;
  }

  // 插入到第一個(gè)位置的情況
  if (i == 0) {
    // 插入
    head.next -> item;
    item.next -> head;
    head = item;
  } else {
     // 第一個(gè)節(jié)點(diǎn)
    Node *pre = head;
    Node *p = head -> next;
    int idx = 0;
    // 添加 p 非空條件，處理 i > length 情況 
    while (idx < i && p != NULL) {
      pre = pre -> next;
      p = p -> next;
    }
    // 插入
    pre.next -> item;
    item.next -> p;
  }
}

處理下來(lái)27行，進(jìn)行了兩次if-else判斷

2.使用哨兵

但如果引入哨兵概念，會(huì)怎么樣呢？

void insert(i,item) {
  // 獲取哨兵和實(shí)際上第一個(gè)節(jié)點(diǎn)
  Node *pre = sentinel;
  Node *p = sentinel -> next;
  int idx = 0;
  // 添加 p 非空條件，處理 i > length 情況 
  while (idx < i && p != NULL) {
    pre = pre -> next;
    p = p -> next;
  }
  // 插入
  pre.next -> item;
  item.next -> p;
}

可以看到，整個(gè)操作簡(jiǎn)單歸一，14行就搞定了，沒(méi)有額外邊界處理邏輯處理，也不需要再進(jìn)行頭結(jié)點(diǎn)變更，哨兵的內(nèi)存開(kāi)銷(xiāo)也不大。是一個(gè)優(yōu)雅的解決方式。

再看看剩下兩個(gè)方法的實(shí)現(xiàn)細(xì)節(jié)

搜索

比較簡(jiǎn)單，沒(méi)有對(duì)前置節(jié)點(diǎn)的依賴(lài)，所以無(wú)需做特殊處理。

Node* search(x) {
    Node *p = head;
    // Node *p = sentinel -> next;

    while (p != NULL) {
        if (*p.data == x) {
            break;
        }
        p = p -> next;
    }

    return p;
}

刪除

先簡(jiǎn)單介紹下兩種鏈表刪除操作

1.依賴(lài)前置節(jié)點(diǎn)pre

1>將 pre->next 指向 found->next
2>去除 found->next指向
3>刪除found節(jié)點(diǎn)

方法一

但是對(duì)于單鏈表操作，拿到前置節(jié)點(diǎn)非常困難，為了避免使用前置節(jié)點(diǎn)，我們可以使用一次拷貝，將刪除節(jié)點(diǎn)從found變成found->next，比如：

2.不依賴(lài)前置節(jié)點(diǎn) pre

1>將next節(jié)點(diǎn)內(nèi)容copy到found
2>found->next指向next->next
3>刪除next

方法二

順利避免了對(duì)前置節(jié)點(diǎn)依賴(lài)，還可以復(fù)用上面的 search 函數(shù)。但是這種設(shè)計(jì)，存在一個(gè)問(wèn)題：就是當(dāng)刪除的是最后一個(gè)節(jié)點(diǎn)時(shí)，依然有對(duì)前置節(jié)點(diǎn)的依賴(lài)。這時(shí)引入一個(gè)末尾哨兵，保證我們的 next 節(jié)點(diǎn)永遠(yuǎn)不為 NULL，讓我們避免這種情況。

需要對(duì)插入、查找做修改

3.引入末尾哨兵

init() {
  head_sentinel = new Node();
  tail_sentinel = new Node();
  head_sentinel->next = tail_sentinel;
  tail_sentinel->next=NULL:
}

void insert(i,item) {
  // 獲取頭部哨兵和實(shí)際上第一個(gè)節(jié)點(diǎn)
  Node *pre = head_sentinel;
  Node *p = head_sentinel -> next;
  int idx = 0;
  // 添加 p ≠ tail_sentinel，處理 i > length 情況 
  while (idx < i && p != tail_sentinel) {
    pre = pre -> next;
    p = p -> next;
  }
  // 插入
  pre.next -> item;
  item.next -> p;
}

Node* search(x) {
    Node *p = head_sentinel -> next;

        // 結(jié)束條件，變?yōu)椴坏扔谀┪采诒?    while (p != tail_sentinel) {
        if (*p.data == x) {
            break;
        }
        p = p -> next;
    }

    return p;
}

void delete(x) {
    Node *found = search(x);
    if (found == NULL) return;

    Node *next = found->next;
    *found.data = copy(*next.data);
        // 因?yàn)橛心┪采诒拇嬖冢琻ext永遠(yuǎn)不為NULL
    found->next = next->next;
    next->next = NULL;
    delete(next);
}

小結(jié)

綜上，哨兵的作用就是保持鏈表非空，將所有操作去差異化，減少邊界條件的處理。從廣義上來(lái)說(shuō)，鏈表的操作過(guò)程中產(chǎn)生了對(duì)“鄰居節(jié)點(diǎn)”的依賴(lài)，當(dāng)這種依賴(lài)是不穩(wěn)定的時(shí)候，我們就可以使用哨兵，將這種依賴(lài)補(bǔ)齊，或者是轉(zhuǎn)化為對(duì)“哨兵”的穩(wěn)定依賴(lài)。
此外，在刪除過(guò)程中，因?yàn)閱捂湵慝@取前置節(jié)點(diǎn)困難，所以針對(duì)該點(diǎn)進(jìn)行優(yōu)化，這也是很多數(shù)據(jù)結(jié)構(gòu)和算法調(diào)優(yōu)的思路。熟悉后可以舉一反三。

參考

http://www.itdecent.cn/p/afbfc784238a
https://www.zhihu.com/question/27155932