数据结构系列：Objective-C实现单链表

作者: ChinaChong | 来源:发表于2018-11-22 14:30 被阅读1次

摘自《维基百科》

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

单向链表

摘自《维基百科》

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针，见下一篇的双向链表）节点。

这种普通的，每个节点只有一个指针的链表也叫单向链表，或者单链表，通常用在每次都只会按顺序遍历这个链表的时候（例如图的邻接表，通常都是按固定顺序访问的）。

单向链表的大致情况介绍完毕，以上就是维基百科中对于单向链表的简介。接下来我以最简单的形式实现单向链表，链表中的节点储存最基础的数据类型NSInteger，便于思考也方便初学者学习。好了，程序员的世界没有BB，直接上源码！下面就是单向链表的核心实现代码以及实例调用。

@implementation SinglyLinkedList

/**
 初始化一个单向链表
 
 @param node 链表的头节点
 @return 返回一个已初始化的单向链表
 */
- (instancetype)initWithNode:(SinglyLinkedListNode *)node {
    self = [super init];
    
    if (self) {
        self.headNode = node;
    }
    
    return self;
}

/**
 判断链表是否为空
 
 @return 为空返回YES，反之为NO
 */
- (BOOL)isEmpty {
    return self.headNode == nil;
}

/**
 获取链表拥有的总节点数
 
 @return 总节点数
 */
- (NSInteger)length {
    // cur游标(指针),用来移动遍历节点
    SinglyLinkedListNode *cur = self.headNode;
    
    // count记录数量
    NSInteger count = 0;
    
    while (cur) {
        count++;
        cur = cur.nextNode;
    }
    
    return count;
}

/**
 遍历链表
 */
- (void)travel {
    // 空链表的情况
    if ([self isEmpty]) return;
    
    SinglyLinkedListNode *cur = self.headNode;
    
    while (cur) {
        NSLog(@"%ld",cur.element);
        cur = cur.nextNode;
    }
}

/**
 头插法：在链表的头部插入节点
 
 @param item 插入的元素
 */
- (void)insertNodeAtHeadWithItem:(NSInteger)item {
    SinglyLinkedListNode *node = [[SinglyLinkedListNode alloc] initWithItem: item];
    
    node.nextNode = self.headNode;
    self.headNode = node;
}

/**
 尾插法：在链表的尾部插入节点
 
 @param item 插入的元素
 */
- (void)appendNodeWithItem:(NSInteger)item {
    SinglyLinkedListNode *node = [[SinglyLinkedListNode alloc] initWithItem: item];
    
    if ([self isEmpty]) {
        self.headNode = node;
    }
    else {
        SinglyLinkedListNode *cur = self.headNode;
        
        while (cur.nextNode) {
            cur = cur.nextNode;
        }
        
        cur.nextNode = node;
    }
}

/**
 指定位置插入节点
 
 @param item 插入的元素
 @param index 位置的索引
 */
- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index {
    
    if (index <= 0) {
        [self insertNodeAtHeadWithItem: item];
    }
    else if (index > ([self length] - 1)) {
        [self appendNodeWithItem: item];
    }
    else {
        SinglyLinkedListNode *pre = self.headNode;
        
        for (int i = 0; i < index - 1; i++) {
            pre = pre.nextNode;
        }
        
        SinglyLinkedListNode *node = [[SinglyLinkedListNode alloc] initWithItem: item];
        
        node.nextNode = pre.nextNode;
        pre.nextNode = node;
    }
}

/**
 删除节点
 
 @param item 删除的元素
 */
- (void)removeNodeWithItem:(NSInteger)item {
    SinglyLinkedListNode *cur = self.headNode;
    
    SinglyLinkedListNode *pre = [[SinglyLinkedListNode alloc] init];
    
    while (cur) {
        if (cur.element == item) {
            // 先判断此节点是否是头节点,如果是头节点
            if (cur == self.headNode) {
                self.headNode = cur.nextNode;
            }
            else {
                pre.nextNode = cur.nextNode;
            }
            cur = nil;
            break;
        }
        else {
            pre = cur;
            cur = cur.nextNode;
        }
    }
}

