社区首页 >专栏 >数据结构和算法之链表 | 链表介绍（难度级别：简单）

数据结构和算法之链表 | 链表介绍（难度级别：简单）

海拥

发布于 2021-08-23 09:44:04

59300

代码可运行

文章被收录于专栏：全栈技术全栈技术

运行总次数：0

代码可运行

与数组一样，链表是一种线性数据结构。与数组不同，链表元素不存储在连续的位置；元素使用指针链接。

为什么使用链表？

数组可用于存储类似类型的线性数据，但数组有以下限制。 1）数组的大小是固定的：所以我们必须提前知道元素数量的上限。此外，一般而言，分配的内存与使用情况无关，等于上限。 2)在元素数组中插入一个新元素是昂贵的，因为必须为新元素创建房间，并且必须移动现有元素才能创建房间。

例如，在一个系统中，如果我们在数组 id[] 中维护一个已排序的 ID 列表。 id[] = [1000, 1010, 1050, 2000, 2040]。

而如果我们要插入一个新的ID 1005，那么为了保持排序顺序，我们必须将1000之后的所有元素（不包括1000）移动。

除非使用某些特殊技术，否则删除数组的代价也很高。例如，要删除 id[] 中的 1010，必须移动 1010 之后的所有内容。

优于数组的优点

1)动态大小 2)易于插入/删除

缺点：

1)不允许随机访问。我们必须从第一个节点开始按顺序访问元素。所以我们不能用它的默认实现有效地对链表进行二分搜索。在这里阅读。 2)列表的每个元素都需要额外的指针存储空间。 3) 对缓存不友好。由于数组元素是连续的位置，因此存在引用的局部性，而在链表的情况下则不存在。

表示：

链表由指向链表第一个节点的指针表示。第一个节点称为头部。如果链表为空，则头部的值为NULL。

列表中的每个节点至少由两部分组成：

1) 数据 2) 指向下一个节点的指针（或引用）

在 C 中，我们可以使用结构来表示一个节点。下面是一个带有整数数据的链表节点的例子。在 Java 或 C# 中，LinkedList 可以表示为一个类，而一个 Node 可以表示为一个单独的类。LinkedList 类包含一个 Node 类类型的引用。

第一个简单链表

1.C

//一个链表节点
struct Node {
	int data;
	struct Node* next;
};

2.C++

class Node {
public:
	int data;
	Node* next;
};

3.Java

class LinkedList {
    Node head; // head of the list
    /* 链表节点*/
    class Node {
        int data;
        Node next;
        // 创建新节点的构造函数
        // next  默认初始化为 null
        Node(int d) { data = d; }
    }
}

4.Python

class Node:

	# 初始化节点对象的函数
	def __init__(self, data):
		self.data = data # 分配数据
		self.next = None # 将 next 初始化为 null

class LinkedList:	
	# 初始化链表对象的函数
	def __init__(self):
		self.head = None

5.C#

class LinkedList {
	// 链表的第一个节点（head）
	// 将是 Node 类型的对象（默认为 null）
	Node head;
	class Node {
		int data;
		Node next;
		// 创建新节点的构造函数
		Node(int d) { data = d; }
	}
}

让我们创建一个具有 3 个节点的简单链表。

// 一个示例 C++ 程序来介绍
// 一个链表
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

// 程序创建一个简单的链接
// 包含 3 个节点的列表
int main()
{
	Node* head = NULL;
	Node* second = NULL;
	Node* third = NULL;

	// 在堆中分配 3 个节点
	head = new Node();
	second = new Node();
	third = new Node();

	/* 三个块已被动态分配。
		我们有指向这三个块的指针作为头部，
		第二个和第三个
	head		 second		 third
		|			 |			 |
		|			 |			 |
	+---+-----+	 +----+----+	 +----+----+
	| # | # |	 | # | # |	 | # | # |
	+---+-----+	 +----+----+	 +----+----+
	
# 代表任何随机值。
数据是随机的，因为我们没有分配
什么都还没有 */

	head->data = 1; // 在第一个节点分配数据
	head->next = second; // 将第一个节点与
	// 第二个节点

	/* 数据已分配到第一个的数据部分
		块（头部指向的块）。 接下来
		第一个块的指针指向第二个。
		所以他们两个是有联系的。

	head		 second		 third
		|			 |			 |
		|			 |			 |
	+---+---+	 +----+----+	 +-----+----+
	| 1 | o----->| # | # |	 | # | # |
	+---+---+	 +----+----+	 +-----+----+	
*/

	// 将数据分配给第二个节点
	second->data = 2;

	// 将第二个节点与第三个节点连接起来
	second->next = third;

	/* 数据已经分配到第二个数据部分
	   块（由秒指向的块）。 接下来
	   第二个块的指针指向第三个
	   堵塞。 所以所有三个块都是链接的。
	
	head		 second		 third
		|			 |			 |
		|			 |			 |
	+---+---+	 +---+---+	 +----+----+
	| 1 | o----->| 2 | o-----> | # | # |
	+---+---+	 +---+---+	 +----+----+	 */

	third->data = 3; // 将数据分配给第三个节点
	third->next = NULL;

	/* 数据已分配到第三个数据部分
	块（由第三个指向的块）。 和下一个指针
	第三块的 NULL 表示
	链表在这里终止。

	我们已经准备好了链表。

		head	
			|
			|
		+---+---+	 +---+---+	 +----+------+
		| 1 | o----->| 2 | o-----> | 3 | NULL |
		+---+---+	 +---+---+	 +----+------+	
	
	
	请注意，只有头部足以表示
	整个列表。 我们可以遍历完整的
	按照下一个指针列出。*/
	return 0;
}

链表遍历

在前面的程序中，我们创建了一个简单的具有三个节点的链表。让我们遍历创建的列表并打印每个节点的数据。对于遍历，让我们编写一个通用函数 printList() 来打印任何给定的列表。

// 一个用于遍历链表的简单 C++ 程序
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

// 此函数打印链表的内容
// 从给定节点开始
void printList(Node* n)
{
	while (n != NULL) {
		cout << n->data << " ";
		n = n->next;
	}
}

// 驱动程序代码
int main()
{
	Node* head = NULL;
	Node* second = NULL;
	Node* third = NULL;

	// 在堆中分配 3 个节点
	head = new Node();
	second = new Node();
	third = new Node();

	head->data = 1; // 在第一个节点分配数据
	head->next = second; // 将第一个节点与第二个节点连接起来

	second->data = 2; // 将数据分配给第二个节点
	second->next = third;

	third->data = 3; // 将数据分配给第三个节点
	third->next = NULL;

	printList(head);

	return 0;
}