前言

昨天说了线性表中的链表，相信仔细看过的同学应该会明白 链 的思想，今天我们来说一说循环链表。

定义

什么是循环链表呢？

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。

图 1 循环链表示意图

我们让链表中的最后一个结点，指向头结点。这样链表就成了一个环（对于内存管理比较熟悉的同学也许已经感觉到了坏味道，因为形成了环，我的思路是，我们打破这个环就好了，而且，我们的主题是数据结构，思想为主）。

Q：使链表循环，或者说头尾相接的的好处是什么呢？

好处就是从循环链表中的任何一个结点出发都能找到任何其他结点。使用起来更加灵活。比如说，我们现在的链表，查找第一个结点，只需要 O(1) 的时间，查找最后一个结点需要 O(n) 的时间，但是相信虽然我还没写到栈和队列，大家也都知道栈和队列的原理。如果一个链表经常要对第一个结点和最后一个结点进行操作，比如栈和队列，那么我们之前实现的链表就不是很合理，因为获取最后一个结点的时间复杂度有点高。

Q：说了这么多，这和循环链表到底有什么关系呢？

我们这里还是需要换个思路，用循环链表来解决这个问题。我们用最后一个结点来表示链表，最后一个结点的 next 称为尾指针。比如说图 1 中的最后一个结点是 node9 ， node9 有数据域 data = 9， 指针域 next = 头结点，那么 node9 就是尾结点 rear ，尾指针就是 rear.next (node9.next) ，也就是头结点了。

通过这种表示方法，我们在获取第一个结点的时候，只需要通过 rear.next.next（node9.next.next => 头结点.next）就可以找到第一个结点；通过 rear 就可以找到最后一个结点，因为 rear 就是最后一个结点（node9）啦。所以，这种表示方法，可以使获取第一个结点和最后一个结点的时间复杂度为 O(1) 常数项。这样，我们在用链表实现栈和队列的时候，例如获取栈顶、栈底、队头、队尾等操作，我们可以以较高的效率来完成，而不是每次去遍历整个表，这样太浪费了；而且类似于合并两个链表的操作就更加省力了，只需将一个表尾和另一个表首链接，去掉头就好了。

Q：在上一节中的链表实现中，我们用 node.next? 来判断链表是否到了表尾、链表是否为空。但是循环链表的 next 一定不为空 （循环嘛），我们怎么判断呢？

图 2 空的循环链表

如图 2 所示，当循环链表为空的时候，头结点的指针域（next）指向头结点自己，构成循环。但是尾结点呢？没错，尾结点就是头结点。所以就有了如下的判断条件：

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

第一种情况我们已经说明了，就是头结点的指针域（next）指向头结点自己；
第二种情况就是， 链表为空的时候，头结点就是尾结点（没明白的同学好好理解，反正我这蠢人，理解了半天才反应过来...），也可以说是头尾重合了，那么链表为空。

我发现使用 Objective-C 来实现循环链表感觉真心有点烦。原因有如下两点：

1. 因为循环链表是个环，大家肯定也很容易想到循环引用，对的，我们要处理保留环；
2. 因为用尾结点来表示循环链表，所以，我们在插入、删除、整表创建的时候都要去修改尾结点，但是像上一节中的链表那样直接把链表本身看成头结点就不行了，因为没办法修改 self （即 self = node 是不允许的）。

循环链表的实现

来看代码吧：

循环链表 header：

/// 循环链表还是继承于线性表，其实现中的 node 也是用的昨天的 node。如果有没看到，或者没看的同学，传送门在这里(本来是想写在代码中的，不过貌似有点冲突.. 就提出来了)。

#import "CHRLinearList.h"

@interface CHRSinglyCircularLinkedList : CHRLinearList
@end

循环链表实现：

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

@interface CHRSinglyCircularLinkedList ()

@property (nonatomic, strong) CHRSinglyLinkedListNode *rear; /// 这里的 rear 是指尾结点，如果链表为空， rear 和 头结点 head 就重合了，也就是说当链表为空， rear == head

@property (nonatomic, assign) NSUInteger count; /// 个数，在循环链表的实现中，每次链表长度的修改，都去计算了 count 值 ， 而不是每次都去遍历整个表才能得到 count，提高了 count 的查询效率

@end

@implementation CHRSinglyCircularLinkedList

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

