什么是单链表 单链表是什么？

什么是单链表

在计算机科学中，链表是一种数据结构，是由一组节点组成。每个节点都包含数据和指向下一个节点的指针（或引用）。其中，单链表是其中一种非常常见的链表结构，它的每个节点都只有一个指针，指向下一个节点。

单链表可以很好地解决数组大小固定的问题，因为链表的大小是可以在运行时动态增加的。同时，还可以轻松地在链表中添加或删除元素。因此单链表成为计算机程序设计中非常重要的数据结构。

单链表的节点

单链表的节点是由两部分组成：数据和指向下一个节点的指针。数据可以是任何类型的数据，可以是一个数字、字符串、结构体等等。指针是一个变量，用于保存下一个节点的地址。

接下来我们来看一个简单的单链表节点的定义，它包含一个整型数据和一个指向下一个节点的指针：

struct ListNode {
    int val;          // 节点的值
    ListNode *next;   // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}
};

单链表的遍历

遍历单链表是我们对单链表进行操作的基础。我们可以使用一个指针从单链表的头节点开始，不断遍历下一个节点，直到链表的尾部。下面是遍历单链表的代码实现：

ListNode* p = head;
while (p) {
    // 访问p所指向的节点
    p = p->next;
}

上面的代码从头节点开始遍历，只要p不为NULL，就继续往下一个节点移动。这样就可以顺序遍历整个单链表了。

单链表的插入和删除

单链表的插入和删除操作也非常重要。我们可以在链表的任意一个位置插入新的节点，也可以删除链表中任意一个节点。下面我们分别来看一下单链表的插入和删除操作：

单链表的插入操作

单链表的插入操作有两种情况：在链表头部插入一个节点和在链表中间插入一个节点。

在链表头部插入一个节点，只需要将新节点的next指向链表的头节点，然后将链表的头指针指向新节点即可。如下所示：

ListNode* new_node = new ListNode(val);
new_node->next = head;
head = new_node;

而在链表中间插入一个节点，也分为两种情况：在某个节点前面插入一个节点和在某个节点后面插入一个节点。以在某个节点前面插入一个节点为例，我们需要找到要插入的位置的前一个节点pre，然后执行如下代码：

ListNode* new_node = new ListNode(val);
new_node->next = pre->next;
pre->next = new_node;

单链表的删除操作

单链表的删除操作也有两种情况：删除链表头部节点和删除链表中间的节点。

删除链表头部节点，只需要将链表的头指针指向下一个节点即可。如下所示：

ListNode* tmp = head;
head = head->next;
delete tmp;

而删除链表中间的节点，也需要找到要删除的节点的前一个节点pre，然后执行如下代码：

Listnode* tmp = pre->next;
pre->next = tmp->next;
delete tmp;

总结

单链表是一种非常常见的数据结构，具有动态分配内存、添加和删除元素简单等特点。我们需要掌握单链表节点的定义、遍历、插入和删除操作等基本操作，以便日后在算法和程序设计中能够灵活运用。