链表( Linked List )

链表是一种线性数据结构，由一系列节点组成。每个节点包含两个部分，一个是存储数据的部分，另一个是指向下一个节点的指针。与数组不同的是，链表中的节点在内存中不一定是连续存储的。

链表可以分为单向链表和双向链表两种类型。在单向链表中，每个节点只有一个指向下一个节点的指针，而在双向链表中，每个节点有两个指针，一个指向前一个节点，另一个指向后一个节点。

链表的插入和删除操作非常高效，因为只需要修改节点的指针即可完成操作。但是，链表的访问操作需要从头节点开始，逐个遍历直到找到目标节点，时间复杂度为O(n)，相比数组的O(1)访问时间要慢很多。

链表的优点是可以灵活地动态添加和删除节点，而且在内存管理方面比数组更加灵活。链表广泛应用于算法和数据结构中，例如链表可以用来实现栈、队列、哈希表等数据结构。

因为单链表比较简单，结构也比较单一，本篇文章就不做介绍

双链表 ( Doubly Linked List )

双链表 （DLL） 包含一个额外的指针 prev，以及 next 指针和链表中的 data

声明

我们以c++中的类为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Node {
public:
	int data;
	// 指向双链表的下一个结点
	Node* next;
	// 指向双链表的前一个结点
	Node* prev;
    
    //添加一个构造函数 用于初始化
    Node(int val) {
		data = val;
		prev = NULL;
		next = NULL;
	}
};

这段代码定义了一个名为 Node 的类，它表示双链表中的一个节点。该类具有三个成员变量：

  1. int data：该节点存储的数据。
  2. Node* next：指向双链表中的下一个节点，它是一个指针类型。
  3. Node* prev：指向双链表中的前一个节点，它也是一个指针类型。

在双链表中，每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。因此，通过定义prev和next两个指针变量，该类实现了双链表节点的功能。

插入节点

可以通过四种方式添加节点：

  • 在 DLL 的前面
  • 在给定节点之后
  • 在 DLL 的末尾
  • 在给定节点之前

为了使用起来更方便，再声明一个名为 Doubly linked list 的类

1
2
3
4
5
6
7
class DoublyLinkedList {
public:
	Node* head; //头节点
	DoublyLinkedList() {
	head = NULL; //同样的，构造函数用于初始化
	}
}

现在我们为它添加方法

在DLL头部插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insertAtHead(int val)
{
	// 创建一个新节点
	Node* newNode = new Node(val);

	// 设置新节点的数据域
	newNode->data = val;

	// 如果当前链表为空，则将新节点设置为头节点
	if (head == NULL) 
    {
		head = newNode;
	}

	// 设置新节点的next指针，指向当前链表的头节点
	newNode->next = head;

	// 设置当前链表的头节点的prev指针，指向新节点
	head->prev = newNode;

	// 将新节点设置为当前链表的头节点
	head = newNode;
}

在给定位置之后插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void insertAfter(int pos, int val) 
{
    //创建一个current来记录当前节点
	Node* current = head;
	//count 用于记录是否到达目标位置
    int count = 1;
	//依次遍历，并检查目标是否合法
    while (count < pos - 1 && current != NULL) 
    {
		current = current->next;//每次遍历更新节点
		count++;//更新
	}
    //如果目标位置不合法
	if (current == NULL)
		cout << "Invalid position" << endl;
    //找到目标，更新
	else
    {
		//将当前节点指向的下一个节点更新到新节点
        newNode->next = current->next;
        //新节点的上一个节点更新为当前节点
		newNode->prev = current;
        //如果插入位置不是尾节点
		if (current->next != NULL)
            //跟新下一个节点的prev指针为当前节点
			current->next->prev = newNode;
        //最后加入新节点
		current->next = newNode;
	}
}

如果你不知道之前节点的 prev 指针，那么就需要像上面这样从头开始遍历(或从尾 这里不细写了，思想是一样的)