- (void)dealloc
{
  /* 
      重写了 dealloc， 打破保留环
      如果不明白为什么的同学，自己查文档吧，传送门都不给了 
    */
  _rear.next = nil;
}

- (nonnull instancetype)initWithObjects:(nullable id)objects,...
{
  self = [super init];
  if (self) {
    
    /* 
      整表创建的时候，和链表很相似，大概就是  
      
      1. 如果有数据，构造结点，把数据包装到结点中
      2. prior 是上一个结点，让上一个结点的指针域 next 指向新的结点
      3. 更新 prior 为新的结点

      直到循环结束， prior 结点已经变成了 rear 结点，如果链表是空的，那么 prior 既是 head 也是 rear， 也就是空链表了
      对了，千万别忘记 rear.next = head， 构成循环
    */
    
    _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
{
  /*
      声明一个 index 为 0
      找到头结点
      声明一个 node 指针指向头结点
      如果头尾没有重合，开始循环
      
      如果 node (头结点).next.data 等同于 object， 也就是第一个结点的数据域如果与 object 相同，那么返回 index(0) 
      如果不相同， index 自增，进入下次循环
      ...
      
      如果在链表中存在 Object，那么在上面的链表的遍历中，就已经返回了 index
      如果过了循环还没有返回，说明链表中不存在与这个 object 等同的数据，那么返回 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 线性表越界， 当前线性表共有 %@ 个元素",  __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 线性表越界， 当前线性表共有 %@ 个元素",  __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
  
  /// 插入操作和链表几乎一致，需要注意的是，有判断是否要更新 尾结点（self.rear），因为用户有可能在表尾插入
  /*  
      有的同学可能会担心如果 prior 是尾结点了，那么循环怎么处理呢？不用担心，看下我的分析
      如果 prior 是尾结点，那么 node.next = prior.next，这个时候新插入的结点的指针域 next 指向 prior 的 next 也就是头结点
      然后我们这样 prior.next = node ，打破了原来尾结点的环，让尾结点的指针域指向新的结点，构成循环
  */
  
  if (prior == self.rear) { /// 更新 rear 指针
    self.rear = node;
  }
}

- (id)removeObjectAtIndex:(NSUInteger)index
{
  ///  删除和插入差不多，我就不多说了，相信好好看的同学，已经看懂了
  NSAssert(index < self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __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; /// 要删除的节点
  prior.next = node.next;
  node.next = nil;
  
  self.count--;
  
  if (node == self.rear) { /// 更新尾指针
    self.rear = prior;
  }
  
  return node.data;
}

- (BOOL)containsObject:(id)object
{
  ///  这个也就不说了吧，遍历整张表，如果结点的数据域 data 等同于 object ，理解返回 YES；如果循环结束，没有返回，那么说明不包含 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
{
  ///  找到头结点 head
  id <CHRSinglyLinkedListNodeProtocol> head = self.rear.next;
  
  /*
      我这边是这样的思路
  
      一直删除第一个结点， 也就是 head.next（就算 head.next 是尾结点，那么 head.next = node.next ， 也就变成了空链表的情况，如图 2 ）
      然后除了循环之后， 更新 rear 和 count
  */
  while (head != head.next) {
    id <CHRSinglyLinkedListNodeProtocol> node = head.next; /// 要删除的节点
    head.next = node.next;
    node.next = nil;
  }
  self.rear = head;
  self.count = 0;
}

@end

End

大概的代码就是这些，相信思路大家已经有了大致了解，我觉得只要整整理解了空表的情况， 也就是 rear == head == read.next ，那么就应该很好理解了。我在看书的时候，看懵逼了好多遍， 实现了三天，才真正理解了，唉，我这麻瓜。

对了，剧透一下，现在我们实现了 链表、循环链表， 但是，我们实现的是单（向）链表。既然有单向链表，那么就有双向链表咯，其实很简单，双向链表就是加一个指针域 prior ，使用起来更加灵活，某些时候可以达到更高的效率，我的理解就是用空间来换时间。双链表也可以循环，其实道理很类似，我们下一篇再说。

还有，这篇昨天写了一半，今天上午写了一半，可能有一些思路断掉了，看不懂，或者有错误的话，大家请指正。本文的代码，还是放在那个仓库中，欢迎大家测试，找 bug ，尤其是内存问题。

好了，先到这里了...
Im Chris, bye ~~