定义

线性表（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 指针）。

时间上

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 是因为我们是单链表实现，为什么叫做单链表？因为后面还有循环链表。在这里不多阐述。
有的同学可能会问我，为什么要搞个协议出来，额，因为我实现的链表是带头结点的链表。这个，确实忘记说了，我的锅。

什么是头结点呢？

图 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.