前言

昨天說了線性表中的鏈表栓霜，相信仔細(xì)看過的同學(xué)應(yīng)該會明白 鏈 的思想，今天我們來說一說循環(huán)鏈表横蜒。

定義

什么是循環(huán)鏈表呢胳蛮？

循環(huán)鏈表是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的最后一個(gè)結(jié)點(diǎn)指向頭結(jié)點(diǎn)丛晌，形成一個(gè)環(huán)仅炊。因此，從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)出發(fā)都能找到任何其他結(jié)點(diǎn)澎蛛。

圖 1 循環(huán)鏈表示意圖

我們讓鏈表中的最后一個(gè)結(jié)點(diǎn)斤贰，指向頭結(jié)點(diǎn)智哀。這樣鏈表就成了一個(gè)環(huán)（對于內(nèi)存管理比較熟悉的同學(xué)也許已經(jīng)感覺到了壞味道次询，因?yàn)樾纬闪谁h(huán)荧恍，我的思路是，我們打破這個(gè)環(huán)就好了屯吊，而且送巡，我們的主題是數(shù)據(jù)結(jié)構(gòu)，思想為主）盒卸。

Q：使鏈表循環(huán)骗爆，或者說頭尾相接的的好處是什么呢？

好處就是從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)出發(fā)都能找到任何其他結(jié)點(diǎn)蔽介。使用起來更加靈活摘投。比如說煮寡，我們現(xiàn)在的鏈表，查找第一個(gè)結(jié)點(diǎn)犀呼，只需要 O(1) 的時(shí)間幸撕，查找最后一個(gè)結(jié)點(diǎn)需要 O(n) 的時(shí)間，但是相信雖然我還沒寫到棧和隊(duì)列外臂，大家也都知道棧和隊(duì)列的原理坐儿。如果一個(gè)鏈表經(jīng)常要對第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)進(jìn)行操作，比如棧和隊(duì)列宋光，那么我們之前實(shí)現(xiàn)的鏈表就不是很合理貌矿，因?yàn)楂@取最后一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度有點(diǎn)高。

Q：說了這么多罪佳，這和循環(huán)鏈表到底有什么關(guān)系呢逛漫？

我們這里還是需要換個(gè)思路，用循環(huán)鏈表來解決這個(gè)問題赘艳。我們用最后一個(gè)結(jié)點(diǎn)來表示鏈表尽楔，最后一個(gè)結(jié)點(diǎn)的 next 稱為尾指針。比如說圖 1 中的最后一個(gè)結(jié)點(diǎn)是 node9 第练， node9 有數(shù)據(jù)域 data = 9阔馋， 指針域 next = 頭結(jié)點(diǎn)，那么 node9 就是尾結(jié)點(diǎn) rear 娇掏，尾指針就是 rear.next (node9.next) 呕寝，也就是頭結(jié)點(diǎn)了。

通過這種表示方法婴梧，我們在獲取第一個(gè)結(jié)點(diǎn)的時(shí)候下梢，只需要通過 rear.next.next（node9.next.next => 頭結(jié)點(diǎn).next）就可以找到第一個(gè)結(jié)點(diǎn)；通過 rear 就可以找到最后一個(gè)結(jié)點(diǎn)塞蹭，因?yàn)?rear 就是最后一個(gè)結(jié)點(diǎn)（node9）啦孽江。所以，這種表示方法番电，可以使獲取第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1) 常數(shù)項(xiàng)岗屏。這樣，我們在用鏈表實(shí)現(xiàn)棧和隊(duì)列的時(shí)候漱办，例如獲取棧頂这刷、棧底、隊(duì)頭娩井、隊(duì)尾等操作暇屋，我們可以以較高的效率來完成，而不是每次去遍歷整個(gè)表洞辣，這樣太浪費(fèi)了咐刨；而且類似于合并兩個(gè)鏈表的操作就更加省力了昙衅，只需將一個(gè)表尾和另一個(gè)表首鏈接，去掉頭就好了定鸟。

Q：在上一節(jié)中的鏈表實(shí)現(xiàn)中绒尊，我們用 node.next? 來判斷鏈表是否到了表尾、鏈表是否為空仔粥。但是循環(huán)鏈表的 next 一定不為空 （循環(huán)嘛）婴谱，我們怎么判斷呢？

圖 2 空的循環(huán)鏈表