/**
 查询某个节点是否存在
 
 @param item 查询的元素
 @return 存在返回YES，反之为NO
 */
- (BOOL)searchNodeWithItem:(NSInteger)item {
    SinglyLinkedListNode *cur = self.headNode;
    
    while (cur) {
        if (cur.element == item) {
            return YES;
        }
        else {
            cur = cur.nextNode;
        }
    }
    
    return NO;
}

@end

实际使用案例


- (void)viewDidLoad {
    [super viewDidLoad];
    
    SinglyLinkedList *lkList = [[SinglyLinkedList alloc] initWithNode: nil];
    
    NSLog(@"%d", [lkList isEmpty]); // 1
    NSLog(@"%ld", [lkList length]); // 0
    
    [lkList appendNodeWithItem: 1];
    NSLog(@"%d", [lkList isEmpty]); // 0
    NSLog(@"%ld", [lkList length]); // 0
    
    [lkList appendNodeWithItem: 2];
    [lkList insertNodeAtHeadWithItem: 8];
    [lkList appendNodeWithItem: 3];
    [lkList appendNodeWithItem: 4];
    [lkList appendNodeWithItem: 5];
    
    [lkList appendNodeWithItem: 6];                 // 8 1 2 3 4 5 6
    [lkList insertNodeWithItem: 9   atIndex: -1];   // 9 8 1 2 3 4 5 6
    [lkList insertNodeWithItem: 100 atIndex: 3];    // 9 8 1 100 2 3 4 5 6
    [lkList insertNodeWithItem: 200 atIndex: 10];   // 9 8 1 100 2 3 4 5 6 200
    [lkList removeNodeWithItem: 100];               // 9 8 1 2 3 4 5 6 200
    
    [lkList travel];
    
    NSLog(@"result: %d", [lkList searchNodeWithItem:200]);
}

寡人的思路

