数据结构单链表详细介绍自己代码
时间: 2023-10-24 19:10:05 浏览: 36
单链表是一种常见的数据结构,它由多个节点组成。每个节点包含两个部分:数据域和指针域。数据域用于存储节点中的数据,指针域用于指向下一个节点的地址。通过指针,多个节点可以组成一个链表,形成一种线性结构。
下面是一个简单的单链表的代码实现:
```C++
#include <iostream>
using namespace std;
// 定义节点结构体
struct ListNode {
int val; // 数据域
ListNode *next; // 指针域
ListNode(int x) : val(x), next(NULL) {} // 构造函数
};
// 定义链表类
class LinkedList {
public:
LinkedList() : head(NULL) {} // 构造函数
~LinkedList(); // 析构函数
void insert(int val); // 插入节点
void remove(int val); // 删除节点
void print(); // 打印链表
private:
ListNode *head; // 头指针
};
// 析构函数
LinkedList::~LinkedList() {
ListNode *p = head;
while (p != NULL) {
ListNode *q = p->next;
delete p;
p = q;
}
}
// 插入节点
void LinkedList::insert(int val) {
ListNode *node = new ListNode(val);
if (head == NULL) {
head = node;
} else {
ListNode *p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = node;
}
}
// 删除节点
void LinkedList::remove(int val) {
if (head == NULL) {
return;
}
if (head->val == val) {
ListNode *p = head;
head = head->next;
delete p;
} else {
ListNode *p = head;
while (p->next != NULL && p->next->val != val) {
p = p->next;
}
if (p->next != NULL) {
ListNode *q = p->next;
p->next = q->next;
delete q;
}
}
}
// 打印链表
void LinkedList::print() {
ListNode *p = head;
while (p != NULL) {
cout << p->val << " -> ";
p = p->next;
}
cout << "NULL" << endl;
}
// 测试代码
int main() {
LinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.print();
list.remove(2);
list.print();
return 0;
}
```
在这个实现中,我们定义了一个 ListNode 结构体,其中包含了一个整数类型的数据域和一个指针类型的指针域。同时,我们定义了一个 LinkedList 类,用于实现单链表的基本操作。
在 insert 方法中,我们首先创建一个新的节点,然后遍历链表,找到最后一个节点,将新节点插入到链表的末尾。
在 remove 方法中,我们首先判断头节点是否是要删除的节点,如果是,直接删除头节点。否则,遍历链表,找到要删除的节点,将其从链表中移除。
最后,在 print 方法中,我们遍历链表,将每个节点的值打印出来。