数据结构之链表篇

前言

  此篇记录一下本人对链表的理解,重点讲解链表的插入与删除算法,相信大家在学习数据结构的时候,第一篇就是链表。简直是给了我一个下马威。我对应它放弃了多次,早在1年前我就接触了链表,emmm,放弃。始终不甘心,然后等到高考暑假后再次鼓起勇气认识它,好吧,又被它打跑了。终于在前几天重新再来学习链表,功夫不负有心人,彻彻底底的搞懂了链表。

基本概念

  链表由n个结点链组成,第一个结点的存储位置叫做头指针,最后一个结点的指针为“空”(NULL)
  结点:包括数据域和指针域
  头指针:指向链表中第一个结点的地址
  头结点:在单链表的第一个结点前附设的一个结点
  头指针是链表的必要元素,头结点是为了操作的统一和方便而设定的,其数据域一般无意义(可用来保存链表的长度),头结点可有可无。   

单链表

结构图

  
  再次强调,请理解头结点和头指针,头指针不是链表的第一个结点,而是指向链表的第一个结点的地址!!

  首先定义链表的结点

// 定义链表的结点
typedef struct node{
    int id;				//数据域,这里为了方便示例全部采用id值
    struct node * next;	//指针域,指向下一个结点的地址
}Node;

  然后定义链表的头结点与头指针

// 头结点
// 在定义链表时,习惯性的会定义头结点,以便统一链表结点的插入和删除操作
typedef struct LinkList{
    Node * next;    //头指针(如果链表有头结点,next就指向头结点,没有就指向第一个结点)
    int length;
}LinkList;

  上面这段代码,你可能会好奇怎么使用,或者说为什么要这样定义,而不是只要有链表的结点不就完了吗,还要这段代码干嘛,别急后面会用到。

单链表插入

  插入分为两种情况,第一种插入到第一个位置,第二种插入到其他位置。
  第一种情况:插入第一个位置
 
  从图片不难看出,首先将要插入的a结点的next指向头指针,即第一个结点(a1)的地址,然后将链表的头指针指向新插入的a结点的地址,就完成了

  第二种情况:插入到其他位置
  这里假设插入到3位置
  
  让a结点的next指向a2的next,然后a2的next指向a,就完成了插入。所以,首先要找到要插入的位置的上一个结点

// 在指定的位置pos插入元素id
void InsertLinkList(LinkList *linkList, int pos, int id)
{
    // 1.创建空结点并为数据域赋值
    Node *node = (Node *)malloc(sizeof(Node)); //创建结点
    node->id = id;
    node->next = NULL;

    // 2.找到要插入位置的结点
    // 如果插入的是第一个元素
    if (pos == 1)
    {
        node->next = linkList->next;
        linkList->next = node; //重新设置头指针
    }
    else
    {
        // 通过循环找到要插入的结点位置
        Node *prev = linkList->next; // 获取到插入pos前一个结点的地址
        for (int i = 1; i < pos - 1 && prev != NULL; i++)
        {
            prev = prev->next;
        }

        // 3.将结点插入并对接前面的结点
        if (prev != NULL)
        {
            //必须先让插入的结点的next获取到前一个结点的next指向的地址空间,
            //低下这两行代码不能调换顺序
            node->next = prev->next;
            prev->next = node;
        }
        // 并不需要单独考虑结点在最后添加的情况
        // 如果在尾部添加结点。因为在前面,就设置了node->next = NULL
        // 所以链表的尾结点插入好后下一个空间的地址就是空
    }

    linkList->length++;
}

单链表初始化

  定义初始化函数,此初始化只出现本篇一次,后面的双链表和循环链表将不会出现初始化示例

// 初始化链表
void InitLinkList(LinkList * linkList,int length)
{
    linkList.length = 0;   //初始化链表长度
    //注意头指针的定义是,即使链表为空,头指针也不为空,这里是本人的代码习惯,所以将头指针设置为空
    linkList.next = NULL;  //初始头指针为空
    for (int i = 0; i < length; i++)
    {
        InsertLinkList(linkList,i + 1,i + 1);
    }
}

单链表删除

  这里也要分两种情况,第一种情况:删除的位置在第一个,第二种情况:在其他位置删除
  第一种情况:删除的位置在第一个示例
  
  整个的逻辑其实是,直接让头指针指向a2即可,然后释放掉a1的内存空间即可
  
  第二种情况:在其他位置删除
  假设删除的位置是2,那么需要找到上一个结点,从图片可知让a1的next指向a2的next,然后释放掉a2的空间即可
  

