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

作者: Chrisss | 来源:发表于2016-08-12 19:11 被阅读300次

前言

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

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~

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

前言

双链表

定义

代码实现

循环双链表

代码实现

End

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

面试题之算法知识

链表