如圖 2 所示麦向，當(dāng)循環(huán)鏈表為空的時(shí)候瘟裸，頭結(jié)點(diǎn)的指針域（next）指向頭結(jié)點(diǎn)自己，構(gòu)成循環(huán)诵竭。但是尾結(jié)點(diǎn)呢话告？沒錯(cuò)，尾結(jié)點(diǎn)就是頭結(jié)點(diǎn)卵慰。所以就有了如下的判斷條件：

1. head.next == head;
2. rear.next == rear; //head == rear

第一種情況我們已經(jīng)說明了沙郭，就是頭結(jié)點(diǎn)的指針域（next）指向頭結(jié)點(diǎn)自己；
第二種情況就是裳朋， 鏈表為空的時(shí)候病线，頭結(jié)點(diǎn)就是尾結(jié)點(diǎn)（沒明白的同學(xué)好好理解，反正我這蠢人鲤嫡，理解了半天才反應(yīng)過來...）送挑，也可以說是頭尾重合了，那么鏈表為空暖眼。

我發(fā)現(xiàn)使用 Objective-C 來實(shí)現(xiàn)循環(huán)鏈表感覺真心有點(diǎn)煩惕耕。原因有如下兩點(diǎn)：

1. 因?yàn)檠h(huán)鏈表是個(gè)環(huán)，大家肯定也很容易想到循環(huán)引用诫肠，對的司澎，我們要處理保留環(huán)；
2. 因?yàn)橛梦步Y(jié)點(diǎn)來表示循環(huán)鏈表区赵，所以惭缰，我們在插入、刪除笼才、整表創(chuàng)建的時(shí)候都要去修改尾結(jié)點(diǎn)，但是像上一節(jié)中的鏈表那樣直接把鏈表本身看成頭結(jié)點(diǎn)就不行了络凿，因?yàn)闆]辦法修改 self （即 self = node 是不允許的）骡送。

循環(huán)鏈表的實(shí)現(xiàn)

來看代碼吧：

循環(huán)鏈表 header：

/// 循環(huán)鏈表還是繼承于線性表昂羡，其實(shí)現(xiàn)中的 node 也是用的昨天的 node。如果有沒看到摔踱，或者沒看的同學(xué)虐先，傳送門在這里(本來是想寫在代碼中的，不過貌似有點(diǎn)沖突.. 就提出來了)派敷。

#import "CHRLinearList.h"

@interface CHRSinglyCircularLinkedList : CHRLinearList
@end

循環(huán)鏈表實(shí)現(xiàn)：

#import "CHRSinglyCircularLinkedList.h"
#import "CHRSinglyLinkedListNode.h"

@interface CHRSinglyCircularLinkedList ()

@property (nonatomic, strong) CHRSinglyLinkedListNode *rear; /// 這里的 rear 是指尾結(jié)點(diǎn)蛹批，如果鏈表為空， rear 和 頭結(jié)點(diǎn) head 就重合了篮愉，也就是說當(dāng)鏈表為空腐芍， rear == head

@property (nonatomic, assign) NSUInteger count; /// 個(gè)數(shù)，在循環(huán)鏈表的實(shí)現(xiàn)中试躏，每次鏈表長度的修改猪勇，都去計(jì)算了 count 值 ， 而不是每次都去遍歷整個(gè)表才能得到 count颠蕴，提高了 count 的查詢效率

@end

@implementation CHRSinglyCircularLinkedList

///  合成屬性 count
@synthesize count = _count;

- (void)dealloc
{
  /* 
      重寫了 dealloc泣刹， 打破保留環(huán)
      如果不明白為什么的同學(xué)，自己查文檔吧犀被，傳送門都不給了 
    */
  _rear.next = nil;
}

