iOS--数据结构之线性表

红花当然配绿叶 这一辈子谁来陪
渺渺茫茫来又回 往日情景再浮现
藕虽断了丝还连 轻叹世间事多变迁
停停停，好好写线性表，唱个锤子歌。

线性表：零个或者多个数据元素的有限序列。元素之间是有序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继。线性表是有限的）

线性表的个数定义为线性表的长度 个数为0即是空表。
在复杂的线性表中，一个数据元素可以由若干个数据项组成。

此文主要总结线性表的相关概念，线性表的顺序存储结构、线性表的链式存储结构以及线性表在iOS中的应用三个方面来阐述。

• 线性表的顺序存储结构

线性表的顺序存储结构： 指的是用一段地址连续的存储单元依次存储线性表的数据元素。

1>线性表的顺序存储结构示意图：

线性表的顺序存储结构（摘自网络）

2>线性顺序表的结构体示意：

typedef int ElemType;//int类型的数据

typedef NS_ENUM(NSUInteger, Status) {
    
    ERROR = 0,//失败或者报错
    SUCCESS = 1,//成功
    
};
#define MAXSIZE 20 //存储空间初始化分配量 线性表的最大长度

typedef struct SQList {
    
    ElemType data[MAXSIZE];//数组存储数据元素 最大值为MAXSIZE 数组data，它的存储位置就是存储空间的存储位置
    int length; //线性表当前长度
    int listSize;//数组的最大长度
    
}SQList;

需要注意的是：

1.数组的长度是存放线性表的存储空间的长度。
2.线性表的长度是线性表中数据元素的个数，随着线性表的增删改查，线性表的长度是有变化的。
3.在任意时刻，线性表的长度该小于等于数组的长度。

线性表长度length和数组的最大长度listSize示意图

3>线性顺序表的初始化：

/**
 初始化线性表
 */
SQList initSequentialList(int listLength)
{
    
    SQList list;
    list.length = 0;
    listLength = (listLength >= MAXSIZE) ? MAXSIZE : listLength;
    for (int i = 0; i < listLength; i++) {
        
        ElemType elem = rand() % 100 + 1;//100以内的随机数
        list.data[i] = elem;
        list.length++;
        
    }
    list.listSize = MAXSIZE;
    
    return list;
    
}

4>获得线性表元素操作：

思路：
1.线性表不能为空。
2.下标不能小于1。
3.下标i不能大于线性表长。
时间复杂度：O(1)

/**
 获得链表元素操作
 思路：
 1.线性表不能为空
 2.下标不能小于1
 3.下标i不能大于线性表长
 时间复杂度 O（1）

 @param list SQList
 @param I 下标
 @return 状态
 */
Status GetElem (SQList list, int i)
{
    if (list.length == 0 || i < 1 || i > list.length) {
        return ERROR;
    }
    ElemType elem = list.data[i - 1];
    
    RYQLog(@"获得链表元素操作   elem = %d ", elem);
    
    return SUCCESS;
}

5>线性表的插入操作：

思路：
1.插入位置不合理，抛出异常。例如数组的长度为20，线性表的长度为10，插入的位置是15，显然不合规矩的，顺序线性链表中的元素是连续的。
2.如果未向线性表中插入数据之前，线性表的长度等于数组长度（不可能大于），则抛出异常或动态增加容量。
3.从第i个位置遍历到最后一个元素，将这些元素都向后移动一个位置。
4.将要插入的元素放置到位置i处。
5.线性表长length加一。
时间复杂度 O（n）

/**
 线性表的插入操作
 思路：
 1.插入位置不合理，抛出异常。例如数组的长度为20，线性表的长度为10，插入的位置是15，显然不合规矩的，顺序线性链表中的元素是连续的。
 2.如果未向线性表中插入数据之前，线性表的长度等于数组长度（不可能大于），则抛出异常或动态增加容量
 3.从第i个位置遍历到最后一个元素，将这些元素都向后移动一个位置
 4.将要插入的元素放置到位置i处
 5.线性表长length加一
 时间复杂度 O（n）

 @param list SQList
 @param I 下标
 @param elem ElemType
 @return 状态
 */
