介绍

链表的数据结构和数组类似，它是有序的数据单元集合，每一个数据单元称为为Node。
每一个Node都存在2个属性分别指向它的下一个Node和前一个Node

//下一个Node
@property(nonatomic, strong) LinkedNode *next;
//前一个Node，使用weak避免循环引用
@property(nonatomic, weak) LinkedNode *pervious;

链表的通过head和tail属性来组织内部Node的关系

@property(nonatomic, strong, readonly) LinkedNode *head;
@property(nonatomic, strong, readonly) LinkedNode * head;

根据链表内Node的相互关系，还可以分为一下三种

1. 单向链表:只指定Node的next属性(如果存在)
2. 双向链表:指定所有Node的next和previous属性(如果存在)
3. 循环链表:特殊的双向链表，tail.next = head;head.prevoius=tail

虚线表示弱引用

示例(以单向链表为例)

@interface LinkedNode : NSObject

@property(nonatomic, copy) NSString *value;
@property(nonatomic, strong) LinkedNode *next;
@property(nonatomic, weak) LinkedNode *pervious;

- (instancetype)initWithValue:(NSString *)value;
@end

@implementation LinkedNode

- (instancetype)initWithValue:(NSString *)value
{
    if (self = [super init]) {
        _value = [value copy];
    }
    return self;
}

- (NSUInteger)hash
{
    return [_value hash] * 31;
}

- (BOOL)isEqual:(id)object
{
    if (object == self) {
        return YES;
    }
    
    if (![object isMemberOfClass:[self class]]) {
        return NO;
    }
    
    LinkedNode *node = (LinkedNode *)object;
    return [_value isEqualToString:node.value];
}
@end

@class LinkedNode;
//单向链表
@interface SinglyLinkedList : NSObject

@property(nonatomic, strong, readonly) LinkedNode *head;
@property(nonatomic, strong, readonly) LinkedNode *tail;

- (void)append:(NSString *)value;
- (LinkedNode *)nodeAtIndex:(NSUInteger)index;
- (void)removeAllNodes;
- (void)removeNode:(LinkedNode *)aNode;

@end

@interface SinglyLinkedList ()

@property(nonatomic, strong, readwrite) LinkedNode *head;

@property(nonatomic, strong, readwrite) LinkedNode *tail;

@end

@implementation SinglyLinkedList

- (void)append:(NSString *)value
{
    LinkedNode *node = [[LinkedNode alloc] initWithValue:value];
    
    if (self.tail == nil) {
        //插入第一个数据
        self.head = node;
        self.tail = node;
    } else {
        LinkedNode *tail = self.tail;
        tail.next = node;
        self.tail = node;
    }
}

- (LinkedNode *)nodeAtIndex:(NSUInteger)index
{
    
    NSUInteger current = 0;
    
    LinkedNode *node = self.head;
    while (node) {
        
        if (current == index) {
            break;
        }
        
        current++;
        node = node.next;
    }
    
    return node;
}

- (void)removeNode:(LinkedNode *)aNode
{
    if (aNode == nil) {
        return;
    }
    
    if ([aNode isEqual:self.head]) {
        self.head = self.head.next;
        //如果只有一个元素的情况
        if (self.head == nil) {
            self.tail = nil;
        }
        return;
    }
    
    LinkedNode *node = self.head;
    while (node) {
        
        if ([node.next isEqual:aNode]) {
            
            //单向链表删除node需要通过这个node的前一个node处理
            LinkedNode *nextNextNode = node.next.next;
            
            node.next = nextNextNode;
            
            if (!nextNextNode) {
                self.tail = node;
            }
            
            break;
        }
        
        node = node.next;
    }
}

- (void)removeAllNodes
{
    self.head = nil;
    self.tail = nil;
}

- (NSString *)description
{
    NSMutableString *str = [NSMutableString new];
    [str appendString:@"["];
    
    LinkedNode *node = self.head;
    while (node) {
        [str appendString:node.value];
        node = node.next;
        if (node) {
            [str appendString:@", "];
        }
    }
    
    [str appendString:@"]"];
    
    return [str copy];
}

@end

使用

- (void)singlyLinkedListTest
{
    SinglyLinkedList *list = [SinglyLinkedList new];
    
    [list append:@"1"];
    [list append:@"2"];
    [list append:@"3"];
    [list append:@"4"];
    
    LinkedNode *node = [list nodeAtIndex:2];
    
    NSLog(@"list = %@", list);
    
    [list removeNode:[[LinkedNode alloc] initWithValue:@"4"]];
    
    NSLog(@"list = %@", list);
}

参考

参考1