- (nonnull instancetype)initWithObjects:(nullable id)objects,...
{
  self = [super init];
  if (self) {
    
    /* 
      整表創(chuàng)建的時(shí)候椅您，和鏈表很相似，大概就是  
      
      1. 如果有數(shù)據(jù)寡键，構(gòu)造結(jié)點(diǎn)襟沮，把數(shù)據(jù)包裝到結(jié)點(diǎn)中
      2. prior 是上一個(gè)結(jié)點(diǎn)，讓上一個(gè)結(jié)點(diǎn)的指針域 next 指向新的結(jié)點(diǎn)
      3. 更新 prior 為新的結(jié)點(diǎn)

      直到循環(huán)結(jié)束昌腰， prior 結(jié)點(diǎn)已經(jīng)變成了 rear 結(jié)點(diǎn)开伏，如果鏈表是空的，那么 prior 既是 head 也是 rear遭商， 也就是空鏈表了
      對了固灵，千萬別忘記 rear.next = head， 構(gòu)成循環(huán)
    */
    
    _count = 0; /// 初始化 count 為0劫流，表中什么都沒有
    
    id <CHRSinglyLinkedListNodeProtocol> head = [[CHRSinglyLinkedListNode alloc] init]; /// 頭指針
    id <CHRSinglyLinkedListNodeProtocol> prior = head;
    
    va_list params;
    va_start(params, objects);
    id object = objects;
    
    while (object) {
      CHRSinglyLinkedListNode *node = [[CHRSinglyLinkedListNode alloc] init];
      node.data = object;
      prior.next = node;
      prior = node;
      _count++;
      object = va_arg(params, id);
    }
    
    va_end(params);
    
    _rear = prior;
    _rear.next = head; 
  }
  return self;
}

- (BOOL)isEmpty
{
  /// 判空條件巫玻，如果 rear.next (head) == rear， 鏈表為空祠汇，頭尾重合了
  return self.rear.next == self.rear;
}

- (NSUInteger)indexOfObject:(id)object
{
  /*
      聲明一個(gè) index 為 0
      找到頭結(jié)點(diǎn)
      聲明一個(gè) node 指針指向頭結(jié)點(diǎn)
      如果頭尾沒有重合仍秤，開始循環(huán)
      
      如果 node (頭結(jié)點(diǎn)).next.data 等同于 object， 也就是第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域如果與 object 相同可很，那么返回 index(0) 
      如果不相同诗力， index 自增，進(jìn)入下次循環(huán)
      ...
      
      如果在鏈表中存在 Object我抠，那么在上面的鏈表的遍歷中苇本，就已經(jīng)返回了 index
      如果過了循環(huán)還沒有返回袜茧，說明鏈表中不存在與這個(gè) object 等同的數(shù)據(jù)，那么返回 NSNotFound
  */
  NSUInteger index = 0;
  id <CHRSinglyLinkedListNodeProtocol> node = self.rear.next;
  while (node != self.rear) {
    node = node.next;
    if ([node.data isEqual:object]) {
      return index;
    }
    index++;
  }
  return NSNotFound;
}

- (id)objectAtIndex:(NSUInteger)index
{
  /// 如果給定的 index 超出了鏈表的范圍瓣窄，崩潰
  NSAssert(index < self.count, @"%s, %d 線性表越界笛厦， 當(dāng)前線性表共有 %@ 個(gè)元素",  __FILE__, __LINE__, @(self.count));
  
  id <CHRSinglyLinkedListNodeProtocol> node = self.rear.next.next;
  NSUInteger ctrIndex = 0;
  while (ctrIndex < index) {
    node = node.next;
    ctrIndex++;
  }

  return node.data;
}

- (void)insertObject:(id)object atIndex:(NSUInteger)index
{
  NSAssert(object, @"%s, %d, 向線性表中插入了 nil 是不允許的", __FILE__, __LINE__);
  NSAssert(index <= self.count, @"%s, %d 線性表越界， 當(dāng)前線性表共有 %@ 個(gè)元素",  __FILE__, __LINE__, @(self.count));
  
  ///  如果上面斷言成功俺夕，那么就是合法的插入
  
  id <CHRSinglyLinkedListNodeProtocol> prior = self.rear.next;
  NSUInteger ctrIndex = 0;
  
  while (ctrIndex < index) {
    prior = prior.next;
    ctrIndex++;
  }
  
  CHRSinglyLinkedListNode *node = [[CHRSinglyLinkedListNode alloc] init];
  node.data = object;
  
  node.next = prior.next;
  prior.next = node;
  
  self.count++; /// 更新 count
  
  /// 插入操作和鏈表幾乎一致裳凸，需要注意的是，有判斷是否要更新 尾結(jié)點(diǎn)（self.rear）劝贸，因?yàn)橛脩粲锌赡茉诒砦膊迦?  /*  
      有的同學(xué)可能會擔(dān)心如果 prior 是尾結(jié)點(diǎn)了姨谷，那么循環(huán)怎么處理呢？不用擔(dān)心悬荣，看下我的分析
      如果 prior 是尾結(jié)點(diǎn)菠秒，那么 node.next = prior.next，這個(gè)時(shí)候新插入的結(jié)點(diǎn)的指針域 next 指向 prior 的 next 也就是頭結(jié)點(diǎn)
      然后我們這樣 prior.next = node 氯迂，打破了原來尾結(jié)點(diǎn)的環(huán)践叠，讓尾結(jié)點(diǎn)的指針域指向新的結(jié)點(diǎn)，構(gòu)成循環(huán)
  */
  
  if (prior == self.rear) { /// 更新 rear 指針
    self.rear = node;
  }
}