初始化一个单向链表：- (instancetype)initWithNode:(SinglyLinkedListNode *)node;
初始化的时候可以指定头节点，也可以不指定，不指定头节点那么此时就是一个空链表。
判断链表是否为空：- (BOOL)isEmpty;
单向链表的所有操作在实现的时候都要从头节点入手，所以如果一个单向链表的头节点为空，则这个单向链表一定为空，反之则不为空。
获取链表拥有的总节点数：- (NSInteger)length;
初始化一个 SinglyLinkedListNode * 类型的游标指针 cur，让 cur 在开始的时候指向头节点。我们定义的单向链表在尾节点处指向了 nil ，所以 while 循环的判断条件 cur 一直到为空时，则说明此时已经遍历到最后的尾节点，那么这个 count 就是链表的总节点数（长度）。
遍历链表：- (void)travel;
遍历链表的思路与计算长度一样，都是让游标指针 cur 顺着 nextNode 一直遍历到尾节点。
头插法--在链表的头部插入节点：- (void)insertNodeAtHeadWithItem:(NSInteger)item;
方法的目的是要把节点 node 插入到链表头部，即第一个位置。那么节点 node 在插入成功后就会成为新的头节点，而原头节点则变成新头节点的 nextNode 。
尾插法--在链表的尾部插入节点：- (void)appendNodeWithItem:(NSInteger)item;
- 链表为空时：尾插法就相当于给链表添加头节点。
- 链表不为空时：方法中 while 循环的判断条件 cur.nextNode 在遍历到尾节点时为空，所以当循环停止时 cur 正指向尾节点。既然是尾插法，那就让尾节点的 nextNode 指向新节点 node 即可。
- 注意：尾插法需要判断此链表是否为空，如果为空，头节点本身就是 nil ，再给它的 nextNode 赋值就变得毫无意义。而前面的头插法则不然，即便链表为空，将 self.headNode 赋值给 node.nextNode 也只是相当于 node.nextNode = nil ，这符合单向链表的规则，它既是头节点又是尾节点也就是单节点的情况。
指定位置插入节点：- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index;
- 位置索引小于或等于 0 时：将新节点插入到头节点，调用头插法即可。
- 位置索引大于长度减 1时：即位置所以已越界，将新节点插入到尾节点，调用尾插法即可。
- 非头尾节点时：在指定位置插入节点，那就需要将新节点 node 插入到索引 index 处节点和它前面的节点之间。前面节点的 nextNode 应该指向 node ，node 的 nextNode 指向索引 index 处的节点，这样才算是在指定位置插入。所以我们必须已知索引 index 处节点和其前面的节点，这样在构造 for 循环的时候，就必须让循环次数为 index - 1，这样在循环结束时我们拿到的是 index 位置前面的节点，又可以利用它的 nextNode 拿到 index 处的节点。
删除节点：- (void)removeNodeWithItem:(NSInteger)item;
- 代码中 cur 指向将删除的节点，pre 指向其前一个节点。
- 删除节点的核心思路在于，要把将删除节点的前一个节点和后一个节点连接起来。
- 举个例子：比如链表 node0→node1→node2→nil，想要删除node1，就要把 node0 和 node2 连接起来，即让 node0.nextNode 指向 node2 。node2 可以通过 node1.nextNode 获取，但是如果只有一个指向 node1 的游标 cur 则取不到 node0 ，所以还需要一个指向 node1 前一个节点 node0 的游标 pre。
- 删除时要考虑两种情况：删除头节点 / 删除非头节点。前面刚刚说的是非头节点的情况。如果删除的是头节点，那么就不需要考虑 pre 指针，直接让头节点指向它的下一个节点即可。
查询某个节点是否存在：- (BOOL)searchNodeWithItem:(NSInteger)item;
没啥可说的，就老老实实顺着节点的 nextNode 一直往下找就行了，找到就返回 YES ，找不到就返回 NO。

单向循环链表

摘自《维基百科》

在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存，假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

@implementation SinglyCycleLinkedList

/**
 初始化一个单向循环链表

 @param node 链表的头节点
 @return 返回一个已初始化的单向循环链表
 */
- (instancetype)initWithNode:(SinglyCycleLinkedListNode *)node {
    self = [super init];
    
    if (self) {
        self.headNode = node;

        // 判断node不为空的情况，循环指向自己
        if (node) {
            node.nextNode = node;
        }
    }
    return self;
}

/**
 判断链表是否为空

 @return 为空返回YES，反之为NO
 */
- (BOOL)isEmpty {
    return self.headNode == nil;
}

/**
 获取链表拥有的总节点数

 @return 总节点数
 */
- (NSInteger)length {
    if ([self isEmpty]) return 0;
    
    SinglyCycleLinkedListNode *cur =  self.headNode;
    
    NSInteger count = 1;
    
    while (cur.nextNode != self.headNode) {
        count++;
        cur = cur.nextNode;
    }
    
    return count;
}

/**
 遍历链表
 */
- (void)travel {
    // 空链表的情况
    if ([self isEmpty]) return;
    
    SinglyCycleLinkedListNode *cur = self.headNode;
    
    while (cur.nextNode != self.headNode) {
        NSLog(@"%ld", cur.element);
        cur = cur.nextNode;
    }
    
    // 退出循环，cur指向尾节点，但尾节点的元素未打印
    NSLog(@"%ld", cur.element);
}

/**
 头插法：在链表的头部插入节点

 @param item 插入的元素
 */
- (void)insertNodeAtHeadWithItem:(NSInteger)item {
    SinglyCycleLinkedListNode *node = [[SinglyCycleLinkedListNode alloc] initWithItem: item];
    
    if ([self isEmpty]) {
        self.headNode = node;
        node.nextNode = node;
    }
    else {
        SinglyCycleLinkedListNode *cur = self.headNode;
        
        while (cur.nextNode != self.headNode) {
            cur = cur.nextNode;
        }
        
        // 利用循环将游标指向尾节点，退出循环
        node.nextNode = self.headNode;
        self.headNode = node;
        cur.nextNode = self.headNode; // cur.nextNode = node;
    }
}

