线性表（双向（循环）链表）

前言

在之前的文章中， 大家还记得我的链表和结点、结点协议的名字么？

1.CHRSinglyLinkedListNodeProtocol
2.CHRSinglyLinkedListNode
3.CHRSinglyLinkedList
4.CHRSinglyCircularLinkedList

细心的朋友应该还记得我说的 Singly ，配合 LinkedList ，翻译过来就是 单向链表结点协议、单向链表结点、单向链表和单向循环链表 了。为什么说是单向的呢？ 很简单，因为我们的链表是 **head -> 0 -> 1 -> ... -> n ** 的，每一个结点只知道下一个结点 next 。

如果说我已经知道了一个结点 m （0 <= m <= n），我想找到 m - 1 的结点呢？ 那么我们就要遍历一遍链表，用之前的指针，找到 m 的 prior 结点。 WTF ，这也太不灵活了，如果我的链表有 1000 W 个结点，m = 999,9999那遍历一次成本也太高了啊，要执行 m - 1 次。有没有灵活一点的办法呢？

请看今天的走进科学，啊呸， 双向链表 吧。（也叫双链表）

双链表

定义

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

我们来看图吧，别被这定义吓到了，见图 1 。
图 1 双链表示意图

大家注意，这里的一条直线是指逻辑上的，内存中的顺序无所谓，也就是理解 链 的思想。

首先把虚线部分去掉来看，和单链表一样，就是多了一个前驱（prior） ，指向每一个结点的前一个结点。头结点也有 prior 结点，只是 prior 为 nil， 就像结点 5 也有后继结点 next ， next 为 nil 一样，避免图太长，懒着画了。

Q：结点 4 的前驱结点 prior 和 后继结点 next 分别是？
**A：结点 3 、结点5 **

Q：结点 0 的前驱结点 prior 和 后继结点 next 分别是？
**A：结点 head 、结点 1 **

Q：结点 5 的前驱结点 prior 和 后继结点 next 分别是？
**A：结点 4 、nil **

Q：头结点的前驱结点 prior 和 后继结点 next 分别是？
**A：nil 、结点 0 **

相信看完了上面一连串的 QA 之后，大家已经明白了，所有的结点相同对待这个道理，也许在单链表的章节就懂了，恕我啰嗦。

接下来我们分析下各种情况：

1. 双链表空表
分析：
双链表空表的时候，和单链表几乎一样，就只有一个头结点， 头结点的指针域 next 、prior 都为 nil 。

2. 向双链表中插入一条数据
我们来看图说话。

图 2 空链表插入前

图 3 空链表插入后

分析：
先来看图 2 ，头结点的前驱 prior 为 nil， 就没有画出来，后继 next 也为 nil ，和单链表差不多，在插入前，先构造一个新的结点，把数据包装到数据域 data 。也就是图中的结点 0 做的事情， 构造一个结点， 把 0 塞进去，结点 0 的前驱 piror 和后继 next 都为 nil 。

然后我们来看图 3 ，插入到链表后， 头结点的 next 指向 结点 0 ，结点 0 的前驱指向头结点。

Q：那么如果是中间结点和尾结点呢？

尾结点和空表插入的操作不是一毛一样么？大家想想看。
中间结点还有处理一个问题，就是处理新插入结点的后继，把链连接好。
例如：向图 3 中 0 位置，插入数据 x 。

  • 我们先构造一个结点， 把 x 包装到结点中，我们叫这个结点为结点 X ；
  • 结点 X 的前驱指向头结点；
  • 结点 X 的后继指向头结点的后继（结点 0 ）；
  • 头结点的后继结点（结点 0）的前驱指向结点 X;
  • 头结点的后继指向 X。

有点绕？我们还是来看张图吧，本来不想画了... 示意见图 4。
图 4 插入示意图

其实 步骤3 和步骤 4 没什么，主要是步骤 1 和步骤 2的顺序，和单链表类似，如果先做了步骤 2 ，那么结点 0 后面的链就挂了。

那么如果是表尾插入呢？其实是一样的，用 Objective-C 来解释就是，如果插入的是表为，也就是图 4 中的结点 0 为 nil，那么结点的数据域和指针域都为 nil，对 nil 的操作的安全的。

3. 从双链表中删除一条数据
分析：
插入理解了，删除就更好理解了，我就不多说了，扔张图，见图 5。

图 5 双链表删除结点示意图

如果说要删除结点 2 的话，这个感觉就简单很多了：

  • 让结点 1 的后继指向结点 3；
  • 结点 3 的前驱指向结点 1；
  • 干掉结点 2 。

