【数据结构与算法】深入浅出：单链表的实现和应用

🌱博客主页：青竹雾色间.

😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注

 ✨人生如寄，多忧何为 ✨

目录

前言

单链表的基本概念

节点

头节点

尾节点

单链表的基本操作

创建单链表

头插法：

尾插法：

插入（增）操作

 删除（删）操作：

查找（查）操作：

修改（改）操作：

遍历链表

单链表的应用场景

前言

在本篇博客中，我们将深入探索一种常见的数据结构——单链表。单链表是一种线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是插入和删除操作非常简单，但是查找和遍历操作可能会比较耗时。我们将学习单链表的基本概念、操作以及实现方式。

单链表的基本概念

下面我们来介绍一下单链表的基本概念和操作。

• 节点

  单链表中的每个节点都包含两个部分：数据域(DATA)和指针域(NEXT)。

  数据域用于存储数据元素可以是数组，可以是int，甚至可以是结构体，

  指针域用于存储指向下一个节点的指针。

  

  typedef int ElemType; //定义单链表结构
  typedef struct Node{
      ElemType data;//数据域
      struct Node *next;//指针域
  } LinkList;//初始化

  • 头节点

    单链表的第一个节点称为头节点，它不包含任何数据元素，只包含一个指向第一个节点的指针。在单链表中，头节点通常被定义为全局变量或者静态变量。

    

    //创建头结点，并将数据存入头结点中
    LinkList CreateList(ElemType n){
        LinkList head = (LinkList)malloc(sizeof(struct Node));
        head->data = n;
        head->next = NULL;
        return head;
    }

    • 尾节点

      单链表的最后一个节点称为尾节点，它也不包含任何数据元素，只包含一个指向最后一个节点的指针。在单链表中，尾节点通常被定义为全局变量或者静态变量。

      链表的尾节点NEXT指向NULL（空），因为尾部没有任何可以指向的空间了.

      

      单链表的基本操作

      单链表是一种常见的数据结构，支持以下四种基本操作：插入（增）、删除（删）、查找（查）、修改（改）。下面将逐一介绍这些操作的实现方法。

      创建单链表

      头插法：

      我们首先创建一个头结点，然后将新节点插入到头结点的后面。具体实现时，我们可以使用指针来遍历链表，找到最后一个节点，然后将新节点插入到该节点的后面。这样就可以保证新节点始终位于链表的头部。

      

      // 头插法
      Node* insertAtHead(Node *head, int data) {
          Node *newNode = (Node*)malloc(sizeof(struct Node));
          newNode->data = data;
          newNode->next = head;
          return newNode;
      }

      尾插法：

      

      我们首先创建一个头结点，然后将新节点插入到头结点的后面。具体实现时，我们可以使用指针来遍历链表，找到最后一个节点，然后将新节点插入到该节点的后面。这样就可以保证新节点始终位于链表的尾部。

      // 尾插法
      Node* insertAtTail(Node *head, int data) {
          Node *newNode = (Node*)malloc(sizeof(struct Node));
          newNode->data = data;
          if (head == NULL) { // 如果链表为空，则直接将新节点作为头结点。
              newNode->next = NULL;
              return newNode;
          } else if (head->next == NULL) { // 如果链表只有一个元素，则直接将新节点插入到该元素后面。
              head->next = newNode;
              return head;
          } else { // 否则，找到最后一个节点，然后将新节点插入到该节点的后面。
              Node *temp = head;
              while (temp->next != NULL) temp = temp->next;
              temp->next = newNode;
              return head;
          }
      }

      • 插入（增）操作

                  在单链表中插入一个新节点，将其链接到链表中的其他节点。

        // 在指定位置插入一个新节点
        void insertAtPos(Node** head, int pos, ElemType e) {
            Node* p = *head;
            int i = 1; // i表示当前节点的位置，从第二个节点开始计算
            while (i next, i++; // 从第二个节点开始遍历到指定位置的前一个节点
            Node* newNode = (Node*)malloc(sizeof(struct Node));
            if (newNode == NULL) exit(0); // 如果分配失败则退出程序
            newNode->data = e; // 将新节点的数据域设置为e
            if (p == NULL) *head = newNode; // 如果指定位置的前一个节点是空的，则将新节点作为新的头结点
            else newNode->next = p->next; // 否则将新节点插入到指定位置的前一个节点后面
            p->next = newNode; // 将新节点插入到链表中
        }

        

        •  删除（删）操作：

                   从单链表中删除一个节点，重新连接链表中的其他节点。

          1. 若要删除的节点为头节点，直接将头节点指向下一个节点即可。
          2. 若要删除的节点不是头节点，遍历链表找到该节点的前一个节点。
          3. 将前一个节点的next指针指向要删除节点的下一个节点。

           

          • 查找（查）操作：

                    在单链表中查找特定的元素。

            1. 从头节点开始遍历链表，逐个比较节点的数据与目标数据是否相等。
            2. 若找到相等的节点，则返回该节点或其他需要的信息。
            3. 若遍历完整个链表仍未找到目标数据，则表示目标数据不存在于链表中。

            //在单链表中查找值为x的结点
            int Locate(LinkList L, int x)
            {
                LinkList p;
                int j = 1;
                p = L->next;
                while (p != NULL && p->data != x)
                {
                    p = p->next;
                    j++;
                }
                if (p)
                {
                    printf("%d在链表中，是第%d个元素", p->data - 48, j);//由于是ASCII，所以-48
                }
                else
                {
                    printf("该数值不在链表里。\n");
                    return 0;
                }
            }

            //求单链表的长度
            int ListLength(LinkList L)
            {
                Node* p;
                p = L->next;
                int j = 0;//计数器j
                while (p != NULL)
                {
                    p = p->next;
                    j++;
                }
                printf("%d", j);
                return 0;
            }

            • 修改（改）操作：

                      更新单链表中节点的数据。

              1. 从头节点开始遍历链表，逐个比较节点的数据与目标数据是否相等。
              2. 若找到相等的节点，则将该节点的数据更新为新的数据。

              //链表内容的修改，在链表中修改值为x的元素变为为k。
              LinkedList LinkedListReplace(LinkedList L,int x,int k) {
                  Node *p=L->next;
                  int i=0;
                  while(p){
                      if(p->data==x){
                          p->data=k;
                      }
                      p=p->next;
                  }
                  return L;
              }

              • 遍历链表

                在单链表中，遍历链表的操作可以通过以下步骤实现：

                a. 从头结点开始遍历链表；

                b. 对于每个节点，执行相应的操作(如打印数据元素)。

                void Print(LinkList L) 
                {
                    Node* p = L->next;
                    while (p) 
                    {
                        printf("%c ", p->data);
                        p = p->next;
                    }
                }

                单链表的应用场景

                单链表在实际的软件开发中有广泛的应用，例如：

                • 数据库系统中的链表索引。

                  

                  • 实现栈和队列等其他数据结构。
                  • 图算法中的邻接表表示。