Status ListInsert (SQList *list, int i , ElemType elem)
{
    int k;
    //线性表已填满  此处先暂时抛出异常
    if (list->length >= list->listSize) {
        return ERROR;
    }
    //插入位置不合理，抛出异常。
    if (i < 1 || i > list->length+1) {
        return ERROR;
    }
    //插入位置在表尾 不需要移动元素，在i(其他位置)，从第i个位置遍历到最后一个元素，将这些元素都向后移动一个位置
    if (i < list->length) {
        
        for (k = list->length-1 ; k > i - 1; k--) {
            list->data[k+1] = list->data[k];
        }
        
    }
    //新元素的赋值
    list->data[i-1] = elem;
    list->length ++;
//    //查询
//    GetElem(list, i);
    
    return SUCCESS;
}

6>线性表的删除操作:

思路:
1.如果删除位置不合理，抛出异常。例如数组的长度为20，线性表的长度为10，删除的位置是15，显然不合规矩的，顺序线性链表中的元素是连续的。
2.取出删除的元素。
3.从删除元素的位置开始遍历到最后一个元素结束，分别将他们都向前移动1个位置。
4.线性表长length减一。
时间复杂度 O（n）

/**
 线性表的删除操作
 思路:
 1.如果删除位置不合理，抛出异常。例如数组的长度为20，线性表的长度为10，删除的位置是15，显然不合规矩的，顺序线性链表中的元素是连续的。
 2.取出删除的元素
 3.从删除元素的位置开始遍历到最后一个元素结束，分别将他们都向前移动1个位置。
 4.线性表长length减一
 时间复杂度 O（n）

 @param list SQList
 @param I 下标
 @return 状态
 */
Status ListDelete (SQList *list, int i)
{
    int k;
    //线性表为空
    if (list->length == 0) {
        return ERROR;
    }
    //删除位置不正确
    if (i < 1 || i > list->length) {
        return ERROR;
    }
    //取出删除的元素
    ElemType elem = list->data[i-1];
    RYQLog(@"要删除的元素 elem = %d", elem);
    //删除的位置在表尾 不需要移动元素，在i(其他位置)，从第i个位置遍历到最后一个元素，将这些元素都向前移动一个位置
    if (i < list->length) {
        
        for (k = i; k < list->length; k++) {
            list->data[k-1] = list->data[k];
        }
        
    }
    list->length--;
    
    return SUCCESS;
}

7>为一个线性顺序表添加数据:

/**
 为一个线性顺序表添加数据

 @param list SQList
 @param elem ElemType
 */
void addElemToList(SQList *list, ElemType elem)
{
    //线性表已填满  此处先暂时抛出异常
    if (list->length >= list->listSize) {
        RYQLog(@"线性表已填满");
        return;
//        //线性表的l扩容
//        sequentialListDilatation(list);
    }
    int length = list->length;
    RYQLog(@"%d", length);
    //新元素的赋值
    list->data[list->length] = elem;
    list->length ++;
//    travelWholeList(*list);
}

8>判断线性表是否为空：

/**
 线性表是否为空

 @param list 线性顺序存储表
 @return ERROR 不为空； SUCCESS 为空；
 */
Status ListisEmpty(SQList list)
{
    if (list.length == 0) {
        RYQLog(@"线性表为空");
        return SUCCESS;
    }
    RYQLog(@"线性表不为空");
    return ERROR;
}

9>判断线性表是否已满:

/**
 线性表是否已满

 @param list 线性顺序存储表
 @return ERROR 线性表未满；SUCCESS 线性表已满
 */
Status ListisFull(SQList list)
{
    if (list.length >= list.listSize) {
        RYQLog(@"线性表已满");
        return SUCCESS;
    }
    RYQLog(@"线性表未满");
    return ERROR;
}

10>元素是否在线性顺序表中:

