单链表的基本操作

首先指出我在学习过程中纠结的几个点：

1.初始化单链表的时候为什么要用二级指针？

反正那会也没学长指导，状态还差了点，但搜了很久后还是想明白了。

说白了你可以选择在定义头节点L的时候就初始化，也可以定义了后用二级指针或者一级指针的引用传进函数InitList来初始化

2.为什么会需要头结点？

若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

>>ADT：

typedef struct Node
{
    DataType data;
    struct Node *next;
}Node, *LinkList;

>>初始化:

void InitList(LinkList *L)
{
    *L = (Node*)malloc(sizeof(Node));
    (*L)->next = NULL;
}

>>判断链表是否为空：

int Empty(Node *L)
{
    if (L->next==NULL) return 1;
    else return 0;
}

>>建立链表：
(1)头插法（逆序存储）

Node *CreatList1(DataType a[], int n)
{
    Node *s = NULL;
    Node *L = (Node*)malloc(sizeof(Node));
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        s = (Node*)malloc(sizeof(Node));
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
    return L;
}

(2)尾插法

Node *CreatList2(DataType a[], int n)
{
    Node *s = NULL, *rear = NULL;
    Node *L = (Node*)malloc(sizeof(Node));
    rear = L;
    for (int i = 0; i < n; i++) {
        s = (Node*)malloc(sizeof(Node));
        s->data = a[i];
        rear->next = s;
        rear = s;
    }
    rear->next = NULL;
    return L;
}

>>遍历链表：

void PrintList(Node *L)
{
    Node *p = L->next;
    while (p!=NULL) {
        printf("%d", p->data);
        p = p->next;
    }
}

>>链表长度：

int Length(Node *L)
{
    Node *p = L->next;
    int cnt = 0;
    while (p!=NULL) {
        cnt++;
        p = p->next;
    }
    return cnt;
}

>>查找节点

(1)按值查找

Node *Get(Node *L, DataType x)
{
    Node *p = L->next;
    while (p&&p->data!=x) p = p->next;
    return p;
}

(2)按位查找

Node *Locate(Node *L, int n)
{
    if (n<=0) return NULL;
    Node *p = L;
    for (int i = 0; i < n; i++)
        p = p->next;
    return p;
}

>>插入节点

int Insert(Node *L, int n, DataType x)
{
    if (n<=0) return 0;
    Node *s = NULL, *p = L;
    int cnt = 0;
    while (p!=NULL&&cnt<n-1) {
        cnt++;
        p = p->next;
    }
    if (p==NULL) return 0;
    else {
        s = (Node*)malloc(sizeof(Node));
        s->data = x;
        s->next = p->next;
        p->next = s;
        return 1;
    }
}

>>删除节点

int Delete(Node *L, int n)
{
    if (n<=0) return 0;
    Node *p = L;
    int cnt = 0;
    while (p!=NULL&&cnt<n-1) {
        cnt++;
        p = p->next;
    }
    if (p==NULL||p->next==NULL) return 0;
    else {
        Node *q = p->next;//单独设置一个指针指向被删除结点进行存储，以防丢失
        p->next = q->next;
        free(q);//手动释放该结点，防止内存泄漏
        return 1;
    }
}

这些只是相对来说还不错的实现方法，当然也有别的写法，可以多看下别人的博客

总结：

线性表的链式存储相比于顺序存储，有两大优势：

1.链式存储的数据元素在物理结构没有限制，当内存空间中没有足够大的连续的内存空间供顺序表使用时，可能使用链表能解决问题。（链表每次申请的都是单个数据元素的存储空间，可以利用上一些内存碎片）

2.链表中结点之间采用指针进行链接，当对链表中的数据元素实行插入或者删除操作时，只需要改变指针的指向，无需像顺序表那样移动插入或删除位置的后续元素，简单快捷。

链表和顺序表相比，不足之处在于，当做遍历操作时，由于链表中结点的物理位置不相邻，使得计算机查找起来相比较顺序表，速度要慢。

感谢以下博客

https://www.cnblogs.com/ciyeer/p/9025871.html

https://blog.csdn.net/u012234115/article/details/39717215

https://www.cnblogs.com/longl/p/6414433.html