设计一个不带头结点的单链表类
时间: 2024-05-09 14:14:48 浏览: 45
不带头结点链表
好的,以下是一个不带头结点的单链表类的基本设计:
```c++
class LinkedList {
private:
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* head; // 头指针
public:
LinkedList() : head(nullptr) {}
~LinkedList() {
while (head) {
Node* temp = head->next;
delete head;
head = temp;
}
}
void insertFront(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}
void insertBack(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
} else {
Node* cur = head;
while (cur->next) {
cur = cur->next;
}
cur->next = newNode;
}
}
void remove(int val) {
if (head == nullptr) return;
if (head->data == val) {
Node* temp = head;
head = head->next;
delete temp;
} else {
Node* cur = head;
while (cur->next && cur->next->data != val) {
cur = cur->next;
}
if (cur->next) {
Node* temp = cur->next;
cur->next = cur->next->next;
delete temp;
}
}
}
void print() {
Node* cur = head;
while (cur) {
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}
};
```
这个类有两个私有成员:`Node` 结构体和头指针 `head`。`Node` 结构体表示一个单链表节点,包含一个数据成员 `data` 和一个指向下一个节点的指针 `next`。`head` 初始值为 `nullptr`。
公有成员包括构造函数、析构函数、在链表前面插入节点的函数 `insertFront`、在链表后面插入节点的函数 `insertBack`、删除节点的函数 `remove` 和打印链表的函数 `print`。
在 `insertFront` 中,首先创建一个新节点 `newNode`,然后将它的 `next` 指向当前头节点 `head`,最后将 `head` 指向新节点 `newNode`。
在 `insertBack` 中,首先创建一个新节点 `newNode`,然后判断当前链表是否为空。如果为空,将 `head` 指向新节点 `newNode`;否则,找到最后一个节点并将其 `next` 指向新节点 `newNode`。
在 `remove` 中,首先判断当前链表是否为空,或者头节点是否需要删除。如果是,直接删除头节点;否则,找到需要删除的节点的前一个节点 `cur`,将它的 `next` 指向要删除节点的下一个节点,最后删除要删除的节点。
在 `print` 中,从头节点开始遍历整个链表,并输出每个节点的值。
阅读全文