浅谈iOS 数据结构之链表

浅谈iOS 数据结构之链表

在计算机科学中，链表是一种数据结构，用于存储一系列按顺序排列的元素。链表的一个关键点是它不需要连续的内存空间来存储元素，相反，每个元素由一个指向下一个元素的指针组成。在iOS开发中，链表在各种场景下都有所应用，如UITableView和UICollectionView的数据源等。本文将详细讲解链表的基本知识和使用技巧。

链表的基本知识

链表由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的指针。链表的头节点包含第一个元素的数据和指向下一个元素的指针；链表的尾节点没有指向下一个元素的指针（或指向null）。链表可以分为单向链表、双向链表和循环链表三种类型。

单向链表

单向链表每个节点只有一个指向下一个节点的指针，不能反向遍历链表。以下是单向链表的定义：

@interface ListNode : NSObject

@property (nonatomic, strong) id value;
@property (nonatomic, strong) ListNode *next;

@end

在单向链表中，每个节点的next指针指向下一个节点，最后一个节点的next指针为null。

双向链表

双向链表每个节点有两个指针，一个指向前面的节点，一个指向后面的节点，可以反向遍历链表。以下是双向链表的定义：

@interface DoubleListNode : NSObject

@property (nonatomic, strong) id value;
@property (nonatomic, strong) DoubleListNode *next;
@property (nonatomic, strong) DoubleListNode *prev;

@end

在双向链表中，每个节点的next指针指向下一个节点，prev指针指向上一个节点。头节点的prev指针为null，尾节点的next指针为null。

循环链表

循环链表在单向链表和双向链表的基础上增加了一个特性，即尾节点的next指向头节点，形成一个闭环。以下是循环链表的定义：

@interface CircleListNode : NSObject

@property (nonatomic, strong) id value;
@property (nonatomic, strong) CircleListNode *next;

@end

在循环链表中，每个节点的next指针指向下一个节点，最后一个节点的next指针指向头节点。

链表的使用技巧

链表可以用于解决一些特定的问题，如链表的排序、链表的合并、链表的反转等，以下是两个链表问题的示例：

链表的排序

将一个单向链表从小到大排序，可以使用插入排序的方式。具体做法是从第二个节点开始，将节点插入已排序部分中正确的位置。

- (ListNode *)sortList:(ListNode *)head {
    if (!head || !head.next) {
        return head;
    }
    ListNode *dummy = [[ListNode alloc] init];
    dummy.next = head;
    ListNode *pre = dummy;
    ListNode *cur = head;
    while (cur) {
        if (cur.next && [cur.next.value integerValue] < [cur.value integerValue]) {
            while (pre.next && [pre.next.value integerValue] < [cur.next.value integerValue]) {
                pre = pre.next;
            }
            ListNode *temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
            pre = dummy;
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;
}

以上代码中，我们使用了dummy节点作为头节点的前驱节点，避免头节点无法排序的问题。

链表的合并

将两个有序链表合并成一个有序链表，可以使用递归的方式。具体做法是比较两个链表的头节点的大小，将较小的节点和后续节点重新合并。

- (ListNode *)mergeList:(ListNode *)head1 withList:(ListNode *)head2 {
    if (!head1) {
        return head2;
    }
    if (!head2) {
        return head1;
    }
    if ([head1.value integerValue] < [head2.value integerValue]) {
        head1.next = [self mergeList:head1.next withList:head2];
        return head1;
    } else {
        head2.next = [self mergeList:head2.next withList:head1];
        return head2;
    }
}

以上代码中，我们使用递归的方式不断将两个有序链表的头节点进行比较和合并。

总结

链表是一种常用的数据结构，在iOS开发中也有广泛的应用。本文对链表的基本知识和使用技巧做了详细的讲解和示例说明。在实际开发中，我们应根据具体问题的需要，选择恰当的链表类型和使用方法。