如果要从知道的某一节点之后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void insertAfter(Node* prevNode, int val)
{
    // 1. 检查是否合法
    if (prev_node == NULL) {
        cout << "the given previous node cannot be NULL";
        return;
    }
 
    // 2. 创建新节点
    Node* newNode = new Node(val);
 
    // 3. 将当前节点指向的下一个节点更新到新节点
    newNode->next = prevNode->next;
 
    // 4. 新节点的上一个节点更新为当前节点
    prevNode->next = newNode;
 
    // 5. 新节点的上一个节点更新
    newNode->prev = prevNode;
 
    // 6. 如果插入位置不是尾节点
    if (new_node->next != NULL)
        // 跟新下一个节点的prev指针为当前节点
        new_node->next->prev = new_node;
}

在给定位置之前插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void insertBefore(Node* nextNode, int val)
{
    if (nextNode == NULL) 
    {
		cout << "the given next node cannot be NULL";
        return;
	}

	// 创建一个新节点
	Node* newNode = new Node(val);

	// 设置新节点的数据 这里传入的val已经在Node()中构造
	//newNode->data = newData;

	// 将新节点插入到nextNode之前
	newNode->prev = nextNode->prev;
	nextNode->prev = newNode;
	newNode->next = nextNode;

	// 如果新节点不是头节点，则更新新节点上一节点的next指针
	if (newNode->prev != NULL)
		newNode->prev->next = newNode;
	else
		head = newNode; // 如果新节点是头节点，则将head指向新节点
}

在DLL尾部插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void insertAtTail(int val) 
{
	// 创建一个新节点
	Node* newNode = new Node(val);

	// 设置新节点的数据域
	//newNode->data = newData;
	//newNode->next = NULL;

	// 如果链表为空，则将新节点作为头节点
	if (head == NULL) 
    {
		newNode->prev = NULL;
		head = newNode;
		return;
	}

	// 找到链表的最后一个节点
	Node* last = head; //创建一个节点代表目前最后节点 从头遍历
	while (last->next != NULL) 
    {
		last = last->next;
	}

	// 将新节点插入到链表的最后一个节点之后
	last->next = newNode;
    // 更新新节点的prev指针
	newNode->prev = last;
}

合并链表

我们可以声明一个函数，直接对类操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
DoublyLinkedList mergeLists(DoublyLinkedList list1, DoublyLinkedList list2)
{
	// 初始化一个名为合并链表的链表
    DoublyLinkedList mergeList;
    // 声明两个临时节点
	Node* current1 = list1.head;
	Node* current2 = list2.head;
    // 下面就是判断合并的条件
	while(current1 != NULL || current2 != NULL)// 两个链表若为空就直接返回
	{
		if(current1 == NULL && current2 !=NULL)// 若链表2不为空
		{
			mergeList.insertAtTail(current2->data);// 将链表2的元素逐步尾插到mergeLists
			current2 = current2->next;
		}
		if(current2 == NULL && current1 !=NULL)// 若链表1不为空
		{
			mergeList.insertAtTail(current1->data);// 将链表1的元素逐步尾插到mergeLists
			current1 = current1->next;
		}
		if(current1 != NULL && current2 != NULL)// 若链表1 和 链表2都不为空
		{
			// 比较 将两个链表中较小的元素先尾插
            if(current1->data < current2->data)
			{
				mergeList.insertAtTail(current1->data);
				// 更新
                current1 = current1->next;
			}
			else
			{
				mergeList.insertAtTail(current2->data);
				// 更新
                current2 = current2->next;
			}
		}
	}
	return mergeList;
}

打印

顺序打印

从头节点开始遍历，逐个打印

1
2
3
4
5
6
7
8
9
void printList(DoublyLinkedList list)
{
	Node* current = list.head;
	while (current != NULL) 
    {
		cout << current->data << " ";
		current = current->next;
	}
}

逆序打印

需要遍历到最后一个节点，再往前打印

1
2
3
4
5
6
7
8
9
10
11
12
13
void printReverseList(DoublyLinkedList list)
{
	Node* current = list.head;
	while (current->next != NULL) 
    {
		current = current->next;
	}
	while(current != NULL)
    {
		cout << current->data << ' ';
		current = current->prev;
	}
}

以上就是 使用C++中的类来完成对链表的基本操作

如果您发现有误，请在评论区留言或联系我