双向链表和单链表的创建有什么不同
时间: 2024-06-05 08:07:14 浏览: 12
单向链表的每个节点都有一个指向下一个节点的指针,而双向链表的每个节点既有一个指向下一个节点的指针,又有一个指向前一个节点的指针。因此,双向链表相比单向链表,多了一个指向前一个节点的指针,使得双向链表可以双向遍历,而单向链表只能单向遍历。在创建时,单向链表只需要为每个节点分配一个指向下一个节点的指针即可,而双向链表则需要为每个节点分配一个指向下一个节点和一个指向前一个节点的指针。
相关问题
双向链表的插入和删除
双向链表的插入和删除操作相对于单链表来说,要稍微复杂一些。因为双向链表中的每个节点都同时具有前驱和后继指针,所以我们需要考虑这两个指针的变化。
下面分别介绍双向链表的插入和删除操作。
### 双向链表的插入操作
双向链表的插入操作分为两种情况:在链表头部插入和在链表尾部插入。
#### 在链表头部插入
在链表头部插入一个新节点的步骤如下:
1. 创建一个新节点,将其 next 指向当前头节点;
2. 将当前头节点的 prev 指针指向新节点;
3. 将新节点设置为新的头节点。
代码实现如下:
```
void insert_front(Node* &head, int data) {
Node* new_node = new Node(data);
new_node->next = head;
if (head != NULL) {
head->prev = new_node;
}
head = new_node;
}
```
#### 在链表尾部插入
在链表尾部插入一个新节点的步骤如下:
1. 创建新节点;
2. 将当前尾节点的 next 指针指向新节点;
3. 将新节点的 prev 指针指向当前尾节点;
4. 将新节点设置为新的尾节点。
代码实现如下:
```
void insert_back(Node* &head, int data) {
Node* new_node = new Node(data);
if (head == NULL) {
head = new_node;
} else {
Node* tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = new_node;
new_node->prev = tail;
}
}
```
### 双向链表的删除操作
双向链表的删除操作同样分为两种情况:删除头节点和删除尾节点。
#### 删除头节点
删除头节点的步骤如下:
1. 将头节点的 next 指针指向新的头节点;
2. 如果新的头节点不为空,则将其 prev 指针设置为 NULL;
3. 释放原来的头节点。
代码实现如下:
```
void delete_front(Node* &head) {
if (head == NULL) {
return;
}
Node* old_head = head;
head = head->next;
if (head != NULL) {
head->prev = NULL;
}
delete old_head;
}
```
#### 删除尾节点
删除尾节点的步骤如下:
1. 找到当前尾节点的前一个节点;
2. 将该节点的 next 指针设置为 NULL;
3. 释放原来的尾节点。
代码实现如下:
```
void delete_back(Node* &head) {
if (head == NULL) {
return;
}
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node* tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
tail->prev->next = NULL;
delete tail;
}
```
以上就是双向链表的插入和删除操作的实现。
用go语言编写程序基于结构体和指针定义单链表和双向循环链表。
以下是基于结构体和指针定义单链表和双向循环链表的示例代码:
单链表:
```go
package main
import "fmt"
type ListNode struct {
val int
next *ListNode
}
func main() {
// 创建链表
head := &ListNode{val: 0, next: nil}
node1 := &ListNode{val: 1, next: nil}
node2 := &ListNode{val: 2, next: nil}
node3 := &ListNode{val: 3, next: nil}
head.next = node1
node1.next = node2
node2.next = node3
// 遍历链表
p := head
for p != nil {
fmt.Printf("%d ", p.val)
p = p.next
}
}
```
双向循环链表:
```go
package main
import "fmt"
type ListNode struct {
val int
prev *ListNode
next *ListNode
}
func main() {
// 创建链表
head := &ListNode{val: 0, prev: nil, next: nil}
node1 := &ListNode{val: 1, prev: nil, next: nil}
node2 := &ListNode{val: 2, prev: nil, next: nil}
node3 := &ListNode{val: 3, prev: nil, next: nil}
head.next = node1
node1.prev = head
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = head
head.prev = node3
// 遍历链表
p := head.next
for p != head {
fmt.Printf("%d ", p.val)
p = p.next
}
}
```
以上代码仅为示例代码,实际应用中需要根据具体情况进行修改。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)