/**
 尾插法：在链表的尾部插入节点

 @param item 插入的元素
 */
- (void)appendNodeWithItem:(NSInteger)item {
    SinglyCycleLinkedListNode *node = [[SinglyCycleLinkedListNode alloc] initWithItem: item];
    
    if ([self isEmpty]) {
        self.headNode = node;
        node.nextNode = node;
    }
    else  {
        SinglyCycleLinkedListNode *cur = self.headNode;
        
        while (cur.nextNode != self.headNode) {
            cur = cur.nextNode; // 让游标指向尾节点
        }
        
        cur.nextNode = node;
        node.nextNode = self.headNode;
        
    }
}

/**
 指定位置插入节点

 @param item 插入的元素
 @param index 位置的索引
 */
- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index {
    if (index <= 0) {
        [self insertNodeAtHeadWithItem: item];
    }
    else if (index > ([self length] - 1)) {
        [self appendNodeWithItem:item];
    }
    else {
        // 这里需要的就是让游标指向前一个节点
        SinglyCycleLinkedListNode *pre = self.headNode;
        
        for (int i = 0; i < index - 1; ++i) {
            pre = pre.nextNode;
        }
        
        SinglyCycleLinkedListNode *node = [[SinglyCycleLinkedListNode alloc] initWithItem: item];
        node.nextNode = pre.nextNode;
        pre.nextNode = node;
    }
}

/**
 删除节点

 @param item 删除的元素
 */
- (void)removeNodeWithItem:(NSInteger)item {
    if ([self isEmpty]) return;
    
    SinglyCycleLinkedListNode *cur = self.headNode;
    SinglyCycleLinkedListNode *pre = [[SinglyCycleLinkedListNode alloc] init];
    
    // 这个循环的终点就是cur指向尾节点
    while (cur.nextNode != self.headNode) {
        if (cur.element == item) {
            if (cur == self.headNode) // 恰好这个cur指向的是头节点
            {
                // 我们需要先找到尾节点
                SinglyCycleLinkedListNode *rear = self.headNode;
                while (rear.nextNode != self.headNode) {
                    rear = rear.nextNode;
                }
                
                self.headNode = cur.nextNode;
                rear.nextNode = self.headNode;
                
            }
            else {
                pre.nextNode = cur.nextNode;
            }
            return;
        }
        else {
            pre = cur;
            cur = cur.nextNode;
        }
    }
    
    // 退出循环，cur指向尾节点
    if (cur.element == item) {
        if (cur == self.headNode) // 证明链表只有一个头节点
        {
            self.headNode = nil;
        }
        else {
            pre.nextNode = cur.nextNode;
        }
    }
}

/**
 查询某个节点是否存在

 @param item 查询的元素
 @return 存在返回YES，反之为NO
 */
- (BOOL)searchNodeWithItem:(NSInteger)item {
    if ([self isEmpty]) return NO;
    
    SinglyCycleLinkedListNode *cur = self.headNode;
    
    while (cur.nextNode != self.headNode) {
        if (cur.element == item) {
            return YES;
        }
        else {
            cur = cur.nextNode;
        }
    }
    
    // 循环结束，cur指向尾节点
    if (cur.element == item) {
        return YES;
    }
    
    return NO;
}

@end

实际使用案例

