链表基础

链表的定义

链表的定义。

刷leetcode的链表的节点都默认定义好了，直接用就行了

没有注意到链表的节点是如何定义的。

C/C++的定义链表节点方式，如下所示：

// 单链表
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;

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

性能分析

再把链表的特性和数组的特性进行一个对比，如图所示：