LinkedList

Posted on Edited on Views:

1、链表

链表的定义（来自维基百科）：

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（“links”）。

链表与顺序表的区别（来自维基百科）：

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表的优缺点（来自维基百科）：

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表的类型（来自维基百科）：

单向链表，双向链表以及循环链表。

2、单向链表

单向链表的定义：

单向链表是链表类型中最为简单的一种，每个节点包含两个域，一个数据域(data)，一个指针域(next)。单向链表的next节点指向下一节点，而尾节点的next节点为空。

单向链表节点的定义：

1
2
3
4
5
6
7
struct ListNode
{
	int val;
    ListNode *next;
    ListNode(int x):val(x),next(nullptr){}
};