/**
 元素是否在线性顺序表中

 @param list 线性顺序存储表
 @param elem 元素
 @return ERROR 不存在；SUCCESS 存在
 */
Status ElemisExitInList(SQList list, ElemType elem)
{
    int index = -1;
    
    for (int i = 0; i < list.length; i++) {
        
        ElemType currentElem = list.data[I];
        if (currentElem == elem) {
            
            index = I;
            RYQLog(@"元素在线性顺序表中 他是第%d个元素", index+1);
            return SUCCESS;
        }
        
    }
    
    RYQLog(@"元素不存在线性顺序表中");
    
    return ERROR;
}

11>遍历打印表中的所有元素:

/**
 遍历打印表中的所有元素

 @param list 线性表
 */
void travelWholeList(SQList list)
{
    for (int i = 0; i < list.length; i++) {
        
        RYQLog(@"第%d个元素  它的值为%d", i+1, list.data[I]);
        
    }
}

12>线性顺序表的销毁：

/**
 线性顺序表的销毁
 */
void destoryLinkList (SQList list)
{
    free(&list);
}

13>两个线性表的合并 A表和B表两个表合并后的新表里面，没有重复的元素。（A与B的并集）:

/**
 两个线性表的合并 A表和B表两个表合并后的新表里面，没有重复的元素。（A与B的并集）
 */
void combineTwoLinkLists ()
{
    SQList secondList = initSequentialList(5);
    SQList firstList = initSequentialList(10);
    int firstLength = firstList.length;
    int secondLength = secondList.length;
    //如果firstLength + secondLength > firstList.listSize 表示该线性表的数组的最大容量需要增大。
    if (firstLength + secondLength > firstList.listSize) {
        firstList.listSize = firstLength + secondLength;
    }
    //将secondList表中的元素 一个个插入到firstList表中
    for (int i = 0; i < secondLength; i++) {
        //从secondList表中将元素一个个取出来
        ElemType elem = secondList.data[i];
        //检测取出来的元素在firstList中是否存在
        Status type = ElemisExitInList(firstList, elem);
        //如果不存在 则将elem插入放到firstList表中
        if (type == ERROR) {
            addElemToList(&firstList, elem);
        }
    }
    RYQLog(@"两个线性表的合并   %d", firstList.length);
}

14>两个线性表的拼接 不考虑A表和B表中是否有重复的元素。直接将B表拼接在A表的后面:

/**
 两个线性表的拼接 不考虑A表和B表中是否有重复的元素。直接将B表拼接在A表的后面
 */
void jointTwoLinkLists ()
{
    SQList secondList = initSequentialList(15);
    SQList firstList = initSequentialList(10);
    int firstLength = firstList.length;
    int secondLength = secondList.length;
    //如果firstLength + secondLength > firstList.listSize 表示该线性表的数组的最大容量需要增大。
    if (firstLength + secondLength > firstList.listSize) {
        firstList.listSize = firstLength + secondLength;
    }
    //将secondList表中的元素 一个个插入到firstList表中
    for (int i = 0; i < secondLength; i++) {
        //从secondList表中将元素一个个取出来
        ElemType elem = secondList.data[i];
        //则将elem插入放到firstList表中
        addElemToList(&firstList, elem);
    }
    RYQLog(@"两个线性表的拼接   %d", firstList.length);
}

15>线性表的拆分:

/**
 线性表的拆分
 */
void componentLinkList ()
{
    //假设切割后listA长度为10，listB为5；
    int listA_Length = 10;
    int listB_length = 5;
    
    SQList list = initSequentialList(listA_Length+listB_length);
    SQList listB = initSequentialList(0);
    for (int i = 0; i < listB_length; i++) {
        ElemType elem = list.data[i+listA_Length];
        //将list表的后五个元素分给listB
        addElemToList(&listB, elem);
        //将list表的后五个元素删除
        ListDelete(&list, list.length);
    }
}

16>线性表顺序存储结构总结：