- (id)removeObjectAtIndex:(NSUInteger)index
{
  ///  刪除和插入差不多嚼蚀，我就不多說了禁灼，相信好好看的同學(xué)，已經(jīng)看懂了
  NSAssert(index < self.count, @"%s, %d 線性表越界轿曙， 當(dāng)前線性表共有 %@ 個(gè)元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  
  id <CHRSinglyLinkedListNodeProtocol> prior = self.rear.next;
  
  while (ctrIndex < index) {
    prior = prior.next;
    ctrIndex++;
  }
  
  id <CHRSinglyLinkedListNodeProtocol> node = prior.next; /// 要刪除的節(jié)點(diǎn)
  prior.next = node.next;
  node.next = nil;
  
  self.count--;
  
  if (node == self.rear) { /// 更新尾指針
    self.rear = prior;
  }
  
  return node.data;
}

- (BOOL)containsObject:(id)object
{
  ///  這個(gè)也就不說了吧弄捕，遍歷整張表，如果結(jié)點(diǎn)的數(shù)據(jù)域 data 等同于 object 导帝，理解返回 YES守谓；如果循環(huán)結(jié)束，沒有返回您单，那么說明不包含 object 斋荞， 返回 NO
  id <CHRSinglyLinkedListNodeProtocol> node = self.rear.next;
  while (node != self.rear) {
    node = node.next;
    if ([node.data isEqual:object]) {
      return YES;
    }
  }
  return NO;
}

- (void)removeAllObjects
{
  ///  找到頭結(jié)點(diǎn) head
  id <CHRSinglyLinkedListNodeProtocol> head = self.rear.next;
  
  /*
      我這邊是這樣的思路
  
      一直刪除第一個(gè)結(jié)點(diǎn)， 也就是 head.next（就算 head.next 是尾結(jié)點(diǎn)虐秦，那么 head.next = node.next 平酿， 也就變成了空鏈表的情況，如圖 2 ）
      然后除了循環(huán)之后悦陋， 更新 rear 和 count
  */
  while (head != head.next) {
    id <CHRSinglyLinkedListNodeProtocol> node = head.next; /// 要刪除的節(jié)點(diǎn)
    head.next = node.next;
    node.next = nil;
  }
  self.rear = head;
  self.count = 0;
}

@end

End

大概的代碼就是這些蜈彼，相信思路大家已經(jīng)有了大致了解，我覺得只要整整理解了空表的情況俺驶， 也就是 rear == head == read.next 幸逆，那么就應(yīng)該很好理解了。我在看書的時(shí)候，看懵逼了好多遍秉颗， 實(shí)現(xiàn)了三天痢毒，才真正理解了送矩，唉蚕甥，我這麻瓜。

對了栋荸，劇透一下菇怀，現(xiàn)在我們實(shí)現(xiàn)了 鏈表、循環(huán)鏈表晌块， 但是爱沟，我們實(shí)現(xiàn)的是單（向）鏈表。既然有單向鏈表匆背，那么就有雙向鏈表咯呼伸，其實(shí)很簡單，雙向鏈表就是加一個(gè)指針域 prior 钝尸，使用起來更加靈活括享，某些時(shí)候可以達(dá)到更高的效率，我的理解就是用空間來換時(shí)間珍促。雙鏈表也可以循環(huán)铃辖，其實(shí)道理很類似，我們下一篇再說猪叙。

還有娇斩，這篇昨天寫了一半，今天上午寫了一半穴翩，可能有一些思路斷掉了犬第，看不懂，或者有錯(cuò)誤的話芒帕，大家請指正歉嗓。本文的代碼，還是放在那個(gè)倉庫中副签，歡迎大家測試遥椿，找 bug ，尤其是內(nèi)存問題淆储。

好了冠场，先到這里了...
Im Chris, bye ~~