介紹

鏈表的數(shù)據(jù)結(jié)構(gòu)和數(shù)組類似，它是有序的數(shù)據(jù)單元集合，每一個數(shù)據(jù)單元稱為為Node。
每一個Node都存在2個屬性分別指向它的下一個Node和前一個Node

//下一個Node
@property(nonatomic, strong) LinkedNode *next;
//前一個Node，使用weak避免循環(huán)引用
@property(nonatomic, weak) LinkedNode *pervious;

鏈表的通過head和tail屬性來組織內(nèi)部Node的關(guān)系

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

根據(jù)鏈表內(nèi)Node的相互關(guān)系，還可以分為一下三種

1. 單向鏈表:只指定Node的next屬性(如果存在)
2. 雙向鏈表:指定所有Node的next和previous屬性(如果存在)
3. 循環(huán)鏈表:特殊的雙向鏈表，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) {
        //插入第一個數(shù)據(jù)
        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