#define OK 1
#define ERROR 0
typedef int Status;

typedef struct
{
    ElemType data;
    struct Node *next;
} Node;

typedef struct Node *LinkList; // 定义单链表

// 获取单链表的长度
Status GetElem(LinkList L, int i, ElemType *e)
{
    in j;              // 用于记录当前位置
    LinkList p;        // 用于指向当前位置
    p = L->next;       // p指向第一个结点
    j = 1;             // j初始化为1
    while (p && j < i) // 当p不为空且j小于i时
    {
        p = p->next; // p后移一个结点
        j++;         // j加1
    }
    if (!p || j > i)  // 当p为空或者j大于i时
        return ERROR; // 返回错误
    *e = p->data;     // 将p的值赋给e
    return OK;        // 返回OK
}

// 在单链表中插入元素
Status ListInsert(LinkList *L, int i, ELemType e)
{
    int j;             // 用于记录当前位置
    LinkList p, s;     // p指向当前结点，s指向新结点
    p = *L;            // p指向第一个结点
    j = 1;             // j初始化为1
    while (p && j < i) // 当p不为空且j小于i时
    {
        p = p->next; // p后移一个结点
        j++;         // j加1
    }
    if (!p || j > i)                    // 当p为空或者j大于i时
        return ERROR;                   // 返回错误
    s = (LinkList)malloc(sizeof(Node)); // 分配空间
    s->data = e;                        // 将e赋给新结点
    s->next = p->next;                  // 将新结点插入到p的后面
    p->next = s;                        // 将p的后继指向新结点
    return OK;                          // 返回OK
}

// 删除单链表中的第i个元素
Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;                   // 用于记录当前位置
    LinkList p, q;           // p指向当前结点，s指向待删除结点
    p = *L;                  // p指向第一个结点
    j = 1;                   // j初始化为1
    while (p->next && j < i) //遍历寻找第i个元素
    {
        p = p->next; // p后移一个结点
        j++;         // j加1
    }
    if (!(p->next) || j > i) // 当p为空或者j大于i时
        return ERROR;        // 返回错误
    q = p->next;             // q指向待删除结点
    p->next = q->next;       // 将q的后继指向p的后继
    *e = q->data;            // 将q的值赋给e
    free(q);                 // 释放q,free函数的作用是释放内存
    return OK;               // 返回OK
}

/*
    插入和删除算法都是由2部分组成，第一部分就是查找第i个元素，第二部分就是插入或删除元素。
    对于插入或删除数据越频繁的操作，单链表比起顺序存储来说，单链表的优势是很明显的。

*/

单链表与结构与顺序结构的优缺点：

  ①存储分配的方式不同，顺序存储结构用一段连续存储单元一次存储线性表的数据元素，单链表则采用链式存储结构，用一组任意的存储单元存放线性表的元素。

  ②时间性能：查找：顺序存储结构：O（1），单链表O（n），

                      插入和删除：顺序存储结构需要平均移动表长一半的元素，时间复杂度为O（n）；单链表在找出位置的指针后，插入和删除时间复杂度仅为O（1）

  ③空间性能：顺序存储结构需要预分配存储空间，分大了就浪费，分小了，就容易发生溢出；单链表不需要分配空间，只要有就分配，元素个数也不收限制。