单向循环链表是在单向链表的基础上，将最后一个节点的next指针指向链表的头节点。但是基于Objective-C内存管理的机制，这样会出现循环引用，所以最后一个节点指向头节点应该用弱引用。
循环链表的节点
循环单向链表需要比单向链表的节点多一个weakNext指向链表的头节点：
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface JKRSingleLinkedListNode : NSObject
@property (nonatomic, strong, nullable) id object;
@property (nonatomic, weak, nullable) JKRSingleLinkedListNode *weakNext;
@property (nonatomic, strong, nullable) JKRSingleLinkedListNode *next;
- (instancetype)init __unavailable;
+ (instancetype)new __unavailable;
- (instancetype)initWithObject:(nullable id)object next:(nullable JKRSingleLinkedListNode *)next;
@end
NS_ASSUME_NONNULL_END
为了便于拿到节点的下一个节点，这里在next的get方法中做了判断，如果next为空再去取weakNext，这样就可以通过获取next来拿到链表的下一个节点，不用去单独判断哪个为空的情况。所以这里需要注意的就是：一定要维护好weakNext和next，使得它们不能够同时有值，并且只能在应该不为空的时候有值。
- weakNext：当节点是链表最后一个节点的时候（包括链表只有一个节点的情况），weakNext指向链表的头节点（链表只有一个节点的时候指向自己），并且此时next为nil。
- next：当节点不是链表的最后一个节点的时候，next指向该节点的下一个节点，并且此时weakNext为nil。
#import "JKRSingleLinkedListNode.h"
@implementation JKRSingleLinkedListNode
- (instancetype)initWithObject:(id)object next:(JKRSingleLinkedListNode *)next {
self = [super init];
self.object = object;
self.next = next;
return self;
}
- (JKRSingleLinkedListNode *)next {
if (_next) {
return _next;
} else {
return _weakNext;
}
}
- (void)dealloc {
// NSLog(@"<%@: %p>: %@ dealloc", self.class, self, self.object);
}
- (NSString *)description {
NSString *tipString = @"";
// 这里是一个next和weakNext维护错误的提示，两个节点都有值即显示E (error)，代表指针维护有问题
if (_next && _weakNext) {
tipString = @"E ";
} else if (_weakNext) {
tipString = @"W ";
}
return [NSString stringWithFormat:@"%@ -> (%@%@)", self.object, tipString, self.next.object];
}
@end
添加节点
添加第一个节点
插入第一个节点时，需要将链表的_first指针指向创建的节点，并将节点的weakNext指向自己。
插入到链表头部
如图，要将一个新节点插入到链表的头部：
需要的操作如下图：
- 新节点的next指针指向原来的头节点。
- 尾节点的weakNext指向新节点。
- 头节点指针_first指向新的节点。
添加后链表的结构：
链表尾部追加一个节点
如图，要将一个新节点插入到链表的尾部：
需要的操作如下图：
- 原来尾节点的weakNext设为nil，原来尾节点的next指向新节点。
- 新节点的weakNext指向头节点。
插入到链表节点中间
如图，要将一个新节点插入到链表中已经存在的两个节点之间：
需要的操作如下图：
- 将插入位置的前一个节点的next指针指向新节点。
- 将新节点的next指针指向插入位置的原节点。
完成操作后的链表结构：
添加节点的代码
综上的添加逻辑，添加节点的代码如下：
- (void)insertObject:(id)anObject atIndex:(NSUInteger)index {
[self rangeCheckForAdd:index];
if (index == 0) { // 插入链表头部或添加第一个节点
JKRSingleLinkedListNode *node = [[JKRSingleLinkedListNode alloc] initWithObject:anObject next:_first];
JKRSingleLinkedListNode *last = (_size == 0) ? node : [self nodeWithIndex:_size - 1];
last.next = nil;
last.weakNext = node;
_first = node;
} else { // 插入到链表尾部或链表中间
JKRSingleLinkedListNode *prev = [self nodeWithIndex:index - 1];
JKRSingleLinkedListNode *node = [[JKRSingleLinkedListNode alloc] initWithObject:anObject next:prev.next];
prev.next = node;
prev.weakNext = nil;
if (node.next == _first) { // 插入到链表尾部
node.next = nil;
node.weakNext = _first;
}
}
_size++;
}
删除节点
删除当前唯一的节点
删除当前唯一的节点，只需要将_first设置为nil，节点就会自动被释放：
删除头节点
删除长度不为1的链表的头部节点，如下图：
- 将_first指向原来头节点的下一个节点。
- 将尾节点的weakNext指向新的头节点。
删除尾节点
删除链表尾部的节点如下图：
要删除尾部的节点，首先要先拿到链表尾部节点的上一个节点，并对其进行如下操作：
- 将尾节点的前一个节点的next设置为nil。
- 将尾节点的前一个节点的weakNext设置为头节点。
删除链表节点之间的节点
删除链表其他节点中间的节点如下图：
只需要找到被删除节点的前一个节点，并将它的next指向被删除节点的next即可：
删除节点的代码
综上所有情况，删除节点的代码为：
- (void)removeObjectAtIndex:(NSUInteger)index {
[self rangeCheckForExceptAdd:index];
JKRSingleLinkedListNode *node = _first;
if (index == 0) { // 删除头节点或者唯一的节点
if (_size == 1) { // 删除唯一的节点
_first = nil;
} else { // 删除头节点
JKRSingleLinkedListNode *last = [self nodeWithIndex:_size - 1];
_first = _first.next;
last.next = nil;
last.weakNext = _first;
}
} else { // 删除尾节点或中间的节点
JKRSingleLinkedListNode *prev = [self nodeWithIndex:index - 1];
node = prev.next;
if (node.next == _first) { // 删除尾节点
prev.next = nil;
prev.weakNext = _first;
} else { // 删除中间节点
prev.next = node.next;
prev.weakNext = nil;
}
}
_size--;
}
测试单向循环链表
测试对象Person
@interface Person : NSObject
@property (nonatomic, assign) NSInteger age;
+ (instancetype)personWithAge:(NSInteger)age;
@end
@implementation Person
+ (instancetype)personWithAge:(NSInteger)age {
Person *p = [Person new];
p.age = age;
return p;
}
- (void)dealloc {
NSLog(@"%@ dealloc", self);
}
- (NSString *)description {
return [NSString stringWithFormat:@"%zd", self.age];
}
添加第一个节点
首先为空的单向循环链表添加第一个节点：
JKRBaseList *list = [JKRSingleCircleLinkedList new];
[list addObject:[Person personWithAge:1]];
打印链表结果：
Size: 1 [1 -> (W 1)]
链表的weakNext指向自己。
插入到链表尾部
再添加一个元素到尾部：
[list addObject:[Person personWithAge:3]];
打印链表结果：
Size: 2 [1 -> (3), 3 -> (W 1)]
age为1的person对象通过强引用指向新的age为3的person对象，age为3的person对象通过弱引用指向age为1的person对象。
插入到链表中间
[list insertObject:[Person personWithAge:2] atIndex:1];
打印链表结果：
Size: 3 [1 -> (2), 2 -> (3), 3 -> (W 1)]
插入到链表头部
[list insertObject:[Person personWithAge:0] atIndex:0];
打印链表结果：
Size: 4 [0 -> (1), 1 -> (2), 2 -> (3), 3 -> (W 0)]
删除头节点
[list removeFirstObject];
打印链表结果：
0 dealloc
Size: 3 [1 -> (2), 2 -> (3), 3 -> (W 1)]
删除链表尾部
[list removeLastObject];
打印链表结果：
3 dealloc
Size: 2 [1 -> (2), 2 -> (W 1)]
删除链表中间节点
重新将上面长度2的节点添加一个age为3的person对象到尾部：
[list addObject:[Person personWithAge:3]];
打印链表结果：
Size: 3 [1 -> (2), 2 -> (3), 3 -> (W 1)]
删除index为1的节点，即中间age为2的节点：
[list removeObjectAtIndex:1];
打印链表结果：
Size: 2 [1 -> (3), 3 -> (W 1)]
时间复杂度分析
单向循环链表和单向同样，在操作插入和删除节点时，对节点关系的维护上都是O(1)，但是和单向链表同样需要通过index查找到对于的节点进行操作，这个查找是从头节点开始，依次通过节点的next指针找到下一个节点，直到找到第index个节点为止，所以在添加、删除、取值上和单向链表一致，平均都是O(n)。
不同的是，单向循环链表在对头节点进行操作时，需要获取尾节点，这个也是O(n)级别的查找，所以，单向链表只有在链表只有一个节点的情况下才有O(1)级别的最优时间，其它情况无论是操作头节点还是尾节点，都是O(n)，而不是像单向链表一样，操作头节点都是O(1)。
对比单向链表和单向循环链表分别操作头节点、中间节点、尾节点的时间：
void compareSingleLinkedListAndSingleCircleLinkedList() {
[JKRTimeTool teskCodeWithBlock:^{
JKRBaseList *array = [JKRSingleLinkedList new];
for (NSUInteger i = 0; i < 10000; i++) {
[array insertObject:[NSNumber numberWithInteger:i] atIndex:0];
}
for (NSUInteger i = 0; i < 10000; i++) {
[array removeFirstObject];
}
NSLog(@"单向链表操作头节点");
}];
[JKRTimeTool teskCodeWithBlock:^{
JKRBaseList *array = [JKRSingleCircleLinkedList new];
for (NSUInteger i = 0; i < 10000; i++) {
[array insertObject:[NSNumber numberWithInteger:i] atIndex:0];
}
for (NSUInteger i = 0; i < 10000; i++) {
[array removeFirstObject];
}
NSLog(@"单向循环链表操作头节点");
}];
[JKRTimeTool teskCodeWithBlock:^{
JKRBaseList *array = [JKRSingleLinkedList new];
for (NSUInteger i = 0; i < 10000; i++) {
[array addObject:[NSNumber numberWithInteger:i]];
}
for (NSUInteger i = 0; i < 10000; i++) {
[array removeLastObject];
}
NSLog(@"单向链表操作尾节点");
}];
[JKRTimeTool teskCodeWithBlock:^{
JKRBaseList *array = [JKRSingleCircleLinkedList new];
for (NSUInteger i = 0; i < 10000; i++) {
[array addObject:[NSNumber numberWithInteger:i]];
}
for (NSUInteger i = 0; i < 10000; i++) {
[array removeLastObject];
}
NSLog(@"单向循环链表操作尾节点");
}];
[JKRTimeTool teskCodeWithBlock:^{
JKRBaseList *array = [JKRSingleLinkedList new];
for (NSUInteger i = 0; i < 10000; i++) {
[array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count >> 1];
}
for (NSUInteger i = 0; i < 10000; i++) {
[array removeObjectAtIndex:array.count >> 1];
}
NSLog(@"单向链表操作中间节点");
}];
[JKRTimeTool teskCodeWithBlock:^{
JKRBaseList *array = [JKRSingleCircleLinkedList new];
for (NSUInteger i = 0; i < 10000; i++) {
[array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count >> 1];
}
for (NSUInteger i = 0; i < 10000; i++) {
[array removeObjectAtIndex:array.count >> 1];
}
NSLog(@"单向循环链表操作中间节点");
}];
}
打印结果：
单向链表操作头节点
耗时: 0.004 s
单向循环链表操作头节点
耗时: 1.947 s
单向链表操作尾节点
耗时: 1.980 s
单向循环链表操作尾节点
耗时: 1.962 s
单向链表操作中间节点
耗时: 0.984 s
单向循环链表操作中间节点
耗时: 0.972 s
单向循环链表的应用：约瑟夫问题
问题来历
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
问题分析
首先所有的人是围城一圈的，而且需要循环很多圈才能够将所有人依次排除，而这非常适合刚刚完成的单向循环链表才解决，尾节点的下一个节点又重新拿到的头节点，刚刚和问题中的情况契合。
首先我们只要拿到链表的头节点，然后依次通过头节点的next指针往后拿到下一个节点，找到第3个移除链表，然后依次循环直到链表为空，移除的顺序就是我们需要的死亡顺序。
为了做到这个功能，首先我们需要先修改一下单向循环链表的_first访问权限为public，让外部能够拿到头节点。
@interface JKRSingleCircleLinkedList : JKRBaseList {
@public
JKRSingleLinkedListNode *_first;
}
@end
单向循环链表求死亡顺序
我们可以将39个人抽象成我们之前测试的Person类，age属性就是每个人编号1-41。将41个人添加到单向循环链表中，先拿到头节点，利用next指针往后查到找到后第三个报数的节点，移除它并打印。然后再将起始报数节点设为被删除的next。具体代码如下：
void useSingleCircleList() {
JKRSingleCircleLinkedList *list = [JKRSingleCircleLinkedList new];
for (NSUInteger i = 1; i <= 41; i++) {
[list addObject:[Person personWithAge:i]];
}
NSLog(@"%@", list);
JKRSingleLinkedListNode *node = list->_first;
while (list.count) {
node = node.next;
node = node.next;
printf("%s ", [[NSString stringWithFormat:@"%@", node.object] UTF8String]);
[list removeObject:node.object];
node = node.next;
}
printf("\n");
}
打印的死亡顺序：
3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