- (void)viewDidLoad {
    [super viewDidLoad];
    
    SinglyCycleLinkedList *ll = [[SinglyCycleLinkedList alloc] initWithNode: nil];
    
//    NSLog(@"%d", [ll isEmpty]); // 1
//    NSLog(@"%ld", [ll length]); // 0
    
    [ll appendNodeWithItem: 1];
//    NSLog(@"%d", [ll isEmpty]); // 0
//    NSLog(@"%ld", [ll length]); // 1
    
    [ll appendNodeWithItem: 2];
    [ll insertNodeAtHeadWithItem: 8];
    [ll appendNodeWithItem: 3];
    [ll appendNodeWithItem: 4];
    [ll appendNodeWithItem: 5];
    [ll appendNodeWithItem: 6];
//    [ll travel]; // 8 1 2 3 4 5 6

    [ll insertNodeWithItem: 9 atIndex: -1];
//    [ll travel]; // 9 8 1 2 3 4 5 6

    [ll insertNodeWithItem: 100 atIndex: 3];
//    [ll travel]; // 9 8 1 100 2 3 4 5 6

    [ll insertNodeWithItem: 200 atIndex: 10];
//    [ll travel]; // 9 8 1 100 2 3 4 5 6 200

    [ll removeNodeWithItem: 100];
    [ll travel]; // 9 8 1 2 3 4 5 6 200
    
    NSLog(@"result: %d", [ll searchNodeWithItem:200]); // result: 1
}

寡人的思路

初始化一个单向循环链表：与单向链表相比只是加了一个判断，若传进来的 node 不为空，让 node 循环指向自己。也就是头节点的 nextNode 指向头节点自己。
判断链表是否为空的方法的思路与单向链表一致。
获取链表拥有的总节点数：由于循环链表尾节点的 nextNode 不是指向 nil 而是指向头节点，所以 while 循环遍历到尾节点的条件也随之改变成 cur.nextNode != self.headNode 。这里不能像单向链表那样 count 从 0 开始直接进入到 while 循环计数，要先判断链表是否为空，空则 count = 0 那么返回 0，非空则 count 从 1 开始计数。
遍历链表：与单向链表相比只是 while 循环判断尾节点的条件不一样。
头插法--在链表的头部插入节点：头插法的核心目的是让节点 node 成为新的头节点。配合这个目的需要做三件事：
1、让 node 的 nextNode 指向原头节点。
2、让 self.headNode 指向新头节点 node。这是给 node 行加冠大礼，给它正名，不能只做实际的头节点，还要做名义上的头节点。
3、让尾节点的 nextNode 指向新头节点 node。

单向循环链表的头插法与单向链表的头插法有很大不同，主要有两方面原因：
- 循环链表的尾节点要指向头节点。因为这个条件在构造头插法时就必须找到尾节点，让尾节点指向头节点。
- 循环链表的头插法要判断链表是否为空。因为循环链表的头插法需要找到尾节点，那就依赖于链表需要不为空，如果为空，遍历过程则变得毫无意义。所以当链表为空时要单独处理，让头节点循环指向自己即可。
尾插法--在链表的尾部插入节点：尾插法的中心思想就是让 node 成为新的尾节点。为了这个中心思想首先得考虑链表是否为空，空就让头节点循环指向自己，如果是非空的情况则要办下面这三件事：
- 找到原尾节点
- 让原尾节点的 nextNode 指向新尾节点 node
- 让新尾节点的 nextNode 指向头节点
指定位置插入节点：与单向链表思路完全一致
删除节点：与单向链表几乎一致，区别在于对头节点和尾节点的处理。
- 头节点：删除头节点后，需要找到尾节点，让尾节点的 nextNode 指向头节点
- 尾节点：循环结束时刚好指向尾节点，所以在循环内并未处理尾节点，需要单独处理。尾节点如果就是头节点，说明链表只有一个节点，那么此时将其置空即可。反之则只需正常处理。
查询某个节点是否存在：与单向链表的区别是寻找尾节点的条件不一样，这就导致循环链表需要判断链表是否为空，尾节点要单独处理。

Github完整源码

单向链表
 单向循环链表

参考资料

链表-维基百科，自由的百科全书

数据结构系列：Objective-C实现单链表

单向链表

实际使用案例

寡人的思路

单向循环链表

实际使用案例

寡人的思路

Github完整源码

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

iOS

程序员

iOS程序猿