资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

深入解析双向链表与单向链表的区别：示例详解

创作时间:

作者:

@小白创作中心

深入解析双向链表与单向链表的区别：示例详解

引用

CSDN

https://blog.csdn.net/qq_35320456/article/details/140401203

链表是一种灵活的数据结构，它通过指针连接一系列节点，实现了动态数组的特性。在众多链表类型中，单向链表和双向链表是最为常见的两种。本文将重点探讨这两种链表的区别，并通过示例进行详细说明。

一、单向链表与双向链表的定义及结构

单向链表

定义：单向链表是链表的一种，每个节点包含数据域和一个指向下一个节点的指针。

结构示例：

节点Node {
    int data; // 数据域
    Node next; // 指针域，指向下一个节点
}

双向链表

定义：双向链表是链表的一种，每个节点包含数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。

结构示例：

节点Node {
    int data; // 数据域
    Node prev; // 指针域，指向前一个节点
    Node next; // 指针域，指向下一个节点
}

二、单向链表与双向链表的区别示例

插入操作

假设要在链表中的某个节点后插入一个新的节点，以下是单向链表和双向链表的插入操作示例。

单向链表插入操作：

// 假设要在节点p后插入新节点newNode
newNode.next = p.next;
p.next = newNode;

双向链表插入操作：

// 假设要在节点p后插入新节点newNode
newNode.prev = p;
newNode.next = p.next;
if (p.next != null) {
    p.next.prev = newNode;
}
p.next = newNode;

从上述示例可以看出，双向链表在插入操作时需要同时维护前驱节点和后继节点的指针，而单向链表只需维护后继节点的指针。

删除操作

假设要删除链表中的某个节点，以下是单向链表和双向链表的删除操作示例。

单向链表删除操作：

// 假设要删除节点p
if (p.prev != null) {
    p.prev.next = p.next;
}

双向链表删除操作：

// 假设要删除节点p
if (p.prev != null) {
    p.prev.next = p.next;
} else {
    // p是头节点，需要更新头节点
    head = p.next;
}
if (p.next != null) {
    p.next.prev = p.prev;
}

从上述示例可以看出，双向链表在删除操作时需要同时维护前驱节点和后继节点的指针，而单向链表只需维护前驱节点的指针。

三、完整示例

以下是双向链表的一个简单示例（C++）：

#include <iostream>
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }
    void printList() const {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " <-> ";
            temp = temp->next;
        }
        std::cout << "NULL" << std::endl;
    }
    ~DoublyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};
int main() {
    DoublyLinkedList list;
    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);
    list.printList();
    return 0;
}

在这个示例中，我们创建了一个双向链表，并在链表头部插入新结点。注意，插入操作中需要同时更新新结点的next和prev指针，以及前一个结点的prev指针和后一个结点的next指针。

以下是单向链表的一个简单示例（C++）：

#include <iostream>
struct Node {
    int data;
    Node* next;
    Node(int data) : data(data), next(nullptr) {}
};
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}
    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }
    void printList() const {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "NULL" << std::endl;
    }
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};
int main() {
    LinkedList list;
    list.insertAtHead(3);
    ist.insertAtHead(2);
    list.insertAtHead(1);
    list.printList();
    return 0;
}