c++单链表和双链表
时间: 2024-09-05 14:00:18 浏览: 30
C++中的单链表和双链表都是线性数据结构,用于动态存储元素,它们的主要区别在于节点之间链接的方式:
1. 单链表(Single Linked List):
- 每个节点包含一个数据域和一个指向下一个节点的指针(next),形成单向连接。
- 插入、删除操作通常只需要修改少数几个节点的指针即可,效率较高。
- 由于只有一条从头到尾的链路,遍历顺序只能从前向后,无法直接访问前一个节点。
2. 双链表(Double Linked List):
- 节点除了有数据域和指向下一个节点的指针(next)外,还有一个额外的指针(prev)指向前一个节点,形成双向连接。
- 这使得插入和删除操作更灵活,可以双向移动,同时也支持快速定位任意位置的节点。
- 遍历顺序可以是双向的,即既可以从前向后也可以从后向前。
相关问题
单链表和双链表的查找,增加,删除,修改相关代码
单链表的定义和基本操作:
```c++
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
查找:
```c++
ListNode* find(ListNode* head, int val) {
ListNode* curr = head;
while (curr != NULL && curr->val != val) {
curr = curr->next;
}
return curr;
}
```
增加:
```c++
void insert(ListNode* &head, int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
head = newNode;
}
```
删除:
```c++
void remove(ListNode* &head, int val) {
ListNode* curr = head;
ListNode* prev = NULL;
while (curr != NULL && curr->val != val) {
prev = curr;
curr = curr->next;
}
if (curr == NULL) {
return;
}
if (prev == NULL) {
head = curr->next;
} else {
prev->next = curr->next;
}
delete curr;
}
```
修改:
```c++
void modify(ListNode* head, int val, int newVal) {
ListNode* curr = find(head, val);
if (curr != NULL) {
curr->val = newVal;
}
}
```
双链表的定义和基本操作:
```c++
struct ListNode {
int val;
ListNode *prev;
ListNode *next;
ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};
```
查找:
```c++
ListNode* find(ListNode* head, int val) {
ListNode* curr = head;
while (curr != NULL && curr->val != val) {
curr = curr->next;
}
return curr;
}
```
增加:
```c++
void insert(ListNode* &head, int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
}
```
删除:
```c++
void remove(ListNode* &head, int val) {
ListNode* curr = find(head, val);
if (curr == NULL) {
return;
}
if (curr->prev != NULL) {
curr->prev->next = curr->next;
} else {
head = curr->next;
}
if (curr->next != NULL) {
curr->next->prev = curr->prev;
}
delete curr;
}
```
修改:
```c++
void modify(ListNode* head, int val, int newVal) {
ListNode* curr = find(head, val);
if (curr != NULL) {
curr->val = newVal;
}
}
```
数据结构双链表基本操作
双向链表的基本操作包括:判断链表是否为空、计算链表的长度、遍历链表。判断链表是否为空和计算链表的长度的方法和单链表一样,主要和双向链表中的指向后继的指针有关。遍历链表时,需要遍历指向后继的指针和指向前驱的指针。
双向链表的插入操作和单链表有所不同。插入操作需要修改指向前驱和指向后继的指针。具体的算法思想和单链表的思想相同,只是修改的指针不同。
下面是一个双向链表插入操作的示例代码:
```c++
int ListInsert(DuLinkList &L, int i, int e) {
// 在双向链表的第i个位置之前插入元素e,1<=i<=表长
struct DuLNode *p;
p = L;
int j = 0;
while (p->next && j < i - 1) {
p = p->next;
j++;
}
if (!(p->next) || j > i - 1) {
return 0;
}
DuLNode *s; // 生成要插入的结点
s = new DuLNode;
s->data = e;
p->next->prior = s;
s->next = p->next;
p->next = s;
s->prior = p;
return 1;
}
```
以上是双向链表的基本操作,可以根据这些操作进行双向链表的创建、插入、删除等操作。