定义
线性表（linear list）是具有相同类型的n（n≥0）个数据元素a0，a1，…an-1组成的有限序列。
线性表有两种实现思路，一种是顺序表，还有一种就是我今天想说的链表。先来看看顺序表。
一、基于静态分配的数组的顺序表
相信学习过 C 语言的大家都知道 C 语言中的数组，例如：
int integerValues[10]; /// 10 个元素的整型数组 integerValues
这个整型数组 integerValues 就是一个线性表了，元素类型相同（int），个数为 10 （≥0），以 integerValues 为首地址，可以通过 *(integerValues + n) 来找到每个位置的元素（有序）。
这样的线性表就是基于静态分配的数组的顺序表。我们来从空间和时间上来分析下顺序表：
空间上：
1. 我们需要在程序执行之前，明确存储规模的大小。
如果线性表的长度变化比较大，难以确定，那么我们一般会设置一个足够大的值，来确保链表可以正常工作，但是这个估值会造成很大的空间浪费；如果估值不是足够大的话，就会造成溢出，程序错误；
**2. 存储密度 为 1。 **
如果线性表的长度变化不大，或者不变，这个时候适合采用顺序表的方式，节约存储空间。
时间上
1. 在获取表中某一个位置 n 的元素的时间复杂度为 O(1) 。
例如：要获取 integerValues 中第 n 个位置的元素，只需要 integerValues[n] 即可，获取每一个位置的时间为常量时间；
2. 在插入或者删除顺序表时，需要较多的时间。
比如说例中的 integerValues 表中已经有了五个元素，如果我们想在表中第 0 个位置插入一个元素，那么我们就要依次把之前就存在的五个元素依次向后移动一个位置，然后把新的元素放在 0 的位置上。
我们可以看出，在插入或者删除某个元素时，顺序表的大部分操作都在移动结点上，当每个结点的信息量较大的时候，时间上的开销相当可观。
总结：
当表长变化不大，容易事先确定大小，且主要操作是查询的时候，我们可以优先考虑使用顺序表。
二、链表
既然我们已经知道了顺序表的使用场景，那么在表长变化较大、插入和删除操作频繁的时候，怎么办呢？ 这个时候，就可以优先考虑链表了。
什么是链表呢？
老实说，我在看到链表的时候，给我的感觉就是，这个东西还可以这样做！当真是惊为天人，心里感受到那种由衷地佩服。用一张图来描述下链表吧：
图 1 链表的思想
-
如图 1 所示，链表中的每个结点在内存中的位置是无序的，但是每个结点都知道自己的下一个结点。这样，就可以从结点 0 -> 1 -> 2 -> ... -> n 一直找到结点 n 了。如果 n 没有下一个结点，或者说 n 的下一个结点为空，那么 n 也就是最后一个结点了。
-
在插入和删除方面，如图 2 所示，我们要在 5 和 6 之间插入一个 100 的话， 那么只需要构造一个结点，将 100 存储。然后让 结点 100 的下一个指向 6 ，再让结点 5 的下一个指向结点 100，其他结点不变 (如图 2 所示)
图 2 链表的插入操作示意图
，删除原理类似；
-
在查找放面，我们要查找某一个位置 (n) 的元素，就要从第一个结点 0 开始，通过下一个的方式一直找到第 n 个结点，所以查询特定的某个元素的时间复杂度是 O(n)。
这样的链式存储结构就叫做链表，物理存储结构是不连续的，而通过 next (下一个)指针，达到逻辑上的有序。我们还是来从空间和时间上分析下链表：
空间上
1.动态分配内存（只要内存还有空闲，我们就可以通过 next 来扩大这个线性表），因此线性表不需要事先明确表长；
2.存储密度 < 1（因为每一个结点不只是存储了数据，还存储了下next 指针）。
时间上
**我们把顺序表和链表一起总结一下吧，我盗了张图.. (如图 3)1.在获取某一个元素时，需要从头开始扫描链表才能获得；
2.在不考虑查找时，插入和删除只需要修改指针就可以。
图 3 顺序表在时间和空间上的分析比较
**
定义一个线性表
啰嗦了这么多，我们来看看如何定义一个线性表吧（顺序表我就不说了，至于静态链表（游标）的实现，我也不说了，感兴趣的同学可以自行查阅。对了，还有说一下，作者是 iOSer， 链表的实现我会用 Objective-C 来实现，而且，实现的是思想，同学们千万别问我 Swift 怎么实现之类的，我觉得没有意义）。线性表的基本抽象如下：
#import <Foundation/Foundation.h>
@interface CHRLinearList : NSObject
/// 线性表是否为空
@property (nonatomic, assign, readonly) BOOL isEmpty;
/// 线性表内元素的个数
@property (nonatomic, assign, readonly) NSUInteger count;
/// 构造方法(整表创建)
- (nonnull instancetype)initWithObjects:(nullable id)objects,... NS_REQUIRES_NIL_TERMINATION;
/// 获取线性表中某一位置的元素，如果超过长度，崩溃
- (nonnull id)objectAtIndex:(NSUInteger)index;
/// 给定一个元素，返回元素在线性表中的位置，如果不存在，返回 NSNotFound
- (NSUInteger)indexOfObject:(nonnull id)object;
/// 向线性表中某一位置插入元素，如果超出链表长度，崩溃
- (void)insertObject:(nonnull id)object atIndex:(NSUInteger)index;
/// 从线性表中删除某一位置的元素，如果超出长度，崩溃
- (nonnull id)removeObjectAtIndex:(NSUInteger)index;
/// 给定一个元素，判断线性表是否包含这个元素，如果包含返回 YES，否则返回 NO
- (BOOL)containsObject:(nonnull id)object;
/// 清空线性表
- (void)removeAllObjects;
@end
这个命名风格完全按照 Objective-C 的风格来， 其实可以说抄袭了 NSArray (NSMutableArray) 的，不过 NSArray 的实现会比这个复杂的多，感兴趣的同学可以查查看哈，我们的主题是链表。
来看看我的链表实现吧，希望大家仔细看看，如有错误，欢迎指正，共同进步共同提升。
结点协议
#import <Foundation/Foundation.h>
@protocol CHRSinglyLinkedListNodeProtocol <NSObject>
@property (nonatomic, strong, readwrite, nonnull) id data;
@property (nonatomic, strong, readwrite, nullable) id <CHRSinglyLinkedListNodeProtocol> next;
@end
只要接受了这个协议的对象，就可以看做是链表的结点。这里起名叫做 Singly 是因为我们是单链表实现，为什么叫做单链表？因为后面还有循环链表。在这里不多阐述。
有的同学可能会问我，为什么要搞个协议出来，额，因为我实现的链表是带头结点的链表。这个，确实忘记说了，我的锅。
什么是头结点呢？
其实道理一样简单，在 0->1->2->...->9 这个链表中，我们要知道 0 的存在，才能完成链表的后续操作。逻辑上是没问题的，只是实现起来稍微麻烦一点。如果把链表本身也当成一个结点，那么链表本身也是一个结点，只不过链表的 data 不会存储任何值，只是把链表当做结点来操作。如果头结点的 next 为空，则链表为空，反之链表不为空。那么图 1 也就变成了这样（如图 4 所示）：
图 4 带头结点的链表
如果没有头结点，实现起来代码会比较烦，至于如何烦，大家等看完了带头结点的实现之后，自己思考一下。
我们接着看下结点的定义和实现：
结点的定义
#import "CHRSinglyLinkedListNodeProtocol.h"
@interface CHRSinglyLinkedListNode : NSObject <CHRSinglyLinkedListNodeProtocol>
@end
结点的实现
#import "CHRSinglyLinkedListNode.h"
@interface CHRSinglyLinkedListNode ()
{
id _data;
id _next;
}
@end
@implementation CHRSinglyLinkedListNode
@synthesize data = _data;
@synthesize next = _next;
@end
这里的代码很简单，结点只有两个属性，一个是 data ，一个是 next 。data 就是我们要存储的数据，例如图 1 中的数字 0 ； next 是下一个指针，相当于图 1 中的 0 -> 1 中的线，记录结点之间的关系。
我们从外界传入的数据，先用结点包装起来，然后内部操作的是结点。这样外部就不知道结点这样一个东西，也就对外部黑盒，降低耦合。
我们来看看链表的 header 和 实现：
链表的 header
#import "CHRSinglyLinkedListNodeProtocol.h"
@interface CHRSinglyLinkedListNode : NSObject <CHRSinglyLinkedListNodeProtocol>
@end
链表的 header 很简单，只是继承了线性表，实现线性表的抽象（因为还有静态表，顺序表等实现么..）。
看看重点，链表的实现（代码有点多，大家耐心来看，我会加上注释）：
链表的实现
#import "CHRSinglyLinkedList.h"
#import "CHRSinglyLinkedListNode.h"
/// 这里， self 就是头结点，所以 self 接受了CHRSinglyLinkedListNodeProtocol （结点协议）
@interface CHRSinglyLinkedList () <CHRSinglyLinkedListNodeProtocol>
{
id _data;
id _next;
}
@end
@implementation CHRSinglyLinkedList
/// 合成属性，实现协议的方法
@synthesize data = _data;
@synthesize next = _next;
/// 构造方法
- (nonnull instancetype)initWithObjects:(nullable id)objects,...
{
self = [super init];
if (self) {
/// self 是头结点， 我们用一个 prior 上一个指针，指向头结点
id <CHRSinglyLinkedListNodeProtocol> prior = self;
/// 可变参数的获取（大家可以自行百度）
va_list params;
va_start(params, objects);
/// 第一个元素，可能为空
id object = objects;
/// 如果元素不为空
while (object) {
/// 构造新的结点
CHRSinglyLinkedListNode *node = [[CHRSinglyLinkedListNode alloc] init];
/// 将数据存储到 新的结点的 data 属性中
node.data = object;
/// 上一个结点的 next 指针指向 新的结点
prior.next = node;
/// 上一个结点更新为新的结点
prior = node;
/// 获取下一个元素
object = va_arg(params, id);
}
/*
第一次循环开始
大概的意思是这样， 如果可变参数有三个，0 , 1, 2
那么先把 0 存储到 node 中
然后 prior （self）.next = node;
然后 prior 更新成 node（此时 node 存储的数据是 0，我们用 node0 表示），prior 已经变成了 node0
第一次循环结束
第二次循环开始
还是，将数据 1 包装到 node1 中，
prior(node0).next = node1;
prior 更新成 node1
第二次循环结束
第三次循环开始
同样，将数据 2 包装到 node2 中，
prior(node1).next = node2;
prior 更新成 node2
第三次循环结束
while (object)， object 为 nil，循环结束
这时链表的结构是这样的
self.next -> node0 -> node1 -> node2->nil
如果大家不明白这个代码，希望大家好好看一看，画一画，下面会用到很多这种技术
*/
/// 结束读取可变参数
va_end(params);
}
return self;
}
- (BOOL)isEmpty
{
/// 如果头结点（self）的 next 不存在，那么链表为空
return !self.next;
}
- (NSUInteger)count
{
/// 其实个数完全可以通过计算来存储，即在创建表之后，每次删除、插入、清空表的时候，可以计算出来，这样就不用每次遍历整个表来浪费操作，不过为了大家熟悉这样的思路，和 while 循环，这里还是用了这种方式
/// 初始化个数 count 为 0
NSUInteger count = 0;
/// 声明一个指针，指向第一个结点
id <CHRSinglyLinkedListNodeProtocol> node = self.next;
/*
第一次循环开始
如果第一个（node0）结点存在，
那么， count 自增 1
node = node0; 更新成第一个结点
第一次循环结束
第二次循环开始
如果第二个node（node1）结点存在，
那么， count 自增 1
node = node1; 更新成第二个结点
第二次循环结束
...
/*
while (node) {
node = node.next;
count++;
}
/// 当退出循环之后， count 即为 链表中 结点的个数，也就是存储元素的个数，相当于遍历了一遍整个链表
/// 大家再看下哈，下面我就不这么写注释了..
return count;
}
- (CHRSinglyLinkedListNode *)objectAtIndex:(NSUInteger)index
{
NSUInteger ctrIndex = 0;
id <CHRSinglyLinkedListNodeProtocol> node = self.next;
while (node && ctrIndex < index) {
node = node.next;
ctrIndex++;
}
/// 通过 index 找到对应 位置的结点
/// 如果 结点不存在，说明 这个 index 位置的 结点为空，即超过了链表的长度，俗称越界了，这里用了断言
NSAssert(node, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素", __FILE__, __LINE__, @(ctrIndex));
/// 断言成功，返回存储的数据元素
return node.data;
}
- (NSUInteger)indexOfObject:(id)object
{
/// 遍历链表
NSUInteger index = 0;
id <CHRSinglyLinkedListNodeProtocol> node = self.next;
while (node) {
/// 如果找到 相同的元素，返回 index，（对象等同性请自行查阅）
if ([node.data isEqual:object]) {
return index;
}
index++;
node = node.next;
}
/// 如果过了循环还没有找到，说明表中不存在相同的 object， 返回 NSNotFound
return NSNotFound;
}
- (void)insertObject:(id)object atIndex:(NSUInteger)index
{
NSAssert(object, @"%s, %d, 向线性表中插入了 nil 是不允许的", __FILE__, __LINE__);
CHRSinglyLinkedListNode *node = [[CHRSinglyLinkedListNode alloc] init];
node.data = object;
id <CHRSinglyLinkedListNodeProtocol> prior = self;
NSUInteger ctrIndex = 0;
while (prior && ctrIndex < index) {
ctrIndex++;
prior = prior.next;
}
/// 找到要插入位置的前驱结点（也就是上一个）
/// 断言前驱结点存在，如果不存在，也就是越界了
NSAssert(prior, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素", __FILE__, __LINE__, @(ctrIndex));
/// 好好看一下这两行代码，并且真正理解
/// 我们构造好了要插入的结点 node
/// 如果原来的表是这样的: prior -> nodeX - >nodeY
/// 那么插入后应该是这样的结构: prior -> node -> nodeX -> nodeY
/// 先将 node -> nodeX 写出来，也就是
/// 然后再 prior -> node
/// 如果顺序调换了，那么结构就变成了 proir -> node -> node，因为 prior.next 已经变成了 node
/// 这样写，也不用写一个中间变量 temp
node.next = prior.next;
prior.next = node;
}
- (id)removeObjectAtIndex:(NSUInteger)index
{
id <CHRSinglyLinkedListNodeProtocol> prior = self;
NSUInteger ctrIndex = 0;
while (prior.next && ctrIndex < index) {
prior = prior.next;
ctrIndex++;
}
/// 断言和插入原理类似，找到前驱结点（上一个）prior
NSAssert(prior, @"%s, %d 线性表越界， 当前线性表共有 %@ 个元素", __FILE__, __LINE__, @(ctrIndex));
/*大概思路：
prior-> node -> nodeX -> nodeY，我们要删除 node， 让链表变成 prior -> nodeX -> nodeY
我们先保留 node 的引用
然后让 prior.next = node.next， 也就是 prior -> nodeX -> nodeY
但是， node 本身的 next 还在，我们抹去这个 next 的存在
node.next = nil;
*/
id <CHRSinglyLinkedListNodeProtocol> node = prior.next; /// 要删除的节点，保留一份引用
prior.next = node.next;
node.next = nil;
return node.data;
}
- (BOOL)containsObject:(id)object
{
/// 原理类似于 indexOfObject
id <CHRSinglyLinkedListNodeProtocol> node = self.next;
while (node) {
if ([node.data isEqual:object]) {
return YES;
}
node = node.next;
}
return NO;
}
- (void)removeAllObjects
{
id <CHRSinglyLinkedListNodeProtocol> head = self;
/// 做了一遍循环删除
while (head.next) {
id <CHRSinglyLinkedListNodeProtocol> temp = head.next; /// 要删除的节点
head.next = temp.next;
temp.next = nil;
}
}
@end
结尾
今天先写到这吧，这图画的丑了点..请原谅，大概的思路相信我写的还算是清楚吧...... 具体代码我放到这里，文件夹是 Chris 下面的，估计现在就我自己写了吧.. 感兴趣的朋友可以私聊我， 大家一起学习。下班下班，回家吃饭。
这里有个 Q 群 (群号: 139852091 ) ，聊天吹水，技术实现，什么都聊，想来玩玩的朋友，速速加入哈。
Im Chris，a student.
网友评论