删除第一个结点和删除最后一个结点，头结点和尾结点可以一样处理，和插入类似， 对 nil 操作是安全的，逻辑上 nil 是链表的结束。

代码实现

说了这么多，来看看代码实现吧，一点都不复杂...

双链表结点协议

#import <Foundation/Foundation.h>

@protocol CHRDoubleLinkedListNodeProtocol <NSObject>

@property (nonatomic, weak, readwrite, nullable) id <CHRDoubleLinkedListNodeProtocol> prior; /// next 来保留引用就好了， prior 就直接使用 weak 了
@property (nonatomic, strong, readwrite, nullable) id <CHRDoubleLinkedListNodeProtocol> next;
@property (nonatomic, strong, readwrite, nullable) id data;

@end

双链表结点 header

#import "CHRDoubleLinkedListNodeProtocol.h"

@interface CHRDoubleLinkedListNode : NSObject <CHRDoubleLinkedListNodeProtocol>
@end

双链表结点 implementation

#import "CHRDoubleLinkedListNode.h"

@interface CHRDoubleLinkedListNode ()
{
  id <CHRDoubleLinkedListNodeProtocol> _next;
  id <CHRDoubleLinkedListNodeProtocol> __weak _prior;
  id data;
}

@end

@implementation CHRDoubleLinkedListNode

@synthesize next = _next;
@synthesize prior = _prior;
@synthesize data = _data;

@end

双链表 header

#import "CHRLinearList.h"

@interface CHRDoubleLinkedList : CHRLinearList
@end

双链表 implementation

#import "CHRDoubleLinkedList.h"
#import "CHRDoubleLinkedListNode.h"

@interface CHRDoubleLinkedList () <CHRDoubleLinkedListNodeProtocol>
{
  id <CHRDoubleLinkedListNodeProtocol> _next;
  id <CHRDoubleLinkedListNodeProtocol> __weak _prior;
  id data;
}

@property (nonatomic, assign) NSUInteger count;

@end

@implementation CHRDoubleLinkedList

@synthesize next = _next;
@synthesize prior = _prior;
@synthesize data = _data;
@synthesize count = _count;

- (instancetype)initWithObjects:(id)objects, ...
{
  self = [super init];
  if (self) {
    
    _count = 0;
    
    id <CHRDoubleLinkedListNodeProtocol> prior = self; /// self 是 头结点
    
    id object = objects;
    va_list params;
    va_start(params, objects);
    
    while (object) {
      // 构造新的结点，并将数据 object 包装到 node 中
      id <CHRDoubleLinkedListNodeProtocol> node = [[CHRDoubleLinkedListNode alloc] init];
      node.data = object;
      
      prior.next = node;
      node.prior = prior;
      
      prior = node; /// 更新 prior
      _count++; /// 更新 count
      
      object = va_arg(params, id); /// 更新 object
    }
    
    va_end(params);
    
  }
  return self;
}

- (BOOL)isEmpty
{
  return !self.next;
}