通过以上总结发现顺序存储线性表的优缺点：
优点：取出元素很容易。不用为表示表中元素之间的逻辑关系而增加额外的存储空间。
缺点：删除和插入要移动大量元素。删除的时候容易造成存储空间碎片。线性表的长度变化较大时，难以控制存储空间的容量.线性表的数组长度需要给定。

• 线性表的链式存储结构

在顺序结构中，每个数据元素只需要存储数据元素的信息就可以了。在链式存储过程中，除了要存储数据元素的信息外，还要存储它的后继元素的存储地址。把存储数据元素信息的区域称为数据域，把存储直接后继位置成为指针域。指针域中存储的信息称为指针或者链。指针域和数据域两部分信息组成数据元素的存储映像，称为结点。

一、单链表：n个结点链组成一个链表，即为线性表的链式存储结构。因为此结点中只包含一个指针域，所以叫单链表。

链表中的第一个结点的存储位置称为头指针。最后一个结点的指针为空。
单链表的第一个结点前附设一个结点，称为头结点。

单链表无头结点结构：

单链表无头结点

单链表带头结点结构：

单链表带头结点结构

空链表：

空链表

头结点和头指针的区分：

1.头指针是指向链表中第一个结点的指针。头结点是为了操作的统一方便设立的，放在第一个元素的结点之前。若链表中有头结点，那么链表中的第一个结点就是头结点了，所以头指针此刻指向的是头结点的指针。
2.头指针具有标识作用，所以常用头指针冠以链表的名字。无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
疑问：为什么空链表一定要有头指针，个人认为链表为空表示链表存在，但是没有任何结点。头指针此刻更觉得像是存储着空链表的地址。纯属猜想。
3.链表有了头结点，在对第一元素结点前插入结点和删除第一个结点，其操作与其他结点的操作就统一了。头结点不一定是链表的必需元素。

1>线性表的单链表存储结构：

/**
 线性表的单链表存储结构
 */
typedef struct Node {
    
    ElemType data;//数据域 存放本结点中的数据
    struct Node *next;//指针域 存放下一个结点的地址
    
} Node;

typedef struct Node *LinkList;//定义一个链表

2>单链表的创建（头插法）

创建思路：
1.声明一个结点p。
2.初始化一个空链表list。
3.让list的头结点的指针指向NULL，即创建一个带头结点的单链表。
4.循环：
生成一个新结点赋值给p
随机生成一个数字赋值给p结点的数据域data
将p插入到头结点和新的结点之间（头插法）

/**
 头插法 后产生的元素放在最前面
 单链表的创建:
 创建思路：
 1.声明一个结点p。
 2.初始化一个空链表list。
 3.让list的头结点的指针指向NULL，即创建一个带头结点的单链表。
 4.循环：
    生成一个新结点赋值给p
    随机生成一个数字赋值给p结点的数据域data
    将p插入到头结点和新的结点之间（头插法）
 

 @param list 单链表
 @param length 大小
 */
void createListHead (LinkList *list, int length)
{
    
    LinkList p;
    //time()主要用来获取当前的系统时间
    //srand()函数主要用来配合rand()，函数来使用。假如没有srand()，那么每次生成的随机数都是一样的。根据时间的不同生成的随机数也不一样
    srand(time(0));
    
    *list = (LinkList)malloc(sizeof(Node));
    (*list)->next = NULL;//创建一个带头结点的空链表
    
    for (int i = 0; i < length; i++) {
        
        p = (LinkList)malloc(sizeof(Node));//生成新的结点
        p->data = rand() % 100 + 1;//生成随机数 赋值给p结点的数据域
        p->next = (*list)->next;
        (*list)->next = p;//将p插入到头结点和新的结点之间
        RYQLog(@"第%d个元素  它的值为%d", i+1, p->data);
    }
}

3>单链表的创建（尾插法）

/**
 尾插法 创建单链表  后产生的元素放在最后面

 @param list 单链表
 @param length 大小
 */