// 在指定位置删除结点
void DeleteLinkList(LinkList *linkList, int pos)
{
    // 1.指向链表的第一个结点
    Node *node = linkList->next;

    // 2.删除的结点为第一个
    if (pos == 1)
    {
        linkList->next = node->next; //重新设置头指针
        free(node);					 //记得要使用free(),这一步容易忽略
        linkList->length--;
        return;
    }

    // 3.获取要删除的结点的前一个结点地址
    for (int i = 1; i < pos - 1; i++)
    {
        node = node->next;
    }
    Node *delNode = node->next; //要删除的结点的地址
    node->next = delNode->next; //重新指向地址
    free(delNode);
    linkList->length--;
}

清空链表

  通过循环链表的方式,去清空链表,代码胜千言
  

// 清空链表
void ClearLinkList(LinkList *linkList)
{
    Node *node = linkList->next;	//指向链表的第一个结点
    Node *nextNode;
    while (node != NULL)
    {
        nextNode = node->next; //先记录当前结点的下一个结点以便释放当前结点的内容
        free(node);
        node = nextNode;		//重新获取结点
    }
    linkList->next = NULL;
    linkList->length = 0;
}

打印链表

void PrintLinkList(LinkList *linkList)
{
    Node *node = linkList->next; //获取到链表的第一个结点
    if (node == NULL)
    {
        printf("链表为空\n");
        return;
    }

    while (node != NULL)
    {
        printf("%d ", node->id);
        node = node->next;
    }
    printf("\n");
}

 main函数展示,本篇也只出现这一次,其他类型的链表main内容都大同小异

int main()
{
    LinkList linkList;

    InitLinkList(&linkList, 4);
    PrintLinkList(&linkList);
    InsertLinkList(&linkList,1,2);
    DeleteLinkList(&linkList,1);
    ClearLinkList(&linkList);
    PrintLinkList(&linkList);
}

  理解了单链表后,那么后面的循环链表和双向链表都大同小异。而从上面的代码中可看出头指针是非常重要的,用起来非常方便。

循环链表

结构图

  
  循环链表最大的特点是尾结点的指针域指向第一个结点
  定义循环链表的结点

// 循环链表的结点
typedef struct CircularNode
{
    int id;                    //数据域
    struct CircularNode *next; //指向下个结点的指针域
} CircularNode;

  定义循环链表的头结点

// 头结点
typedef struct CircularLinkList
{
    CircularNode *next; //指向第一个结点的指针,头指针
    int length;
} CircularLinkList;

循环链表的插入

  循环链表的插入稍微复杂了一点点,有4种情况
  第一种:插入位置在第一个,链表长度不为0
  第二种:插入位置在第一个,链表长度为0
  第三种:插入位置在尾部
  第四种:插入位置在非上述情况

  虽然看起来要四种情况,但其实总的来说只有两大种,其他两小种只需要在里面,加一个if判断就能搞定
  第一种:插入位置在第一个,链表长度不为0
  
  先让a结点的next指向第一个结点的地址,然后让尾结点的next指向a结点的地址,最后头指针指向a结点的地址即可
  第二种:插入位置在第一个,链表长度为0
  
  直接让头指针指向即可
  第三种:插入位置在尾部
  
  第四种:插入位置在非上述情况
  
  可以看到在非第一个位置插入的情况下,都需要找到前缀结点,先让a结点的next指向前缀结点的next,在让前缀结点的next指向a。如果插入的位置在最后需要更新尾结点指针域

// 在循环链表指定位置插入元素
void InsertCircularLinkList(CircularLinkList *linkList, int pos, int id)
{
    // 创建一个空节点
    CircularNode *node = (CircularNode *)malloc(sizeof(CircularNode));
    node->id = id;
    node->next = NULL;

    // 插入的位置是第一个
    if (pos == 1)
    {
        node->next = linkList->next;

        // 如果长度不为0,就要找到链表的最后一个结点
        if (linkList->length != 0)
        {
            CircularNode *lastNode = linkList->next;
            for (int i = 1; i < linkList->length; i++)
            {
                lastNode = lastNode->next;
            }
            // 重新设置尾结点
            lastNode->next = node;
        }
        linkList->next = node; //重新设置头结点
        linkList->length++;
        return;
    }

    CircularNode *currNode = linkList->next;	//找到要插入的上一个结点地址
    for (int i = 1; i < pos - 1 && currNode != NULL; i++)
    {
        currNode = currNode->next;
    }

    node->next = currNode->next;
    currNode->next = node;
    // 插入的结点在尾部
    if (pos == linkList->length)
    {
        node->next = linkList->next; //设置尾结点指针域
    }
    linkList->length++; 
}

循环链表的删除

  删除分为两种情况
  第一种:在第一个位置删除
  
  先让尾结点的next指向a2,此gif下的一步应该是让头指针指向a2,为了方便演示故此顺序不一样,最后free(a1)即可

  第二种:在其他位置删除
  
  其实循环链表的删除和单链表的删除基本是一模一样的,无非就是多了一个更新尾结点的操作

