链表

链表是一种常见的数据结构，链表中的数据是以节点表示的。每一个节点都有数据域(Data)和指针域(Next)，数据域用来存放数据，指针域指向下一个节点。

节点示意图.png

这样节点一个一个的连接起来就构成了简单的链表，

简单链表.png

链表可以分为单向链表，双向链表和循环链表。我们先来看一下单向链表。

单向链表

插入节点

插入节点.png

主要代码实现:

节点
@interface XSYSingleNode : NSObject<NSCopying,NSMutableCopying>
@property (nonatomic, strong) id key;
@property (nonatomic, strong) id value;
@property (nonatomic, strong) XSYSingleNode * next;
+ (instancetype)nodeWithKey:(id)key value:(id)value;
- (instancetype)initWithKey:(id)key value:(id)value;
@end
@implementation XSYSingleNode
- (instancetype)initWithKey:(id)key value:(id)value{
    self.key = key;
    self.value = value;
    return [self init];
}

+ (instancetype)nodeWithKey:(id)key value:(id)value{
    return [[self alloc] initWithKey:key value:value];
}

- (instancetype)init{
    if (self = [super init]) {
        
    }
    return self;
}

- (id)copyWithZone:(NSZone *)zone{
    XSYSingleNode * node = [[XSYSingleNode allocWithZone:zone] init];
    node.key = self.key;
    node.value = self.value;
    node.next = self.next;
    return node;
}

- (id)mutableCopyWithZone:(NSZone *)zone{
    return [self copyWithZone:zone];
}
@end

- (void)insertNode:(XSYSingleNode *)node{
    if (!node || !node.key || !node.value) {
        return;
    }
    
    if (!_head) {
        _head = node;
    }
    else{
        XSYSingleNode * nod = _head;
        while (nod.next) {
          nod= nod.next;
        }
        nod.next = node;
        
    }
    _nodeDic[node.key] = node.value;
}

测试：

XSYSingleLinkedList * singleList = [XSYSingleLinkedList singleLinkedList];
    
    XSYSingleNode * firNode = nil;
    XSYSingleNode * delNode = nil;
    for (int i = 1; i < 6; i ++) {
        XSYSingleNode * node = [XSYSingleNode nodeWithKey:
[NSString stringWithFormat:@"%d",i] value:[NSString stringWithFormat:@"xsy_%02d",i]];
        [singleList insertNode:node];
        if (i == 1) {
            firNode = node;
        }
        else if(i == 3){
            delNode = node;
        }
    }

打印结果：

(
    "xsy_01",
    "xsy_02",
    "xsy_03",
    "xsy_04",
    "xsy_05"
)

删除节点

删除节点.png

- (BOOL)removeNode:(XSYSingleNode *)node{
    BOOL result = NO;
    if ([[_nodeDic allKeys] containsObject:node.key]) {
        result = YES;
        if (node.next) {
            node.key = node.next.key;
            node.value = node.next.value;
            node.next = node.next.next;
        }
        else{
            // 删除头结点
            _head = nil;
        }
        
        [_nodeDic removeObjectForKey:node];
        
    }
    return result;
}

测试：

    BOOL result1 = [singleList removeNode:firNode];
    NSLog(@"删除节点 --- %d",result1);
    BOOL result2 = [singleList removeNode:delNode];
    NSLog(@"删除节点 --- %d",result2); 
    NSLog(@"所有节点为 b--- %@",[singleList allNodes]);

打印结果:

删除节点 --- 1
删除节点 --- 1
所有节点为 b--- (
    "xsy_02",
    "xsy_04",
    "xsy_05"
)