void createTailLinkList (LinkList *list, int length)
{
    LinkList p,r;
    int I;
    //time()主要用来获取当前的系统时间
    //srand()函数主要用来配合rand()，函数来使用。假如没有srand()，那么每次生成的随机数都是一样的。根据时间的不同生成的随机数也不一样
    srand(time(0));
    *list = (LinkList)malloc(sizeof(Node));//整个线性表
    r = *list;
    
    for (i = 0; i < length; i++) {
        
        p = (LinkList)malloc(sizeof(Node));//生成新的结点
        p->data = rand() % 100 + 1;//生成随机数 赋值给p结点的数据域
        r->next = p;//将表尾的结点指针指向新的结点
        r = p;//将新的结点赋值给表尾的结点
        RYQLog(@"第%d个元素  它的值为%d", i+1, p->data);
    }
    
    r->next = NULL;//表示当前链表u也结束
}

4>单链表的数据读取:

获取链表第i个数据的思路:通过下标i，比方要查找第4个数据。从第一个开始通过next指针，找到第二个数据。再通过第二个数据的next指针找到第三个数据。最后通过第三个数据的next指针找到第四个数据。
1.声明一个结点p指向链表的y第一个结点，初始化j从1开始。
2.当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1.
3.若到链表末尾p为空，则说明第i个元素不存在；
4.若查找成功，返回结点p的数据
时间复杂度O（n）

/**
 单链表的数据读取
 获取链表第i个数据的思路:通过下标i，比方要查找第4个数据。从第一个开始通过next指针，找到第二个数据。再通过第二个数据的next指针找到第三个数据。最后通过第三个数据的next指针找到第四个数据。
 1.声明一个结点p指向链表的第一个结点，初始化j从1开始。
 2.当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1.
 3.若到链表末尾p为空，则说明第i个元素不存在；
 4.若查找成功，返回结点p的数据
 时间复杂度O（n）

 @param list 结点
 @param I 下标
 @return 结果
 */
Status GetNodeElem (LinkList list, int i)
{
    
    int j = 1;
    LinkList pList = list->next;//声明一个结点p 并让p指向链表
    //p不为空g或者计数器j还没有等于i的时候 循环继续。
    while (pList && j < i) {
        
        //让p指向下一个结点
        pList = pList->next;
        
        ++j;
    }
    //第i个元素不存在 抛异常
    if (!pList || j > i) {
        RYQLog(@"单链表的数据读取  没有找到该元素");
        
        return ERROR;
    }
    
    ElemType elem = pList->data;
    RYQLog(@"单链表的数据读取  elem = %d", elem);

    return SUCCESS;
}

5>单链表的数据插入:

思路：
1.寻找p结点，假如没有找到，返回失败。
2.查找成功生成一个新结点s，结点s数据域的赋值。
3.将p结点的next指针指向赋值给s的next指针
4.将p结点的next指针指向s。
时间复杂度O(1)

单链表插入示意图：

单链表插入

1.生成一个新的结点s：

LinkList s = (LinkList)malloc(sizeof(Node));//生成一个新的结点s
s->data = elem;//结点s数据域的赋值

2.将p结点的next指针指向赋值给s的next指针。
将p结点的next指针指向s。
这两步不可交换，若先执行将p结点的next指针指向s，那么s->next将无法正确赋值。

s->next = p->next;//将p结点的next指针指向赋值给s的next指针
p->next = s;//将p结点的next指针指向s

单链表插入示意图

3.单链表插入完成。

单链表插入示意图

/**
 单链表的数据插入
 思路：
 1.寻找p结点，假如没有找到，返回失败。
 2.查找成功生成一个新结点s，结点s数据域的赋值。
 3.将p结点的next指针指向赋值给s的next指针
 4.将p结点的next指针指向s

 @param list 结点
 @param I 下标
 @return 结果
 */