// 删除循环链表中指定位置的元素
void DeleteCircularLinkList(CircularLinkList *linkList, int pos)
{
    CircularNode *node = linkList->next;
    if (pos == 1)
    {
        CircularNode *lastNode = linkList->next; //找到最后一个结点
        for (int i = 1; i < linkList->length; i++)
        {
            lastNode = lastNode->next;
        }
        lastNode->next = node->next; // 重新设置尾指针
        linkList->next = node->next; // 重新设置头指针
    }
    else
    {
        // 找到要删除的结点的前一个结点
        CircularNode * preNode = linkList->next;
        for (int i = 1; i < pos - 1; i++)
        {
            preNode = preNode->next;
        }
        node = preNode->next;    //要删除的结点地址
        preNode->next = node->next;
    }
    
    free(node);
    linkList->length--;
}

循环链表的特殊遍历法

  通过给定的某个位置,循环遍历出链表中的每个元素
  只需要先拷贝当前要位置的结点的地址,用do while循环遍历,当下一个地址不等于拷贝的地址就循环打印即可

// 通过给定的某个位置,循环遍历出链表中的每个元素
void PrintCircularLinkListByNode(CircularLinkList * linkList,int pos)
{
    CircularNode * node = linkList->next; 
    
    if(node == NULL || pos <= 0 || pos > linkList->length)
    {
        return NULL;
    }
    
    //获取到pos位置的结点的地址
    for (int i = 1; i < pos; i++)
    {
        node = node->next;
    }
    
    CircularNode * BackupNode = node;     //拷贝该结点的地址
    do
    {
        printf("%d ",node->id);
        node = node->next;
    }while(node != BackupNode);

}

双向链表

  双向链表只是在单链表的基础上,多了一个前缀结点,就多了一份存储空间,相当于用空间换时间

结构图

  老规矩,先创建结点和头结点
/** 双向链表的结点,包含一个数据域和两个指针域 */
typedef struct Node{
    int id;
    struct Node * next;     //指向前缀结点
    struct Node * prev;     //指向后继结点
}Node;
/** 双向链表 */
typedef struct LinkList{
    int length;
    Node * next;
}LinkList;

双向链表的插入

  第一种情况:插入的位置在第一个,链表为空
  
  第二种情况:插入的位置在第一个,链表不为空
  
  第三种情况:插入的位置在中间
  
  第四种情况:插入的位置在最后
  

// 向双向链表指向位置插入元素
void InsertDoublyLinkList(LinkList * linkList,int pos,int id)
{
    // 创建空结点
    Node * node = (Node *)malloc(sizeof(Node));
    node->id = id;
    node->next = NULL;
    node->prev = NULL;

    if(pos == 1)
    {
    	//链表不为空
        if(linkList->length != 0)
        {
           node->next = linkList->next;
           linkList->next->prev = node;
        }
        linkList->next = node;  //更新头指针
    }
    else
    {
        Node * preNode = linkList->next;    //获取到要插入位置的前缀结点
        for (int i = 1; i < pos - 1; i++)
        {
            preNode = preNode->next;
        }
        // 在中间插入
        if (preNode->next != NULL)
        {
            node->next = preNode->next;
            preNode->next->prev = node; 
        }
        node->prev = preNode;   
        preNode->next = node;
    }
    
    linkList->length++;
}

双向链表的删除

  第一种情况:删除的位置在第一个,链表长度为1
  

  请勿将代码直接写成 头指针=null (linkList->next = null)的形式,而是换一种等价写为法:linkList->next = node->next,这种写法将直接减少代码行数
  第二种情况:删除的位置在第一个,链表长度不为1
  
  第三种情况:删除的位置在中间
  
  第四种情况:删除的位置在最后
  
  这里找删除结点跟前两个不一样,因为有了前缀结点,所以找结点的时候直接找到要删除的结点即可,而不是要删除的结点的前缀结点

// 在指定位置删除元素
void DeleteLinkList(LinkList * linkList,int pos)
{
    Node * node = linkList->next;   //获取到链表的第一个结点
    if (pos == 1)
    {
        // 链表长度不为1
        if (node->next != NULL)
        {
            node->next->prev = NULL;
        }
        linkList->next = node->next;    //更新头指针
    }
    else
    {
        // 循环找到要删除的结点的位置
        for (int i = 1; i < pos; i++)
        {
            node = node->next;
        }
        node->prev->next = node->next;
        // 不是在最后一个位置删除
        if(node->next != NULL)
        {
            node->next->prev = node->prev;
        }
    }
    free(node);
    linkList->length--;
    
}

后记

  至此,链表的核心操作就介绍完了,感谢大家的阅读!为了更好的理解链表的详细操作步骤,本人花费大量的时间做出这些gif图片。如果你要使用这些图片,请包含出处等信息,在此谢谢各位大佬!

查看评论 -
评论