单向链表 - 掘金

接着上一篇动态数组，这里再来创建通过单向链表实现一个动态数组。首先先来分析下动态数组的缺点，才能够了解到链表的意义。首先回顾下之前动态数组添加和删除的过程：

动态数组添加元素的时候，最坏的情况是插入元素到数组的头部，则需要依次向后挪动所以元素，进行的操作数取决于当前元素的数量，复杂度为O(n)，最好的情况是追加到数组的尾部，不需要挪动元素，复杂度为O(1)。平均复杂度为O(n)。扩容由于不是每次添加都需要的操作，只有在溢出的时候才需要扩容，扩容的时候复杂度为O(n)，不扩容的时候为O(1)，均摊复杂度依然为O(1)。

删除和添加基本相同，最好的情况删除队尾复杂度为O(1)，最差的情况是删除队头，复杂度为O(n)，平均复杂度为O(n)。

而在根据index取值的时候，由于本质是通过index直接从数组中取值，数组中取值的复杂度为O(1)，所以取元素的复杂度为O(1)。

注：从数组中值并不需要遍历，而是通过地址计算直接取值，复杂度为O(1)。

那么链表会不会比静态数组更快呢，下面我们来实现一个自定义单向链表，然后比较一下就知道了。首先提示一下，单向链表可能没想象的那么快哦。

首先看一下数组和链表在内存中的不同

链表在内存中并不是连续的，链表中每一个存储的单元称为一个节点，在单向链表中，每一个节点中存储两个值，一个是存放的指向存储元素的指针，另一个是指向下一个节点的指针，这样链表就能够通过每一个节点指向下一个节点的指针找到当前节点的下一个节点，只要得到链表的第一个节点，就能够访问到链表的所以节点，同时也就能够拿到链表的全部元素。

单向链表的节点结构

这样一看单向链表是不是非常的简单，在Objective-C语言中，就相当于每一个节点对象有两个成员变量，一个是存值的，另一个是存下一个节点对象的，下面就声明一个单向链表的节点对象：

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface JKRSingleLinkedListNode : NSObject

@property (nonatomic, strong, nullable) id object;
@property (nonatomic, strong, nullable) JKRSingleLinkedListNode *next;

- (instancetype)init __unavailable;
+ (instancetype)new __unavailable;
- (instancetype)initWithObject:(nullable id)object next:(nullable JKRSingleLinkedListNode *)next;

@end

NS_ASSUME_NONNULL_END

单向链表的结构

既然只需要拿到单向链表的头节点，就能够访问到全部节点，那么单向链表中需要存储成员变量只需要两个，一个是 _size，存储这链表的长度。另一个是_first，保存链表的第一个节点。

注：_size存储在父类中，所有的接口声明也在父类中，父类的定义参见通过静态数组的扩容实现动态数组，全部源代码在文章结尾。

#import "JKRBaseList.h"
#import "JKRSingleLinkedListNode.h"

NS_ASSUME_NONNULL_BEGIN

@interface JKRSingleLinkedList : JKRBaseList {
    // NSUInteger _size; 
    JKRSingleLinkedListNode *_first;
}

@end

NS_ASSUME_NONNULL_END

下面是完整的单向链表的内存结构图，可以更加直接的了解单向链表的结构：

通过index查找节点

上面的链表结构图可以看到，链表对象保存这链表的长度和链表的头节点，如果要通过index获得具体的某一个节点，需要从头节点开始逐一通过next指针往后查找，直到找到第index个节点。

时间复杂度取决于index，取index为0的节点只需要访问头节点，只需要1次访问。访问尾节点需要从头节点一直访问到尾节点，访问次数取决于节点数量。综上平均时间复杂度为O(n)。

