Bidirectional circular linked lists

A bidirectional circular list is an extension of a unidirectional circular list. The principle of a bidirectional circular list is similar to that of a unidirectional list: the next of the tail points to the head of the list. On this basis, the prev of the head node points to the tail node, thus achieving a bidirectional circular linked list. Also, to prevent circular references, weak references are used when the tail node points to the head node.

Nodes of a bidirectional cyclic linked list

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface JKRLinkedListNode : NSObject

@property (nonatomic, strong, nullable) id object;
@property (nonatomic, weak, nullable) JKRLinkedListNode *weakNext;
@property (nonatomic, strong, nullable) JKRLinkedListNode *next;
@property (nonatomic, weak, nullable) JKRLinkedListNode *prev;

- (instancetype)init __unavailable;
+ (instancetype)new __unavailable;

- (instancetype)initWithPrev:(JKRLinkedListNode *)prev object:(nullable id)object next:(nullable JKRLinkedListNode *)next;

@end

NS_ASSUME_NONNULL_END
Copy the code

Add a node

Adding nodes to a bidirectional list is basically the same as adding nodes to a bidirectional list, with the addition of prev at the head and next at the tail.

Add the first node of the list

Compared with bidirectional linked list, bidirectional circular linked list points the head node and the tail node of the linked list to the new node, and also needs to point the prev and weakNext of the node to itself.

The code logic is as follows:

if (_size == 0 && index == 0) {
    JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:nil object:anObject next:nil];
    _last = node;
    _first = _last;
    _first.prev = _first;
    _first.next = nil;
    _first.weakNext = _first;
}
Copy the code

Appends a node to the end of the list

The newly added node replacing the original tail node is called the new tail node:

The required operations are shown below:

The prev of the newly added node points to the last node of the original list.
Last points to the newly added node.
The next of the original tail of the list points to the new tail of the list (that is, the newly added node).
The prev of the list head node points to the newly added node.
WeakNext of the newly added tail node points to the head node of the linked list.

if(_size == index && _size ! = 0) { JKRLinkedListNode *oldLast = _last; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:nil object:anObject next:nil]; _last = node; oldLast.next = _last; oldLast.weakNext = nil; _first.prev = _last; _last.next = nil; _last.weakNext = _first; }Copy the code

Add first node and tail append node code consolidation

if (_size == 0 && index == 0) {
    JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:nil object:anObject next:nil];
    _last = node;
    _first = _last;
    _first.prev = _first;
    _first.next = nil;
    _first.weakNext = _first;
}

if(_size == index && _size ! = 0) { JKRLinkedListNode *oldLast = _last; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:nil object:anObject next:nil]; _last = node; oldLast.next = _last; oldLast.weakNext = nil; _first.prev = _last; _last.next = nil; _last.weakNext = _first; }Copy the code

The above two codes merge the same judgment logic and separate the different judgment logic:

if (_size == index) {
    if (_size == 0) {
        JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:nil object:anObject next:nil];
        _last = node;
        _first = _last;
        _first.prev = _first;
        _first.next = nil;
        _first.weakNext = _first;
    } else{ JKRLinkedListNode *oldLast = _last; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:nil object:anObject next:nil]; _last = node; oldLast.next = _last; oldLast.weakNext = nil; _first.prev = _last; _last.next = nil; _last.weakNext = _first; }}Copy the code

Bring out the same code:

if(_size == index) { JKRLinkedListNode *oldLast = _last; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:_last object:anObject next:_first]; _last = node; // _size == 0 OldLast because the empty list _last is emptyif(_size == 0) {// Add the first element of the list _first = _last; _first.prev = _first; _first.next = nil; _first.weakNext = _first; }else{// Insert into the end of the table oldlast.next = _last; oldLast.weakNext = nil; _first.prev = _last; _last.next = nil; _last.weakNext = _first; }}Copy the code

Insert into the head of the list

Insert a new node into the head of the list as shown below:

The required operations are shown below:

The new node prev points to the prev of the original head node.
The next of the new node points to the original head node.
The prev of the original head node points to the new node.
The first pointer to the linked list points to the new node.
WeakNext of the prev (i.e. tail node) of the original head node points to the new head node.

The linked list after node insertion is complete is as follows:

The code logic is as follows:

if(index == _size) {// Add the first node to the end of the list or to an empty list //... }else {
    if(index == 0) {// Insert into the header JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; _first = node; prev.next = nil; prev.weakNext = node; }else{// Insert between two nodes}}Copy the code

Insert between nodes in the list

Insert a new node between the two nodes in the linked list as shown below:

The required operations are shown below:

First get the node corresponding to the index insertion position.
The new node prev points to the preV of the original node at the list insertion location.
The next of the new node points to the original node where the list was inserted.
List insertion position The prev of the original node points to the new node.
The next of the previous node points to the new node.

The linked list after node insertion is complete is as follows:

The code logic is as follows:

if(index == _size) {// Add the first node to the end of the list or to an empty list //... }else {
    if(index == 0) {// Insert into the header JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; _first = node; prev.next = nil; prev.weakNext = node; }else{// Insert between two nodes JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; prev.next = node; prev.weakNext = nil; }}Copy the code

Logical consolidation of code inserted into non-empty node locations of the table

    if(index == 0) {// Insert into the header JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; _first = node; prev.next = nil; prev.weakNext = node; }else{// Insert between two nodes JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; prev.next = node; prev.weakNext = nil; }Copy the code

Extract the same code logic:

JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; // Next == _first is the first node in the listif(index == 0) {// Insert into the table header _first = node; prev.next = nil; prev.weakNext = node; }else{// Insert between two nodes. Next = node; prev.weakNext = nil; }Copy the code

Add node code summary

- (void)insertObject:(id)anObject atIndex:(NSUInteger)index { [self rangeCheckForAdd:index]; // index == size = insert to the end of the list or add the first node to an empty listif (_size == index) {
        JKRLinkedListNode *oldLast = _last;
        JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:_last object:anObject next:_first];
        _last = node;
        // _size == 0
        if(! OldLast) {// Add the first element of the list _first = _last; _first.prev = _first; _first.next = nil; _first.weakNext = _first; }else{// Insert into the end of the table oldlast.next = _last; oldLast.weakNext = nil; _first.prev = _last; _last.next = nil; _last.weakNext = _first; }}elseJKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *next = [self nodeWithIndex:index]; JKRLinkedListNode *prev = next.prev; JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next]; next.prev = node; // index == 0if(next == _first) {// Insert into the header _first = node; prev.next = nil; prev.weakNext = node; }else{// Insert between two nodes. Next = node; prev.weakNext = nil; } } _size++; }Copy the code

Remove nodes

Delete a unique node

Delete the only node in the linked list as shown below:

The required operations are shown below:

Point the head node of the linked list to NULL
Point the last node of the linked list to NULL

The code is as follows:

if(_size == 1) {// Delete only node _first = nil; _last = nil; }Copy the code

Delete the head node

Delete the head node as shown below:

The required operations are shown below:

WeakNext of the last node (tail node) of the deleted node points to the next node of the deleted node.
The preV of the node after the deleted node points to the node before the deleted node.
The head node of the linked list points to the next node after the deleted node.

Delete the header node as follows:

if(_size == 1) {// Delete only node _first = nil; _last = nil; }elseJKRLinkedListNode *node = [self nodeWithIndex:index]; // The last node of the deleted node JKRLinkedListNode *prev = node.prev; // Next node of the deleted node JKRLinkedListNode *next = node.next;if(node == _first) {// Delete header prev.next = nil; prev.weakNext = next; next.prev = prev; _first = next; }else{/ /... }}Copy the code

Deleting tail nodes

Delete the head node as shown below:

The required operations are shown below:

WeakNext of the previous node (new tail node) of the original tail node points to next (head node) of the original tail node.
Points the prev of the node following the original tail node (the head node) to the node preceding the original tail node (the new tail node).
The last node of the list points to the previous node (the new last node) of the previous last node.

The code is as follows:

if(_size == 1) {// Delete only node _first = nil; _last = nil; }elseJKRLinkedListNode *node = [self nodeWithIndex:index]; // The last node of the deleted node JKRLinkedListNode *prev = node.prev; // Next node of the deleted node JKRLinkedListNode *next = node.next;if(node == _first) {// Delete header prev.next = nil; prev.weakNext = next; next.prev = prev; _first = next; }else if(node == _last) {// Delete the last node prev.next = nil; prev.weakNext = next; next.prev = prev; _last = prev; }else{// Delete nodes between nodes //... }}Copy the code

Deletes a node in the middle of a linked list node

Delete the nodes in the middle of the linked list as shown below:

The required operations are shown below:

The next of the node before the deleted node points to the next of the deleted node.
The prev of the next node points to the preV of the deleted node.

The code is as follows:

if(_size == 1) {// Delete only node _first = nil; _last = nil; }elseJKRLinkedListNode *node = [self nodeWithIndex:index]; // The last node of the deleted node JKRLinkedListNode *prev = node.prev; // Next node of the deleted node JKRLinkedListNode *next = node.next;if(node == _first) {// Delete header prev.next = nil; prev.weakNext = next; next.prev = prev; _first = next; }else if(node == _last) {// Delete the last node prev.next = nil; prev.weakNext = next; next.prev = prev; _last = prev; }else{// Delete nodes between nodes. Next = next; next.prev = prev; }}Copy the code

Add node code summary

- (void)removeObjectAtIndex:(NSUInteger)index {
    [self rangeCheckForExceptAdd:index];

    if(_size == 1) {// Delete only node _first = nil; _last = nil; }elseJKRLinkedListNode *node = [self nodeWithIndex:index]; // The last node of the deleted node JKRLinkedListNode *prev = node.prev; // Next node of the deleted node JKRLinkedListNode *next = node.next;if(node == _first) {// Delete header prev.next = nil; prev.weakNext = next; next.prev = prev; _first = next; }else if(node == _last) {// Delete the last node prev.next = nil; prev.weakNext = next; next.prev = prev; _last = prev; }else{// Delete nodes between nodes. Next = next; next.prev = prev; } } _size--; }Copy the code

test

Use the same test cases as the bidirectional list:

void testCirleList() {
    JKRBaseList *list = [JKRLinkedCircleList new];
    [list addObject:[Person personWithAge:1]];
    printf("%s", [NSString stringWithFormat:@"Add first node \n%@\n\n", list].UTF8String);
    
    [list addObject:[Person personWithAge:3]];
    printf("%s", [NSString stringWithFormat:@"Append a node \n%@\n\n", list].UTF8String);
    
    [list insertObject:[Person personWithAge:2] atIndex:1];
    printf("%s", [NSString stringWithFormat:@"Insert between two linked list nodes \n%@\n\n", list].UTF8String);
    
    [list insertObject:[Person personWithAge:0] atIndex:0];
    printf("%s", [NSString stringWithFormat:@"Insert into head of list \n%@\n\n", list].UTF8String);
    
    [list removeFirstObject];
    printf("%s", [NSString stringWithFormat:@"Delete head node \n%@\n\n", list].UTF8String);
    
    [list removeObjectAtIndex:1];
    printf("%s", [NSString stringWithFormat:@"Delete the node \n%@\n\n", list].UTF8String);
    
    [list removeLastObject];
    printf("%s", [NSString stringWithFormat:@"Delete tail node \n%@\n\n", list].UTF8String);
    
    [list removeAllObjects];
    printf("%s", [NSString stringWithFormat:@"Delete the only node \n%@\n\n", list].UTF8String);
}
Copy the code

Print result:

Add node Size: 1 [(W 1) -> 1 -> (W 1)] add node Size: 2 [(W 3) -> 1 -> (3), (W 1) -> 3 -> (W 1)] add node Size: 1 [(W 1) -> 1 -> (W 1)] 3 [(3 W) - 1 - > > (2), (W) 1 - > 2 - > (3), (W) 2 - > 3 - > 1 (W)] is inserted into the list head Size: 4 [3 (W) - > 0 - > (1), (W) - 1 - > > (2), (W) 1 - > 2 - > (3), (W) 2 - > 3 - > 0 (W)] 0 dealloc to remove head node Size: 3 [(3 W) - 1 - > > (2), (W) 1 - > 2 - > (3), (W) 2 - > 3 - > 1 (W)] 2 dealloc delete list node Size between the two nodes: 2 [(W 3) -> 1 -> (3), (W 1) -> 3 -> (W 1)] 3 deallocCopy the code

As you can see, all nodes point to the previous node by weak reference, and all nodes except the tail node point to the next node by strong reference. WeakNext of the tail node points to the head node through weak reference cycle, and the head node points to its tail node through weak reference through PREv.

Time complexity analysis

From the logic of adding and deleting above, it can be seen that the time complexity of the two-way circular list is O(1) when operating from head to tail. For nodes in the middle of the list, the same bidirectional list is also O(n). The closer you are to the middle of the list, the faster you are to the head or tail of the list.

Same as the test case in the previous section, compare the operation time of 50000 insertions and deletes at different positions of the bidirectional circular list and bidirectional linked list:

Time spent on head node of bidirectional circular linked list operation: 0.053s Time spent on head node of bidirectional circular linked list operation: 0.034s Time spent on tail node of bidirectional circular linked list operation: 0.045s time spent on tail node of bidirectional linked list operation: 0.032s index = Total number of nodes *0.25 Node time: 12.046s Index = Total number of nodes *0.25 node time: 11.945s Index = Total number of nodes *0.75 Node duration: 19.340s Index = Total number of nodes *0.75 Node duration: 19.162s Intermediate node duration: It takes 37.876s to operate intermediate nodes in the bidirectional linked listCopy the code

Applications of circular linked lists: The Joseph problem

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.

We used one-way cyclic lists to solve Joseph’s problem. Here we can use bidirectional cyclic lists as well:

void useLinkedCircleList() {
    JKRLinkedCircleList *list = [JKRLinkedCircleList new];
    for (NSUInteger i = 1; i <= 41; i++) {
        [list addObject:[NSNumber numberWithInteger:i]];
    }
    NSLog(@"% @", list);
    
    JKRLinkedListNode *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 code

Print order:

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 code

The last two numbers are 16 and 31.

The following

Now that lists and arrays are complete, it’s time to use these simple array structures to implement data structures that sounded awesome before: hash tables, but aren’t that complicated after all.

The source code

Click to view source code

Nodes of a bidirectional cyclic linked list

Add a node

Add the first node of the list

Appends a node to the end of the list

Add first node and tail append node code consolidation

Insert into the head of the list

Insert between nodes in the list

Logical consolidation of code inserted into non-empty node locations of the table

Add node code summary

Remove nodes

Delete a unique node

Delete the head node

Deleting tail nodes

Deletes a node in the middle of a linked list node

Add node code summary

test

Time complexity analysis

Applications of circular linked lists: The Joseph problem

The following

The source code

Related Posts

AVFoundation text to voice and audio recording playback

WKWebView development and use experience sharing

Delimit key | iOS15 official release, a new notification push system, you must know!