Status NodeListInsert (LinkList *list, int i)
{
    int j = 1;
    LinkList p = *list;//声明一个结点p 并让p指向链表
    //p不为空g或者计数器j还没有等于i的时候 循环继续。
    while (p && j < i) {
        
        //让p指向下一个结点
        p = p->next;
        
        ++j;
    }
    //第i个元素不存在 抛异常
    if (!p || j > i) {
        return ERROR;
    }
    
    ElemType elem = 99;//要插入的数值
    LinkList s = (LinkList)malloc(sizeof(Node));//生成一个新的结点s
    s->data = elem;//结点s数据域的赋值
    s->next = p->next;//将p结点的next指针指向赋值给s的next指针
    p->next = s;//将p结点的next指针指向s
    
    return SUCCESS;
}

6>单链表的数据删除:

删除下标为i的结点思路：
1.声明一个结点p指向链表的第一个结点，初始化j从1开始。
2.当j < i时，遍历链表，让p的指针向后移，不断指向下一个结点，j累加1。
3.若到链表末尾p为空，则说明第i个元素不存在。
4.否则就是查找成功，将欲删除的结点p->next 赋值给q。
5.单链表的删除标准语句p->next = q->next。
6.将q结点中的数据赋值给elem。
7.释放q结点，表示成功删除。

单链表的数据删除示意图:

单链表的数据删除示意图

/**
 单链表的数据删除
 删除下标为i的结点思路：
 1.声明一个结点p指向链表的第一个结点，初始化j从1开始；
 2.当j < i时，遍历链表，让p的指针向后移，不断指向下一个结点，j累加1.
 3.若到链表末尾p为空，则说明第i-1个元素不存在
 4.否则就是查找成功，将欲删除的结点p->next 赋值给q。
 5.单链表的删除标准语句p->next = q->next，
 6.将q结点中的数据赋值给elem
 7.释放q结点，表示成功删除

 @param list 单链表
 @param i 删除的下标
 @return 结果
 */
Status NodelistDelete (LinkList *list, int i)
{
    int j = 1;
    LinkList p,q;
    p = *list;//结点p指向链表的第一个结点
    //在单链表中遍历寻找第i个元素
    while (j < i && p->next) {
        
        p = p->next;
        ++j;
        
    }
    //查找的元素不存在
    if (j > i || !(p->next)) {
        return ERROR;
    }
    //查找的元素存在  此时p结点为找到的第i-1个元素 q结点为第i个元素
    q = p->next;
    //将q的g后继结点赋值给p的后集结点
    p->next = q->next;
    ElemType elem = q->data;
    RYQLog(@"单链表的数据删除   elem = %d", elem);
    free(q);
    
    return SUCCESS;
}

7>清空单链表:

思路：
从单链表的第一个结点开始依次遍历。依次释放，最后将头结点指针域置为空。

/**
 清空单链表

 @param list 单链表
 @return 删除结果
 */
Status CleanNodeList(LinkList *list)
{
    LinkList p,q;
    p = (*list)->next;//p指向第一个结点
    while (p) {
        
        q = p->next;
        free(p);
        p = q;
        
    }
    (*list)->next = NULL;//头结点指针域置为空
    
    return SUCCESS;
}

8>销毁单链表:

/**
 销毁单链表
 
 @param list 单链表
 @return 结果
 */
Status DestroyLinkList(LinkList *list)
{
    LinkList p,q;
    p = (*list)->next;//p指向第一个结点
    while (p != *list) {
        
        q = p->next;
        free(p);
        p = q;
        
    }
    free(list);
    list = NULL;
    
    return SUCCESS;
}

9>翻转单链表(头插法，要多手动画图理解单链表的就地逆置):

/**
 翻转单链表：头插法

 @param list 单链表
 @return 结果
 */
Status ReversalLinkList(LinkList *list)
{
    LinkList p, q;//定义p和q两个结点分别记录待逆置链表的首位结点和次首位结点
    p = (*list)->next;//p指向首位结点
    (*list)->next = NULL;//断开头结点与链表
    while (p) {
        q = p;
        p = p->next;
        
        q->next = (*list)->next;
        (*list)->next = q;
    }
    
    return SUCCESS;
}

10>单链表的拼接

/**
 合并两个单链表
 */
