A one-way circular linked list is based on a one-way linked list, the next pointer of the last node points to the head node of the list. But with objective-C memory management, there are circular references, so the last node pointing to the head node should be a weak reference.
The nodes of a circular linked list
WeakNext points to the head node of the linked list:
#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
Copy the codeIn order to get the next node of the node, judgment is made in the get method of next. If next is empty, weakNext is taken. In this way, the next node of the linked list can be obtained by obtaining Next, and there is no need to separately judge which is empty. Therefore, it is necessary to pay attention to that: We must maintain weakNext and next well, so that they can not have values at the same time, and can only have values when they should not be empty.
- WeakNext: When the node is the last node in the list (including the case where the list has only one node), weakNext points to the head node of the list (points to itself when the list has only one node), and next is nil at this point.
- Next: When the node is not the last node in the linked list, next points to the next node of the node, and weakNext is 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 = @""; // Here is a reminder of maintenance error for Next and weakNext. If both nodes have values, E (error) is displayed, indicating that there is a problem in pointer maintenanceif (_next && _weakNext) {
tipString = @"E ";
} else if (_weakNext) {
tipString = @"W ";
}
return [NSString stringWithFormat:@"% @ - > (% @ % @)", self.object, tipString, self.next.object];
}
@end
Copy the codeAdd a node
Add the first node
When inserting the first node, you need to point the _FIRST pointer of the linked list to the created node and weakNext of the node to yourself.
Insert into the head of the list
To insert a new node into the head of the list:
The required operations are shown below:
- The next pointer to the new node points to the original head node.
- WeakNext of the tail node points to the new node.
- The head node pointer _first points to the new node.
Add the structure of the linked list:
Appends a node to the end of the list
To insert a new node at the end of the list:
The required operations are shown below:
- WeakNext of the original tail node is set to nil, and next of the original tail node points to the new node.
- WeakNext of the new node points to the head node.
Insert into the middle of the linked list node
To insert a new node between two nodes that already exist in the list:
The required operations are shown below:
- Points the next pointer to the previous node at the insertion position to the new node.
- Place the next pointer of the new node to the original node at the insertion position.
Linked list structure after operation:
Add the code for the node
To sum up the above adding logic, the code for adding nodes is as follows:
- (void)insertObject:(id)anObject atIndex:(NSUInteger)index {
[self rangeCheckForAdd:index];
if(index == 0) {// Insert the head of the list or add the first node 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; }elseJKRSingleLinkedListNode *prev = [self nodeWithIndex: index-1]; JKRSingleLinkedListNode *node = [[JKRSingleLinkedListNode alloc] initWithObject:anObject next:prev.next]; prev.next = node; prev.weakNext = nil;if(node.next == _first) {// Insert into the end of the list node.next = nil; node.weakNext = _first; } } _size++; }Copy the codeRemove nodes
Delete the current unique node
Delete the currently unique node, just set _first to nil, and the node will be freed automatically:
Delete the head node
Delete the head node of the linked list whose length is not 1, as shown below:
- Point _first to the next node from the original head node.
- WeakNext of the tail node points to the new head node.
Deleting tail nodes
Delete the nodes at the end of the linked list as shown below:
To delete the tail node, first get the last node of the tail node of the list and perform the following operations:
- Set next to nil for the previous node of the tail node.
- WeakNext of the previous node of the tail node is set as the head node.
Deletes a node between linked list nodes
Delete the nodes in the middle of other nodes in the linked list as shown below:
Just find the previous node of the deleted node and point its next to next of the deleted node:
Delete the code of the node
In summary, the code for deleting nodes is:
- (void)removeObjectAtIndex:(NSUInteger)index {
[self rangeCheckForExceptAdd:index];
JKRSingleLinkedListNode *node = _first;
if(index == 0) {// Delete the header or unique nodeif(_size == 1) {// Delete only node _first = nil; }else{// delete header JKRSingleLinkedListNode *last = [self nodeWithIndex:_size - 1]; _first = _first.next; last.next = nil; last.weakNext = _first; }}elseJKRSingleLinkedListNode *prev = [self nodeWithIndex: index-1]; node = prev.next;if(node.next == _first) {// Delete last node prev.next = nil; prev.weakNext = _first; }else{// Delete middle node prev.next = node.next; prev.weakNext = nil; } } _size--; }Copy the codeTest one-way circular linked lists
Test object 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];
}
Copy the codeAdd the first node
First add the first node to the empty one-way circular list:
JKRBaseList *list = [JKRSingleCircleLinkedList new];
[list addObject:[Person personWithAge:1]];
Copy the codePrint linked list results:
Size: 1 [1 -> (W 1)]
Copy the codeLinked list weakNext points to itself.
Insert to the end of the list
Add another element to the tail:
[list addObject:[Person personWithAge:3]];
Copy the codePrint linked list results:
Size: 2 [1 -> (3), 3 -> (W 1)]
Copy the codeThe Person object with age 1 points to the new Person object with age 3 by strong reference, and the person object with age 3 points to the person object with age 1 by weak reference.
Insert into the middle of the list
[list insertObject:[Person personWithAge:2] atIndex:1];
Copy the codePrint linked list results:
Size: 3 [1 -> (2), 2 -> (3), 3 -> (W 1)]
Copy the codeInsert into the head of the list
[list insertObject:[Person personWithAge:0] atIndex:0];
Copy the codePrint linked list results:
Size: 4 [0 -> (1), 1 -> (2), 2 -> (3), 3 -> (W 0)]
Copy the codeDelete the head node
[list removeFirstObject];
Copy the codePrint linked list results:
0 dealloc
Size: 3 [1 -> (2), 2 -> (3), 3 -> (W 1)]
Copy the codeDelete the end of the list
[list removeLastObject];
Copy the codePrint linked list results:
3 dealloc
Size: 2 [1 -> (2), 2 -> (W 1)]
Copy the codeDelete the middle node of the linked list
Add a person object with age 3 to the end of the node of length 2 above:
[list addObject:[Person personWithAge:3]];
Copy the codePrint linked list results:
Size: 3 [1 -> (2), 2 -> (3), 3 -> (W 1)]
Copy the codeDelete node where index = 1, age = 2;
[list removeObjectAtIndex:1];
Copy the codePrint linked list results:
Size: 2 [1 -> (3), 3 -> (W 1)]
Copy the codeTime complexity analysis
One-way circular linked list and one-way same, in the operation of the insert and delete nodes, on the maintenance of the relationship between the nodes are O (1), but and singly linked list also need to through the index for to find the node, the lookup is node start from scratch, in order to find the next node through the next node pointer, until you find the first index nodes, So the addition, deletion, and value of the one-way list are the same, the average is O(n).
, one-way circular linked list in adversary node operation, need to get end node, this also is O (n) levels of the search, therefore, singly linked list only only under the condition of a node in the linked list is O (1) the level of the optimal time and other situations both head node and end node, is O (n), rather than like a singly linked list, The operation head node is O(1).
Compare the operation time of the head node, the middle node and the tail node of the one-way linked list and the one-way cyclic linked list respectively:
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(@"Head node of one-way linked list operation");
}];
[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(@"Head node of one-way circular linked list operation");
}];
[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(@"End node of one-way linked list operation");
}];
[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(@"End node of one-way cyclic linked list operation");
}];
[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(@"One-way linked list operation intermediate node");
}];
[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(@"Middle node of one-way circular linked list operation");
}];
}
Copy the codePrint result:
Time spent on head node of one-way linked list operation: 0.004s Time spent on head node of one-way linked list operation: 1.947s Time spent on tail node of one-way linked list operation: 1.980s Time spent on tail node of one-way linked list operation: 1.962s Time spent on middle node of one-way linked list operation: 0.984 s Time spent on intermediate nodes of one-way cyclic linked list operation: 0.972 sCopy the codeApplications of unidirectional cyclic linked lists: The Joseph problem
Question history
Josephus, the famous Jewish historian, is said to have told the following story: After the Roman occupation of Joe tower pat, 39 jews and Josephus and his friend hiding in a hole, 39 decided jews would rather die don’t was caught by the enemy, then made a suicide, 41 people arranged in a circle, start from 1 individual number off, each number off to third person would have to commit suicide, and then the next number off again, Until everyone committed suicide. Josephus and his friends, however, did not want to comply. Start with one person, pass k-2 people (since the first person has already been passed), and kill the KTH person. And then you go over k minus one person and you kill the k person. The process continues along the circle until only one person is left, and that person can continue to live. The question is, given the sum, where do you have to stand to avoid execution in the first place? Josephus told his friend to pretend to obey first, and he escaped the game of death by placing him and his friend in positions sixteen and thirty-one.
Problem analysis
First of all, all the people are in a circle, and it takes a lot of circles to get rid of all the people in turn, which is very suitable for a one-way circular list that has just been completed, and then the next node at the tail node gets the head node again, which just fits the situation in the problem.
First, we just need to get the first node of the linked list, then take the next node through the next pointer of the first node, find the third node to remove the linked list, and then cycle until the list is empty. The order of removal is the order of death we need.
To do this, we first need to change the _first access to public, so that outsiders can get the head node.
@interface JKRSingleCircleLinkedList : JKRBaseList {
@public
JKRSingleLinkedListNode *_first;
}
@end
Copy the codeFind the order of death by a one-way circular list
We can abstract 39 people into the Person class we tested earlier, where the age property is numbered 1-41. Add 41 people to a one-way circular list, get the first node, use the next pointer to look back to the third node after finding it, remove it and print it. Then set the start count node to the deleted Next. The specific code is as follows:
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");
}
Copy the codePrinted order of death:
6 9 12 15 18 21 24 27 30 33 36 39 15 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 31Copy the codeThe source code
Click to view source code