19数据结构-链表

链表是指逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置。

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。

如图所示，当每一个数据元素都和它下一个数据元素用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。

每个元素本身由两部分组成:

存储数据的区域，称为“数据域"；

指向直接后继的指针，称为“指针域”。

 

这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。

由于每个结点中只包含一个指针域，生成的链表又被称为单链表。

链表中存放的不是基本数据类型，需要用结构体实现自定义：

typedef int Data;
typedef struct linkList
{
    Data data;			//数据域
    struct linkList*next;	//指针域，指向下一个节点
}linkList;

头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

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

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

单链表中可以没有头结点，但是不能没有头指针！

万事开头难，初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时，要保证有一个指针永远指向的是链表的表头，这样做不至于丢失链表。

createlinkList()创建一个空链表并返回链表的头指针：

linkList* createlink
List()
{
    linkList*head = calloc(1,sizeof(linkList));     //创建一个头结点
    if(!head)
        return NULL;
    return head;
}

链表中插入结点，根据插入位置的不同，分为3种：

插入到链表的首部，也就是头结点和首元结点中间；

插入到链表中间的某个位置；

插入到链表最末端；

 

虽然插入位置有区别，但都使用相同的插入手法。分为两步，如上图所示：

将新结点的next指针指向插入位置后的结点；

将插入位置前的结点的next指针指向插入结点；

头插：

void push_front(linkList* list,Data val)
{
    linkList* newNode = calloc(1,sizeof(linkList));
    if(!newNode)
        return NULL;
    newNode->data = val;
    newNode->next = list->next;
    list->next = newNode;
}

尾插：

void push_back(linkList* list,Data val)
{
    //找到最后一个节点
    linkList* lastNode = list;
    while(lastNode->next)
    {
        lastNode = lastNode->next;
    }
    
    linkList*newNode = calloc(1,sizeof(linkList));
    if(!newNode)
        return;
    newNode->data = val;
    lastNode->next = newNode;
}

指定插:

void insert(linkList*list,Data val,size_t pos)
{
    linkList* prevNode = list;  //辅助节点，用来保存待插入位置的上一个节点
    //先判断有没有pos位置
    for(int i = 0;i < pos; i++)
    {
        if(prevNode == NULL)
        {
            printf("插入位置无效n");
            return;
        }
        prevNode = prevNode->next;
    }
    //如果找到了位置，创建节点插入
    linkList* newNode = calloc(1,sizeof(linkList));
    if(!newNode)
        return;
    newNode->data = val;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

一般情况下，链表只能通过头结点或者头指针进行访问，如果要访问所有节点就需要对链表中的结点进行逐个遍历。

void printList(linkList*list)
{
    linkLis*curNode = list->next;   //指向首元结点
    while(curNode)
    {
        printf("%d ",curNode->data);
        curNode = curNode->next;
    }
}

当需要从链表中删除某个结点时，需要进行两步操作：

将结点从链表中摘下来;

手动释放掉结点，回收被结点占用的内存空间;

使用malloc函数申请的空间，一定要注意手动free掉。否则在程序运行的整个过程中，申请的内存空间不会自己释放（只有当整个程序运行完了以后，这块内存才会被回收），造成内存泄漏，别把它当成是小问题。

void removeOne(linkList*list,Data val)
{
    linkList* curNode = list;
    //找到要删除的节点的前一个节点
    while(curNode->next)
    {
        if(curNode->next->data == val)
        {
            break;
        }
        curNode = curNode->next;
    }
    //如果找到了要删除的节点删除节点
    if(curNode->next != NULL)
    {
        linkList* delNode = curNode->next;
        curNode->next = delNode->next;
        free(delNode);
    }
}

当链表使用完毕，需要对链表进行销毁，即释放每个节点的内存。

void freelinkList(linkList*list)
{
    linkList* curNode = list;
    linkList* delNode = NULL;
    while(curNode)
    {
        delNode = curNode;          //保存要删除的节点
        curNode = curNode->next;    //curNode向后移动
        free(delNode);//释放
    }
    list = NULL;    //这句能否修改实参？
}