iOS算法：链表-2020-08-05

简介

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单链表：

image.png

双链表：

image.png

iOS 数据结构之链表

这里以单链表为主，双链表大同小异，不重复。

节点

在C语言中可以用struct表示，那么在OC中就应该用类来表示。这里简单起见，就两个成员，数据和下一个指针。

@interface ListNode : NSObject

// key，用来标识结点本身，不需要唯一，默认情况下可以用data的hash代替
@property (assign, nonatomic) NSInteger key;

// 数据
@property (strong, nonatomic) id data;

// 下一个指针
@property (strong, nonatomic) ListNode *next;

@end

如果创建节点，就需要初始化函数。

- (instancetype)initWithData:(id)data {
    self = [super init];
    if (self) {
        _data = data;
    }
    return self;
}

+ (instancetype)nodeWithData:(id)data {
    return [[[self class] alloc] initWithData:data];
}

头结点

对于一个单链表来讲，头结点就代表了这个链表本身。所以需要一个头结点属性。

@interface List()

// 头结点
@property (strong, nonatomic) ListNode *headNode;

@end

添加节点

可以固定在头部添加，这也符合最新使用的原则。
另外提供一个方便方法，将数组中的值连续添加进去。

// 添加节点，加在头部
- (void)addNode:(ListNode *)node {
    // 空节点不需要添加
    if (node == nil) {
        return;
    }
    
    // key可以重复，可以相同，没必要检查是否存在
    
    // 添加到头部
    if (self.head != nil) {
        node.next = self.head;
        self.head = node;
    } else {
        self.head = node;
    }
}

// 方便方法，添加一组节点
- (void)addNodes:(NSArray *)datas {
    [datas enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [self addNode:[ListNode nodeWithData:obj]];
    }];
}

读取所有节点

遍历链表，打印信息，同时返回节点数组。

// 读取所有节点
- (NSArray *)readAllNodes {
    NSMutableArray *nodes = [NSMutableArray array];
    ListNode *temp = self.head;
    while (temp) {
        [nodes addObject:temp];
        NSLog(@"node key:%ld; node data: %@", (long)temp.key, temp.data);
        temp = temp.next;
    }
    
    return [nodes copy];
}

倒序排列

对于单链表，讨论最多的就是倒序输出。倒序输出理解起来确实比较麻烦。
需要引入previous, current, next三个指针辅助理解，相对简单一点:

image.png

1. 将下一个保存在next中。next = current.next;

2. 反转：将下一个指向前一个。current.next = previous;

3. 移动：前一个移动到当前。previous = current;

4. 移动：当前移动到下一个。 current = next;

循环之后，current已经移动到最后，previous就是新的头

图解单链表反转

// 倒序
- (void)reverse {
    ListNode *previous = nil;
    ListNode *current = self.head;
    ListNode *next = nil;
    
    while (current) {
        // 1. 将下一个保存在`next`中。
        next = current.next;
        // 2. 反转：将下一个指向前一个。
        current.next = previous;
        // 3. 移动：前一个移动到当前。
        previous = current;
        // 4. 移动：当前移动到下一个。
        current = next;
    }
    
    // current已经移动到最后，previous就是新的头
    self.head = previous;
}

测试

image.png

// 生成链表
- (IBAction)generateButtonTouched:(id)sender {
    NSString *input = self.inputTextView.text;
    NSArray *array = [input componentsSeparatedByString:@","];
    [self.list addNodes:array];
    
    NSArray *nodes = [self.list readAllNodes];
    NSMutableArray *messages = [NSMutableArray array];
    [nodes enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        ListNode *node = (ListNode *)obj;
        NSString *message = [NSString stringWithFormat:@"%@", node.data];
        [messages addObject:message];
    }];
    self.listLabel.text = [messages componentsJoinedByString:@";"];
}

// 反向链表
- (IBAction)reverseButtonTouched:(id)sender {
    [self.list reverse];
    
    NSArray *nodes = [self.list readAllNodes];
    NSMutableArray *messages = [NSMutableArray array];
    [nodes enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        ListNode *node = (ListNode *)obj;
        NSString *message = [NSString stringWithFormat:@"%@", node.data];
        [messages addObject:message];
    }];
    self.reverseLabel.text = [messages componentsJoinedByString:@";"];
}

image.png

demo

https://gitee.com/zhangxusong888/ObjectCDemo/tree/master/AlgorithmDemo