void mergeTwoLinkList ()
{
    //单链表的创建
    LinkList listA;
    createTailLinkList(&listA, 2);
    LinkList listB;
    createTailLinkList(&listB, 2);
    travelAllStoragelist(&listA);
    travelAllStoragelist(&listB);
    
    LinkList p;
    for(p=listA;p->next!=NULL;p=p->next)
        ;
    p->next=listB->next;
    free (listB);
    travelAllStoragelist(&listA);
}

• 循环链表

循环链表 就是在单链表的基础上修改而来 单链表是将尾结点的指针指向NULL，循环链表是将尾结点的指针指向向链表的第一个结点。

非空循环链表 空循环链表

创建循环链表:

/**
 创建循环链表  后产生的元素放在最后面
 
 @param list 单链表
 @param length 大小
 */
void createTailCycleList (CycleList *list, int length)
{
    CycleList p,r;
    int I;
    //time()主要用来获取当前的系统时间
    //srand()函数主要用来配合rand()，函数来使用。假如没有srand()，那么每次生成的随机数都是一样的。根据时间的不同生成的随机数也不一样
    srand(time(0));
    *list = (CycleList)malloc(sizeof(Node));//整个线性表
    r = *list;
    
    for (i = 0; i < length; i++) {
        
        p = (CycleList)malloc(sizeof(Node));//生成新的结点
        p->data = rand() % 100 + 1;//生成随机数 赋值给p结点的数据域
        r->next = p;//将表尾的结点指针指向新的结点
        r = p;//将新的结点赋值给表尾的结点
        
    }
    
    r->next = *list;
}

• 双向链表。

双向链表是在单链表的基础上添加了前驱指针。

1>双链表的结构示意图：

双链表 空双链表

typedef struct DoubleNode
{
    ElemType data;
    struct DoubleNode *prior;//直接前驱指针
    struct DoubleNode *next;//直接后继指针
    
}DoubleNode, *DoubleLinkList;

2>双向链表的创建：

/**
 头插法 后产生的元素放在最前面
 
 @param list 双向链表
 @param length 大小
 */
void createDouleListHead (DoubleLinkList *list, int length)
{
    
    DoubleLinkList p;
    //time()主要用来获取当前的系统时间
    //srand()函数主要用来配合rand()，函数来使用。假如没有srand()，那么每次生成的随机数都是一样的。根据时间的不同生成的随机数也不一样
    srand(time(0));
    
    *list = (DoubleLinkList)malloc(sizeof(DoubleNode));
    (*list)->next = *list;
    (*list)->prior = *list;
    
    for (int i = 0; i < length; i++) {
        
        p = (DoubleLinkList)malloc(sizeof(DoubleNode));//生成新的结点
        p->data = rand() % 100 + 1;//生成随机数 赋值给p结点的数据域
        p->next = (*list)->next;
        p->prior = (*list);
        (*list)->next->prior = p;
        (*list)->next = p;//将p插入到头结点和新的结点之间
    }
}

3>双向链表的数据插入：

1.如箭头1，将s的前置指针指向p结点：s->prior = p;//把p结点赋值给s的前置指针。
2.箭头2，将s的后置指针指向p->next：s->next = p->next;//将p结点的next指针指向赋值给s的next指针。
3.箭头3，s结点插入到p和p->next之间，p->next的前置指针需要指向s：p->next->prior = s;//s结点赋值给p结点的next的前置指针。
4.箭头4，将p结点的next指针指向s：p->next = s;

双向链表的数据插入

/**
 双向链表的数据插入
 
 @param list 结点
 @param I 下标
 @return 结果
 */