- (id)objectAtIndex:(NSUInteger)index
{
  /// 断言 index 没有越界
  /// self.count 不向单链表中，是遍历得到，耗费时间。所以，这里直接用 self.count 断言
  NSAssert(index < self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  id <CHRDoubleLinkedListNodeProtocol> node = self.next;
  while (ctrIndex < index) {
    node = node.next; /// 更新 node
    ctrIndex++; /// 自增 ctrIndex
  }
  
  return node.data;
}

- (NSUInteger)indexOfObject:(id)object
{
  /// 与单链表相同了，只需要一个 后继指针 next 就可以搞定
  NSUInteger index = 0;
  id <CHRDoubleLinkedListNodeProtocol> node = self.next;
  while (node) {
    if ([node.data isEqual:object]) {
      return index;
    }
    node = node.next;
    index++;
  }
  return NSNotFound;
}

- (void)insertObject:(id)object atIndex:(NSUInteger)index
{
  /// 断言 object 非空
  NSAssert(object, @"%s, %d, 向线性表中插入了 nil 是不允许的", __FILE__, __LINE__);
  /// self.count 不向单链表中，是遍历得到，耗费时间。所以，这里直接用 self.count 断言
  NSAssert(index <= self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  
  id <CHRDoubleLinkedListNodeProtocol> prior = self;
  while (ctrIndex < index) {
    prior = prior.next;
    ctrIndex++;
  }
  
  CHRDoubleLinkedListNode *node = [[CHRDoubleLinkedListNode alloc] init];
  node.data = object;
  
  node.prior = prior;
  node.next = prior.next;
  prior.next.prior = node;
  prior.next = node;
  
  self.count++; /// 更新 count
}

- (id)removeObjectAtIndex:(NSUInteger)index
{
  /*
      这里的 node 是要删除的结点
      而单链表中是要删除结点的前驱
      因为双向，所以可以很容易的找到自己的前驱，前驱的前驱、后继、后继的后继 and so on...
      这里直接找自己就好了
   */
  NSAssert(index < self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  id <CHRDoubleLinkedListNodeProtocol> node = self.next;
  while (ctrIndex < index) {
    node = node.next; /// 更新 node
    ctrIndex++; /// 自增 ctrIndex
  }
  
  node.prior.next = node.next;
  node.next.prior = node.prior;
  
  node.next = nil; /// 把 node.next 置空
  node.prior = nil; // 因为 prior 是 weak， 所以，理论上是不用管的，不过为了安全，万一以后有人改你的代码呢，一个不注意可能出问题，把感觉潜在的风险扼杀在摇篮中吧
  
  self.count--; /// 更新 count
  
  return node.data;
}

- (BOOL)containsObject:(id)object
{
  /// 和单链表一样
  id <CHRDoubleLinkedListNodeProtocol> node = self.next;
  
  while (node) {
    if ([node.data isEqual:object]) {
      return YES;
    }
    node = node.next;
  }
  return NO;
}

- (void)removeAllObjects
{
  id <CHRDoubleLinkedListNodeProtocol> head = self;
  
  @autoreleasepool {
    while (head.next) {
      id <CHRDoubleLinkedListNodeProtocol> node = head.next; /// 要删除的结点（一直删除第一个结点）
      node.prior.next = node.next;
      node.next.prior = node.prior;
      node.prior = nil;
      node.next = nil;
    }
  }
  
  self.count = 0;
}

@end

循环双链表

其实双链表并不是很常用，我们一般写双链表一般写循环双链表，其实就是在形成个闭环后，处理下循环引用。

双链表成了环的话，那么我们可以很容易的通过头结点的前驱 prior 找到尾结点，所以时间复杂度就是 O(1) 了，空间换算时间，确实很容易想，也好实现 。

我们来看下示意图，如图 6（用 Numbers 画图真难受...）。
图 6 双循环链表示意图

其实就是在图 1 的基础上加了一根实线，一根虚线，让结点 5 的 next 指向头结点；头结点的 prior 指向结点 5 。

我们来分析下各种情况吧：

1. 空表
如图 7 所示，头结点的 next 指向头结点自己，头结点的 prior 也指向自己。

图 7 双循环链表空表示意图

2. 向双循环链表插入数据
其实插入数据和双向链表操作一样，不需要像用尾结点表示的单循环链表，要更新 rear。这里图就不画了，大家多动脑。

3. 从双循环链表删除数据
删除和插入类似，和双向链表删除数据操作相同，同理不说了（大家自己一定考虑清楚，尤其是边界值）。

代码实现

#import "CHRDoubleCircularLinkedList.h"
#import "CHRDoubleLinkedListNode.h"

@interface CHRDoubleCircularLinkedList ()

@property (nonatomic, strong) CHRDoubleLinkedListNode *head;
@property (nonatomic, assign) NSUInteger count;

@end

@implementation CHRDoubleCircularLinkedList

@synthesize count = _count;

- (void)dealloc
{
  /// 打破保留环，方式和单循环链表相同
  
  _head.prior.next = nil;
}

- (instancetype)initWithObjects:(id)objects, ...
{
  self = [super init];
  if (self) {
    
    _count = 0;
    _head = [[CHRDoubleLinkedListNode alloc] init];
    
    id <CHRDoubleLinkedListNodeProtocol> prior = _head; /// self.head 是 头结点
    
    id object = objects;
    va_list params;
    va_start(params, objects);
    
    while (object) {
      // 构造新的结点，并将数据 object 包装到 node 中
      id <CHRDoubleLinkedListNodeProtocol> node = [[CHRDoubleLinkedListNode alloc] init];
      node.data = object;
      
      prior.next = node;
      node.prior = prior;
      
      prior = node; /// 更新 prior
      _count++; /// 更新 count
      
      object = va_arg(params, id); /// 更新 object
    }
    
    va_end(params);
    
    /// 上面操作和双链表一样， 我们要使双链表循环， 升级为双向循环链表
    
    prior.next = _head; /// prior 到这里已经是尾结点了，就算是空表，尾结点就是 self.head，头尾重合咯
    _head.prior = prior;
  }
  return self;
}

- (BOOL)isEmpty
{
  /* 
   空链表的情况， 前驱(prior) 和后继 (next) 都指向头结点自己 (self.head)
   维基百科上是这样写的:
      return self.head.prior == self && self.head.next == self.head
   这里用一个指针就可以判断，所以我就没有 && self.head.prior == self.head 了
   */
  return self.head.next == self.head;
}

- (id)objectAtIndex:(NSUInteger)index
{
  /// 和双链表操作一样
  
  NSAssert(index < self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  id <CHRDoubleLinkedListNodeProtocol> node = self.head.next;
  while (ctrIndex < index) {
    node = node.next;
    ctrIndex++;
  }
  
  return node.data;
}

- (NSUInteger)indexOfObject:(id)object
{
  /// 与单链表相同了，只需要一个 后继指针 next 就可以搞定
  NSUInteger index = 0;
  id <CHRDoubleLinkedListNodeProtocol> node = self.head.next;
  while (node != self.head) {
    if ([node.data isEqual:object]) {
      return index;
    }
    node = node.next;
    index++;
  }
  return NSNotFound;
}

- (void)insertObject:(id)object atIndex:(NSUInteger)index
{
  /// 插入同双链表
  NSAssert(object, @"%s, %d, 向线性表中插入了 nil 是不允许的", __FILE__, __LINE__);
  NSAssert(index <= self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  
  id <CHRDoubleLinkedListNodeProtocol> prior = self.head;
  while (ctrIndex < index) {
    prior = prior.next;
    ctrIndex++;
  }
  
  CHRDoubleLinkedListNode *node = [[CHRDoubleLinkedListNode alloc] init];
  node.data = object;
  
  node.prior = prior;
  node.next = prior.next;
  prior.next.prior = node;
  prior.next = node;
  
  self.count++;
}

- (id)removeObjectAtIndex:(NSUInteger)index
{
  /// 删除同双链表
  NSAssert(index < self.count, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素",  __FILE__, __LINE__, @(self.count));
  
  NSUInteger ctrIndex = 0;
  id <CHRDoubleLinkedListNodeProtocol> node = self.head.next;
  while (ctrIndex < index) {
    node = node.next;
    ctrIndex++;
  }
  
  node.prior.next = node.next;
  node.next.prior = node.prior;
  
  node.next = nil;
  node.prior = nil;
  
  self.count--;
  
  return node.data;
}

- (BOOL)containsObject:(id)object
{
  /// 和单链表一样
  id <CHRDoubleLinkedListNodeProtocol> node = self.head.next;
  
  while (node != self.head) {
    if ([node.data isEqual:object]) {
      return YES;
    }
    node = node.next;
  }
  return NO;
}

- (void)removeAllObjects
{
  /// 同双链表
  
  id <CHRDoubleLinkedListNodeProtocol> head = self.head;
  
  @autoreleasepool {
    while (head.next != self.head) {
      id <CHRDoubleLinkedListNodeProtocol> node = head.next;
      node.prior.next = node.next;
      node.next.prior = node.prior;
      node.prior = nil;
      node.next = nil;
    }
  }
  
  self.count = 0;
}

@end

End

链表是基础中的基础，希望大家基础扎实。因为：

堆栈是用链表实现的、队列是用链表实现的
队列是用链表实现的、队列是用链表实现的
树，通过一定的变形用二叉树表示。二叉树可以总得来说，和链表也脱不开干系..

写的好累，放假要好好休息休息，尽可能的把 堆栈 和 队列 写完。
链的思想非常重要。比如说 iOS 中的响应链、树形结构中的每一条链、栈（导航控制器）、队列（比如 operation） and so on...
大家别忘记初中哈，我认为思想最重要，语言无所谓。

Im Chris. zZ~

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,524评论 5赞 460
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,869评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,813评论 0赞 320
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,210评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,085评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,117评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,533评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,219评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,487评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,582评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,362评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,218评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,589评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,899评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,176评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,503评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,707评论 2赞 335

推荐阅读更多精彩内容

  • 数据结构第4-2讲双向链表
    链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？ 可以...
    rainchxy阅读 1,897评论 0赞 6
  • 线性表复习和进阶学习
    大学的时候不好好学习，老师在讲台上讲课，自己在以为老师看不到的座位看小说，现在用到了老师讲的知识，只能自己看书查资...
    和珏猫阅读 1,427评论 1赞 3
  • 数据结构三(线性表)
    1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,014评论 6赞 15
  • 线性表及ArrayList/LinkedList源码分析总结
    一.线性表 定义:零个或者多个元素的有限序列。也就是说它得满足以下几个条件:  ①该序列的数据元素是有限的。  ②...
    Geeks_Liu阅读 2,667评论 1赞 12
  • 二. 数据结构之线性结构
    本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,844评论 0赞 7