极客笔记C++ 创建链表
什么是链表
链表是一种线性数据结构，由一系列节点组成。每个节点存储着一段数据和对列表中下一个节点的引用（指针）。链表适用于存储数据集合时，集合大小未知或数据频繁插入或删除的情况。
在C++中，我们可以通过定义一个节点类和一个链表类来创建链表。节点类代表列表中的单个节点，包含一个数据字段和一个指向下一个节点的指针。链表类中包含一个头指针，指向列表中的第一个节点，并包含用于插入、删除和遍历列表中节点的各种方法。
下面是一个C++中节点类的示例：
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
这个节点类有一个公共数据字段 data ，类型为 int ，和一个指向列表中下一个节点的公共指针 next 。它还有一个构造函数，用于初始化数据字段并将下一个指针设置为nullptr。
以下是使用节点和链表类创建和操作链表的C++示例：
#include
using namespace std;
// Node class
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Linked list class
class LinkedList {
private:
Node *head;
public:
LinkedList() {
this->head = nullptr;
}
void insertAtBeginning(int data) {
Node *newNode = new Node(data);
newNode->next = head;
head = newNode;
}
void insertAtEnd(int data) {
Node *newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node *temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteAtBeginning() {
if (head == nullptr) {
return;
}
Node *temp = head;
head = head->next;
delete temp;
}
void deleteAtEnd() {
if (head == nullptr) {
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node *temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
void printList() {
Node *temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
// Create a linked list
LinkedList List;
// Insert some nodes at the beginning of the list
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
// Insert some nodes at the end of the list
list.insertAtEnd(4);
list.insertAtEnd(5);
list.insertAtEnd(6);
// Print the list
cout << "Original list: ";
list.printList();
// Delete a node at the beginning of the list
list.deleteAtBeginning();
// Print the List again
cout << "List after deleting a node at the beginning: ";
list.printList();
// Delete a node at the end of the list
list.deleteAtEnd();
// Print the List again
cout << "List after deleting a node at the end: ";
list.printList();
return 0;
}
输出：
解释：
这个链表类有一个指向链表中第一个节点的私有字段head，并且有各种公共方法，用于在链表的开头和末尾插入和删除节点，并将链表打印到控制台上。这个程序将创建一个链表，在链表的开头和末尾插入一些节点，删除一个在链表开头和末尾的节点，并将链表打印到控制台。
下面是一个使用模板类在C++中创建链表的示例：
#include
template
class Node {
public:
T data;
Node *next;
Node(T data) {
this->data = data;
this->next = nullptr;
}
};
template
class LinkedList {
private:
Node *head;
public:
LinkedList() {
this->head = nullptr;
}
void insertAtBeginning(T data) {
Node *newNode = new Node(data);
newNode->next = head;
head = newNode;
}
void insertAtEnd(T data) {
Node *newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node *temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteAtBeginning() {
if (head == nullptr) {
return;
}
Node *temp = head;
head = head->next;
delete temp;
}
void deleteAtEnd() {
if (head == nullptr) {
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node *temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
void printList() {
Node *temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a linked list
LinkedList list;
// Insert some nodes at the beginning of the list
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
// Insert some nodes at the end of the list
list.insertAtEnd(4);
list.insertAtEnd(5);
list.insertAtEnd(6);
// Print the list
std::cout << "Original list: ";
list.printList();
// Delete a node at the beginning
// Delete a node at the beginning of the list
list.deleteAtBeginning();
// Print the List again
std::cout << "List after deleting a node at the beginning: ";
list.printList();
// Delete a node at the end of the list
list.deleteAtEnd();
// Print the List again
std::cout << "List after deleting a node at the end: ";
list.printList();
return 0;
}
输出：
解释:
在上面的代码中，我们定义了一个模板类Node，它表示链表中的一个节点。Node类有一个公共数据字段data，其类型为T（其中T是一个模板参数），还有一个公共指针指向List中的下一个节点。它还有一个构造函数，用于初始化数据字段并将下一个指针设置为nullptr。
我们还定义了一个模板类LinkedList，它表示一个链表，并包含一个私有字段head，该字段指向List中的第一个节点。LinkedList类有各种公共方法，用于在List的开头和结尾插入和删除节点，并将List打印到控制台上。
insertAtBeginning方法使用给定的数据创建一个新节点，并通过更新head指针将其插入到List的开头。insertAtEnd方法使用给定的数据创建一个新节点，并通过遍历List并更新最后一个节点的下一个指针将其插入到List的末尾。deleteAtBeginning方法通过更新head指针并释放节点使用的内存来删除List中的第一个节点。deleteAtEnd方法通过遍历List并更新倒数第二个节点的下一个指针来删除List中的最后一个节点。printList方法遍历List并将每个节点的数据打印到控制台上。
在main函数中，我们创建了一个LinkedList类的实例，并调用各种方法来插入、删除节点和打印List。输出显示了原始List，删除开头节点后的List以及删除末尾节点后的List。