数据结构单链表四个操作

单链表是由节点组成的数据结构，每个节点包含了一个数据元素和一个指向下一个节点的指针。

单链表的四个基本操作包括：

1. 插入节点：在链表的某个位置插入一个新的节点，需要修改前一个节点的指针，使其指向新节点，新节点的指针指向后一个节点。

2. 删除节点：从链表中删除一个节点，需要修改前一个节点的指针，使其指向后一个节点。

3. 查找节点：在链表中查找一个节点，需要遍历链表，比较每个节点中的数据元素，直到找到匹配的节点或者到达链表的末尾。

4. 遍历链表：遍历整个链表，访问每个节点中的数据元素。

需要注意的是，在单链表中，只能从前往后遍历，无法从后往前遍历，因为每个节点只有一个指针指向下一个节点。如果需要从后往前遍历，可以使用双向链表。

相关问题

数据结构单链表四个操作代码

单链表是一种常见的数据结构，它由多个节点组成，每个节点都包含了一个数据元素和指向下一个节点的指针。单链表常用的四个操作包括：创建链表、插入节点、删除节点和遍历链表。以下是使用 C 语言实现单链表的四个操作的代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点的结构体
typedef struct ListNode {
    int val;                // 节点存储的数据
    struct ListNode* next;  // 指向下一个节点的指针
} ListNode;

// 创建一个新的节点
ListNode* createNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// 创建一个单链表并返回头节点
ListNode* createList(int* arr, int n) {
    if (n == 0) return NULL;
    ListNode* head = createNode(arr[0]);
    ListNode* p = head;
    for (int i = 1; i < n; i++) {
        p->next = createNode(arr[i]);
        p = p->next;
    }
    return head;
}

// 在单链表的指定位置插入一个新节点
void insertNode(ListNode* head, int pos, int val) {
    ListNode* node = createNode(val);
    // 找到要插入位置的前一个节点
    ListNode* p = head;
    for (int i = 0; i < pos - 1; i++) {
        p = p->next;
    }
    // 插入新节点
    node->next = p->next;
    p->next = node;
}

// 在单链表中删除指定位置的节点
void deleteNode(ListNode* head, int pos) {
    // 找到要删除节点的前一个节点
    ListNode* p = head;
    for (int i = 0; i < pos - 1; i++) {
        p = p->next;
    }
    // 删除节点
    ListNode* node = p->next;
    p->next = node->next;
    free(node);
}

// 遍历单链表
void traverseList(ListNode* head) {
    ListNode* p = head;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(int);
    ListNode* head = createList(arr, n);
    traverseList(head);
    insertNode(head, 2, 6);
    traverseList(head);
    deleteNode(head, 3);
    traverseList(head);
    return 0;
}

单链表的基本操作及应用

单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的基本操作包括：创建、插入、删除、查找和显示。下面是具体的实现步骤：

1. 创建单链表：定义一个 `Node` 结构体，用于表示链表的节点，其中包括一个数据元素和一个指向下一个节点的指针。然后定义一个 `LinkedList` 类，其中包括一个头节点指针，用于指向链表的头节点。链表的创建可以通过从头节点开始，依次插入新的节点来实现。

   struct Node {
       int data;
       Node* next;
   };
   
   class LinkedList {
   public:
       LinkedList() {
           head = new Node;
           head->next = nullptr;
       }
   
       void createList(int n) {
           Node* p = head;
           for (int i = 0; i < n; i++) {
               int data;
               cout << "请输入第" << i + 1 << "个节点的值：";
               cin >> data;
               Node* node = new Node;
               node->data = data;
               node->next = nullptr;
               p->next = node;
               p = node;
           }
       }
   
   private:
       Node* head;
   };

2. 插入节点：提供 `insertNode()` 方法，可以在链表中插入新的节点。需要考虑插入的位置和节点的值。比如，插入到链表的第三个位置，可以先找到链表的第二个节点，然后将新节点的指针指向第三个节点，第二个节点的指针指向新节点。

   void insertNode(int pos, int data) {
       Node* p = head;
       for (int i = 0; i < pos - 1; i++) {
           p = p->next;
       }
       Node* node = new Node;
       node->data = data;
       node->next = p->next;
       p->next = node;
   }

3. 删除节点：提供 `deleteNode()` 方法，可以删除链表中的指定节点。需要考虑被删除节点的前驱节点和后继节点的连接。比如，删除链表的第三个节点，可以先找到链表的第二个节点，然后将第二个节点的指针指向第四个节点，释放第三个节点的内存空间。

   void deleteNode(int pos) {
       Node* p = head;
       for (int i = 0; i < pos - 1; i++) {
           p = p->next;
       }
       Node* q = p->next;
       p->next = q->next;
       delete q;
   }

4. 查找节点：提供 `searchNode()` 方法，可以在链表中查找指定值的节点。需要遍历整个链表，依次比较节点的值。如果找到了目标节点，返回它的位置；否则返回 -1。

   int searchNode(int data) {
       Node* p = head->next;
       int pos = 1;
       while (p != nullptr) {
           if (p->data == data) {
               return pos;
           }
           p = p->next;
           pos++;
       }
       return -1;
   }

5. 显示链表：提供 `displayList()` 方法，可以将整个链表打印出来，方便查看和调试。需要遍历整个链表，依次输出每个节点的值。

   void displayList() {
       Node* p = head->next;
       while (p != nullptr) {
           cout << p->data << " ";
           p = p->next;
       }
       cout << endl;
   }

6. 通讯录设计（应用）：在 `Node` 结构体中增加姓名、电话等属性，实现通讯录的基本功能，比如添加联系人、删除联系人、查找联系人等。

   struct Node {
       string name;
       string phone;
       Node* next;
   };
   
   class AddressBook {
   public:
       AddressBook() {
           head = new Node;
           head->next = nullptr;
       }
   
       void addContact(string name, string phone) {
           Node* p = head;
           while (p->next != nullptr) {
               p = p->next;
           }
           Node* node = new Node;
           node->name = name;
           node->phone = phone;
           node->next = nullptr;
           p->next = node;
       }
   
       void deleteContact(string name) {
           Node* p = head;
           while (p->next != nullptr) {
               if (p->next->name == name) {
                   Node* q = p->next;
                   p->next = q->next;
                   delete q;
                   return;
               }
               p = p->next;
           }
           cout << "通讯录中不存在该联系人！" << endl;
       }
   
       void searchContact(string name) {
           Node* p = head->next;
           while (p != nullptr) {
               if (p->name == name) {
                   cout << "姓名：" << p->name << "，电话：" << p->phone << endl;
                   return;
               }
               p = p->next;
           }
           cout << "通讯录中不存在该联系人！" << endl;
       }
   
       void displayContacts() {
           Node* p = head->next;
           while (p != nullptr) {
               cout << "姓名：" << p->name << "，电话：" << p->phone << endl;
               p = p->next;
           }
       }
   
   private:
       Node* head;
   };