- (JKRSingleLinkedListNode *)nodeWithIndex:(NSInteger)index {
    [self rangeCheckForExceptAdd:index];
    JKRSingleLinkedListNode *node = _first;
    for (NSInteger i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

通过index取值

上面已经实现了拿到index位置的节点，这里只需要调用方法获取节点，然后返回节点存储的值就可以了。时间复杂度同查找节点：O(n)

- (id)objectAtIndex:(NSUInteger)index {
    return [self nodeWithIndex:index].object;
}

添加节点

在链表中间插入节点

在链表中间插入节点，如下图，链表中存在三个节点，此时我们需要在链表index为1的位置插入一个节点：

此时需要做的就是让index为0的节点的next指向新节点，并让新节点的next指向原来index为1的节点：

这样插入就成功的将一个节点插入到链表的两个节点中：

在链表头部插入节点

在链表头部插入节点如下图：

这时需要将新节点的next指向原来链表的_first，并将链表的_first指向新节点：

在链表头部成功插入节点后链表的结构：

链表添加的节点的代码实现

综上步骤，链表添加节点两种情况的代码实现如下：

- (void)insertObject:(id)anObject atIndex:(NSUInteger)index {
    [self rangeCheckForAdd:index];
    
    if (index == 0) {
        JKRSingleLinkedListNode *node = [[JKRSingleLinkedListNode alloc] initWithObject:anObject next:_first];
        _first = node;
    } else {
        JKRSingleLinkedListNode *prev = [self nodeWithIndex:index - 1];
        JKRSingleLinkedListNode *node = [[JKRSingleLinkedListNode alloc] initWithObject:anObject next:prev.next];
        prev.next = node;
    }
    
    _size++;
}

添加时index的越界检查有动态数组的父类统一实现。

因为添加节点时，虽然插入只需要1次操作，但是涉及到查找index位置的节点，这个查找的复杂度为O(n)，所以添加节点的复杂度为O(n)。

删除节点

在链表中间删除节点

假设删除链表index为1的节点，如下图：

只需要将被删除节点的前一个节点的next指针改变指向，指向被删除节点的下一个节点，那么被删除节点由于没有引用，就会自动被回收：

删除后链表的结构：

删除链表头节点

删除链表的头节点如下图：

只需要将单向链表的_first指针指向原来头节点下一个节点即可：

删除后链表的结构：

链表删除节点的代码实现

综上两种情况，链表删除的代码如下：

- (void)removeObjectAtIndex:(NSUInteger)index {
    [self rangeCheckForExceptAdd:index];
    
    JKRSingleLinkedListNode *node = _first;
    if (index == 0) {
        _first = _first.next;
    } else {
        JKRSingleLinkedListNode *prev = [self nodeWithIndex:index - 1];
        node = prev.next;
        prev.next = node.next;
    }
    _size--;
}

同添加节点的操作，虽然删除节点只需要1次操作，但是涉及到查找index位置的节点，这个查找的复杂度为O(n)，所以删除节点的复杂度也是为O(n)。

至于其他功能都是基于上面几个接口调用实现的，比如尾部追加、删除头节点等，就不一一列举了，最后源码中都有。

和动态数组对比时间复杂度

数据结构	动态数组	单向链表
详细分类	最好最差平均	最好最差平均
插入任意位置元素	O(1) O(n) O(n)	O(1) O(n) O(n)
删除任意位置元素	O(1) O(n) O(n)	O(1) O(n) O(n)
替换任意位置元素	O(1) O(1) O(1)	O(1) O(n) O(n)
查找任意位置元素	O(1) O(1) O(1)	O(1) O(n) O(n)
添加元素到尾部	O(1) O(n) O(1)	O(n) O(n) O(n)
删除尾部元素	O(1) O(1) O(1)	O(n) O(n) O(n)
添加元素到头部	O(n) O(n) O(n)	O(1) O(1) O(1)
删除头部元素	O(n) O(n) O(n)	O(1) O(1) O(1)

上面是总结出来的时间复杂度对比：

插入任意位置元素：动态数组需要挪动元素，且越靠近头部挪动次数越多。单向链表需要找到对于的节点进行指针操作，且越靠近尾部查找次数越多。
删除任意位置元素：动态数组需要挪动元素，且越靠近头部挪动次数越多。单向链表需要找到对于的节点进行指针操作，且越靠近尾部查找次数越多。
替换任意位置元素：动态数组直接通过index取对于位置的值，操作数稳定为1。单向链表需要找到对于的节点进行指针操作，且越靠近尾部查找次数越多。
查找任意位置元素：动态数组直接通过index取对于位置的值，操作数稳定为1。单向链表需要找到对于的节点进行指针操作，且越靠近尾部查找次数越多。
添加元素到尾部：动态数组尾部添加直接在数组尾部对应的index添加值即可，虽然可能有扩容操作，但是均摊下来依旧是O(1)。单向链表需要从头节点一直找到尾节点，为O(n)。
删除尾部元素：动态数组尾部添加直接在数组尾部对应的index添加值即可，固定1次操作。单向链表需要从头节点一直找到尾节点，为O(n)。
添加元素到头部：动态数组需要最大的挪动元素次数，为O(n)。单向链表只需要1次操作。
删除头部元素：动态数组需要最大的挪动元素次数，为O(n)。单向链表只需要1次操作。

由上面的分析可以直到，单向链表并不是所有情况下时间复杂度都优于动态数组的，当需要频发的删除和添加到数组头部时，单向链表优于动态数组。当需要频发的删除和添加到数组尾部时，动态数组优于单向链表。

下面测试一下：

进行10000次头部的插入和删除操作，动态数组和单向链表对比：

进行10000次尾部的插入和删除操作，动态数组和单向链表对比：

所以并不是说单向链表就一定时间复杂度上优于动态数组，依然要区分在不同的应用场景。如果需要频繁的对数组头部进行插入和删除操作，单向链表是大大优于动态数组的。如果是需要频繁的在数组尾部进行插入和删除操作，动态数组又是大大优于单向链表的。

源码

点击查看源码