Status DouleNodeListInsert (DoubleLinkList *list, int i)
{
    int j = 1;
    DoubleLinkList p = *list;//声明一个结点p 并让p指向链表
    //p不为空g或者计数器j还没有等于i的时候 循环继续。
    while (p && j < i) {
        
        //让p指向下一个结点
        p = p->next;
        
        ++j;
    }
    //第i个元素不存在 抛异常
    if (!p || j > i) {
        return ERROR;
    }
    
    ElemType elem = 99;//要插入的数值
    DoubleLinkList s = (DoubleLinkList)malloc(sizeof(DoubleNode));//生成一个新的结点s
    s->data = elem;//结点s数据域的赋值
    s->prior = p;//把p结点赋值给s的前置指针
    s->next = p->next;//将p结点的next指针指向赋值给s的next指针
    p->next->prior = s;//s结点赋值给p结点的next的前置指针
    p->next = s;//将p结点的next指针指向s
    
    return SUCCESS;
}

4>双向链表的数据删除：

1.箭头1，将q->prior的后置指针指向q->next：q->prior->next = q->next;
2.箭头2，将q的前置结点赋值给q的后置结点的前指针：q->next->prior = q->prior;

双向链表的数据删除

/**
 双向链表的数据删除
 
 @param list 双向链表
 @param i 删除的下标
 @return 结果
 */
Status DouleNodelistDelete (DoubleLinkList *list, int i)
{
    int j = 1;
    DoubleLinkList p,q;
    p = *list;//结点p指向链表的第一个结点
    //在双向链表中遍历寻找第i个元素
    while (j < i && p->next) {
        
        p = p->next;
        ++j;
        
    }
    //查找的元素不存在
    if (j > i || !(p->next)) {
        return ERROR;
    }
    //查找的元素存在  此时p结点为找到的第i-1个元素 q结点为第i个元素
    q = p->next;
    q->prior->next = q->next;//将q的后继结点赋值给q的前置结点的后指针
    q->next->prior = q->prior;//将q的前置结点赋值给q的后置结点的前指针
    ElemType elem = q->data;
    RYQLog(@"双向链表的数据删除   elem = %d", elem);
    free(q);
    
    return SUCCESS;
}

5>清空双向链表：

/**
 清空双向链表
 
 @param list 双向链表
 @return 删除结果
 */
Status CleanDouleNodeList(DoubleLinkList *list)
{
    DoubleLinkList p,q;
    p = (*list)->next;//p指向第一个结点
    while (p != *list) {
        
        q = p->next;
        free(p);
        p = q;
        
    }
    (*list)->next = (*list)->prior = NULL;//头结点指针域置为空
    
    return SUCCESS;
}

6>销毁双向链表：

/**
 销毁双向链表

 @param list 双向链表
 @return 结果
 */
Status DestroyDouleNodeList(DoubleLinkList *list)
{
    DoubleLinkList p,q;
    p = (*list)->next;//p指向第一个结点
    while (p != *list) {
        
        q = p->next;
        free(p);
        p = q;
        
    }
    free(list);
    list = NULL;
    
    return SUCCESS;
}

对比单链表和双向表：单链表内存开销更小，因为没有前置指针。但是双向表有前置指针，逆向遍历更方便。使用链式存储结构的时候单链表优先，双链表其次。

最后用类比的方法总结一下线性表的顺序存储和链式存储吧：

（线性表的顺序存储）
谁说恋爱像线性表
热恋的时候，总要将亲密有序紧挨着排放（顺序存储空间连续）
虽然删除每一个好感，都要移动以后得甜蜜(顺序存储删除或增加都要移动该元素之后的所有元素)
但是那样子的甜蜜，总是容易看的见(容易读取)
（链式存储）
进入平和期，恋爱像链式存储
无时无刻为生活奔波，不管距离多远都会有彼此(存储空间不连续，通过next指针链接)
像指针紧紧的连接着

有伤痛，就算断开了一份亲密
也不影响以后的生活
至多再找下一个幸福的结点愈合

就算出轨的时候
也能在原地，做出选择
那样子的伤口很容易愈合
(删除和插入元素都不用移动结点的位置，只需要改变指针指向即可)

数据结构之线性表Demo

• 线性表在iOS中的应用

NSArray，NSMutableArray。（线性顺序表）

NSAutoreleasePool（自动释放池）：双链表。 AutoreleasePool的解析