Chapter 2 Linked List

链表基础

链表是一种通过指针串联将需要存储的值在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

• 涉及到的特殊概念
  • 头节点
    • 头节点是指链表中第一个节点，它是链表的入口点。
    • 头节点通常包含链表的元数据信息，例如链表的长度、节点的类型等。
    • 头节点可以是一个空节点，也可以包含一些数据。
  • 尾节点
    • 尾节点是指链表中最后一个节点，它是链表的结束点。
    • 尾节点通常不包含任何数据，它的指针域指向null。
  • 虚拟头节点
    • 虚拟头节点是指链表中一个特殊的节点，它没有实际的数据，只是为了方便链表的操作而存在。
    • 虚拟头节点通常在链表的头部添加，它的指针域指向链表的第一个节点。
    • 虚拟头节点可以简化链表的操作，例如在链表的头部插入节点、删除节点等。
  • 虚拟尾节点
    • 虚拟尾节点是指链表中一个特殊的节点，它没有实际的数据，只是为了方便链表的操作而存在。
    • 虚拟尾节点通常在链表的尾部添加，它的指针域指向null。
    • 虚拟尾节点可以简化链表的操作，例如在链表的尾部插入节点、删除节点等。
  • 空链表
    • 空链表是指链表中没有任何节点。
    • 空链表通常不包含任何数据，它的指针域指向null。
    • 空链表通常不包含任何数据，它的指针域指向null。

链表的类型

接下来说一下链表的几种类型:

单链表

单链表中的指针域只能指向节点的下一个节点。

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。因此，双链表可以向前查询和向后查询。

环形链表

将单链表或者双链表的尾节点指向头节点，从而组成一个环形链表。

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表的定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

虽然不定义链表构造函数的前提下，C++ 默认不充一个构造函数，会但是这个构造函数不会初始化任何成员变量，下面我来举两个例子：

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

链表的操作

删除节点

实现思路

1. 找到待删除节点的上一个节点。
2. 让上一个节点的next指针指向待删除节点的下一个节点。

代码实现

func (l *ListNode) DeleteNode(val int) {
    cur := l
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        }
        cur = cur.Next
    }
}

添加节点

实现思路

1. 找到待添加节点的上一个节点。
2. 让待添加节点的next指针指向待添加节点的上一个节点的next指针指向的节点。
3. 让待添加节点的上一个节点的next指针指向待添加节点。

代码实现

func (l *ListNode) AddNode(val int) {
    cur := l
    for cur!= nil && cur.Next!= nil {
        cur = cur.Next
    }
    cur.Next = &ListNode{Val: val}
}