首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

一种用于双向链表C++的插入方法

双向链表的插入方法

基础概念

双向链表(Doubly Linked List)是一种链式数据结构,其中每个节点包含三个部分:数据域、前驱指针(指向前一个节点)和后继指针(指向后一个节点)。这种结构允许从任意节点向前或向后遍历链表。

插入方法的优势

  1. 灵活性:双向链表允许在任何位置插入或删除节点,而不需要移动其他节点。
  2. 高效查找:虽然链表的查找效率不如数组,但双向链表可以通过前驱和后继指针快速定位前后节点。
  3. 内存利用率:链表的节点可以动态分配内存,不需要预先分配固定大小的数组。

插入方法的类型

  1. 头插法:在链表头部插入新节点。
  2. 尾插法:在链表尾部插入新节点。
  3. 中间插法:在链表的任意位置插入新节点。

应用场景

双向链表广泛应用于需要频繁插入和删除操作的场景,例如:

  • LRU缓存:最近最少使用的缓存淘汰算法。
  • 双向链表栈:结合栈和链表的优点,实现高效的入栈和出栈操作。
  • 图和树的遍历:在某些遍历算法中,双向链表可以用于存储路径或状态。

插入方法的实现

以下是一个C++实现双向链表插入方法的示例代码:

代码语言:txt
复制
#include <iostream>

// 定义双向链表节点结构
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 定义双向链表类
class DoublyLinkedList {
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // 头插法
    void insertAtHead(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // 尾插法
    void insertAtTail(int value) {
        Node* newNode = new Node(value);
        if (!tail) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
    }

    // 中间插法
    void insertAtPosition(int value, int position) {
        if (position <= 0) {
            insertAtHead(value);
            return;
        }

        Node* newNode = new Node(value);
        Node* current = head;
        int count = 0;

        while (current && count < position - 1) {
            current = current->next;
            count++;
        }

        if (!current) {
            insertAtTail(value);
        } else {
            newNode->next = current->next;
            newNode->prev = current;
            if (current->next) {
                current->next->prev = newNode;
            } else {
                tail = newNode;
            }
            current->next = newNode;
        }
    }

    // 打印链表
    void printList() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

private:
    Node* head;
    Node* tail;
};

int main() {
    DoublyLinkedList list;
    list.insertAtHead(1);
    list.insertAtTail(3);
    list.insertAtPosition(2, 2);
    list.printList(); // 输出: 1 2 3
    return 0;
}

可能遇到的问题及解决方法

  1. 内存泄漏:在插入节点时,如果没有正确管理内存,可能会导致内存泄漏。解决方法是在删除节点时释放内存。
  2. 空指针异常:在访问节点的前驱或后继指针时,如果节点为空,会导致空指针异常。解决方法是在访问指针前检查节点是否为空。
  3. 插入位置错误:在中间插入节点时,如果插入位置超出链表范围,会导致插入失败。解决方法是检查插入位置的有效性。

参考链接

通过以上内容,你应该对双向链表的插入方法有了全面的了解,包括基础概念、优势、类型、应用场景以及常见问题的解决方法。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

DS双向链表—祖玛 C++

一旦有三个或更多同色珠子变成相邻,它们就会立即消失。这类消除现象可能会连锁式发生,其间你将暂时不能发射珠子。 给定轨道上初始珠子序列,然后是玩家所做一系列操作。...你任务是,在各次操作之后及时计算出新珠子序列。 输入 第一行是一个由大写字母'A'~'Z'组成字符串,表示轨道上初始珠子序列,不同字母表示不同颜色。...这道题关键在于消除,首先要注意到是三个或三个以上都能消,所以去判断连续三个或四个甚至五个方法是不行,所以我解决方法是先去数有多少个相同,大于等于三个才去消除,因为有可能会出现连环反应,所以必须写成循环...using namespace std; class Node { public: char data; Node * next = NULL; }; class List {//带头结点链表...List(); //析构函数,逐个结点回收 int Insert(char item, int i); //第i位置插入元素,操作成功或失败返回OK或ERROR void print();//打印单链表所有数据

21730

链表双向链表实现

前言 ---- 链表数据通过指针连接,添加、插入或删除节点只需要修改指针指向 实现思路 实现一个链表需要具备以下方法 在链表尾部添加节点 获取链表所有节点数据 链表指定位置插入元素 获取链表指定位置节点数据...获取节点在链表位置 更新链表指定位置数据 移除链表指定位置节点 移除链表指定节点 判断链表是否为空 获取链表长度 链表内部需要定义head指针和链表长度 实现代码 定义head指针和length...(linkedList.size()) 双向链表 双向链表指针是双向,前指针指向上一个节点,后指针指向下一个节点 head指向第一个节点,tail指向最后一个节点 双向链表实现思路 需要具备以下方法...判断链表是否为空 获取链表长度 定义head和tail分别指向第一个节点和最后一个节点 代码实现 /** * 双向链表 */ function DoublyLinkedList() { //指向第一个节点...this.tail = node } //链表长度加一 this.length += 1 } 向前遍历链表获取节点数据 forwardString() { //用于存储节点数据

70540
  • 循环双向链表

    链表使用 初级版:   结构体   struct data{     struct data* next;     int data;   };   head=p1->p2->p3->p4->NULL...  需要删除节点p3时就很麻烦,我们需要从头去遍历,找到next指针为p3时将next指针指向p3next;   为此方便起见,我们可以使用双向链表进行实现。...内核中是这样处理,   创建一个双向循环链表   =>headp1p2p3p4=   向链表中指定位置插入节点   原有链prenext   这也是最基本插入节点方法...}   根据插入节点方式写删除节点就容易多了   _del(struct data * pre,struct data * next){     pre->next = next;     next...}   没有做释放代码,创建链时候需要用malloc去创建,内核中双向链表正是这么实现,   特别容易书写,不太会产生副作用。二级指向是在太难理解了

    29010

    C++ 链链不忘@必有回响之双向链表

    前言 写过一篇与单链表相关博文,实际应用中,双向循环链表功能更强大。 单链表中,查询一个已知结点后驱结点时间复杂度为O(1)。...双向链表 双向链表中除了有存储头结点head头指针变量外,一般还会增加一个存储尾结点名为tail尾指针变量。这样,可以实现从头到尾或从尾到头对链表进行遍历。...在双向链表中,在尾结点后驱指针位存储头结点地址,头结点前驱指针位存储尾结点地址,形成一个首尾相连闭环,称这样链表双向循环链表。...双向链表需要提供对链表数据进行常规维护算法,如: 链表初始化。 创建链表。 查找。 后插入、前插入。 删除。...…… 算法整体思路和单链表相似,因结点中多了一个前驱结点信息,为各种操作带来便利同时,需要注意细节。下文将介绍双向链表几个重要函数。

    24110

    C++ STL源码剖析之双向环形链表list

    C++ STL源码剖析之双向环形链表list 0. 导语 源码对应版本为gcc-4.9.1 1.list list为双向环形链表,其结构为: ? 自己绘制图如下: ?...像前面提到push_back、push_front、_M_insert,还有insert都是使用最基础双向链表插入函数_M_hook实现。...sort接受输入迭代器是随机访问迭代器,但是双向list链表容器访问方式是双向迭代器,因此,不能使用STL本身排序算法sort,必须自己定义属于自己访问排序算法。..._M_node) { list __carry; // 辅助链表用于从a中提取元素以及临时保存两个链表合并结果 list __tmp[64]; // 保存着当前每一个归并层次结果...,用于从a中提取元素以及临时保存两个链表合并结果 list counter[64]; // 保存着当前每一个归并层次结果, i号链表保存元素个数为2i次方或者0 int

    1.6K40

    双向链表优雅实现

    文中涉及代码可访问 GitHub:https://github.com/UniqueDong/algorithms.git 上次我们说了「单向链表代码实现,今天带大家一起玩下双向链表双向链表节点比单项多了一个指针引用...双向链表就像渣男,跟「前女友」和「现女友」,还有一个「备胎』都保持联系。前女友就像是前驱节点,现女友就是 「当前 data」,而「next」指针就像是他套住备胎。...使用这样数据结构就能实现「进可攻退可守」灵活状态。 接下来让我们一起实现『渣男双向链表』。...prev; this.item = item; this.next = next; } } 代码实现 定义好渣男节点后,就开始实现我们双向链表...一种是在指定节点前面插入新节点。 在后面添加前面尾巴添加已经说过,对于在指定节点前面插入需要我们先找到指定位置节点,然后改变他们 prev next 指向。

    81530

    循环链表实现_建立双向循环链表

    循环链表   循环链表是一个收尾相接链表,将单链表最后一个指针域改由NULL改为指向表头结点这就是单链式循环链表,并称为循环单链表   带头结点循环单链表各种操作算法实现与带头结点单链表算法实现类似...单链表判别条件为p!=NULL或p->next!=NULL,而单循环链表判别条件是p!=L或p->next!=L   在循环单链表中附设尾指针有时候比附设头指针更简单。...如:在用头指针循环单链表中找a1时间复杂度是O(1),找an需要从头找到尾,时间复杂度是O(n),如果用为指针rear,找开始结点和终端结点存储位置分别是rear->next->next和rear...    方法一:先找到两个链表LA,LB表尾,分别用p,q指向它,然后将第一个链表表尾与第二个链表第一个结点连起来,修改第二个表尾q,使它链域指向第一个表头 //头指针合并循环链表 #include...;//返回新链表尾指针 }   循环链表求长度 #include #define len sizeof(Node) #include typedef struct

    74820

    C++奇迹之旅:双向链表容器list灵活使用技巧

    kw=list std::list 是 C++ 标准库中一个序列容器,它实现了双向链表(doubly linked list)。...列表是序列容器,允许在序列中任何位置进行常数时间插入和删除操作,并且支持双向遍历。 列表容器实现为双向链表双向链表可以将它们包含每个元素存储在不同且无关存储位置。...); explicit 关键字在 C++用于控制构造函数隐式转换行为。...具体来说,explicit 关键字主要用于防止以下两种情况: 隐式类型转换:构造函数可以被用于隐式地将一种类型对象转换为另一个类型。...总结 std::list是C++标准库中双向链表容器,具有常数时间内插入和删除元素优势。

    8210

    深入探索 C++ STL: 高效双向链表 list 使用与实践

    C++ STL(Standard Template Library) list 容器是双向链表实现,适合需要频繁插入和删除元素场景。...概述 C++ list 是一个双向链表,与 vector 或 deque 相比,它主要优点在于插入和删除操作效率较高,因为插入和删除操作只涉及局部节点调整,而不会像 vector 那样涉及整个容器重新分配...2. list 容器特性 list 是双向链表,具有以下几个显著特性: 双向链表:每个节点都包含指向前一个节点和后一个节点指针,支持从任意位置高效插入和删除操作。...list 提供了 sort() 函数用于链表元素进行排序。...由于 list 迭代器是双向迭代器,因此可以使用适用于双向迭代器所有算法。

    10210

    从零开始实现 C++ 双向链表:深入理解链表底层原理

    前言: 在 C++ 标准库中,std::list 是一种非常常用数据结构,其底层采用了双向链表实现。...在实际开发中,双向链表一种具有灵活插入和删除操作数据结构,尤其适合那些需要频繁操作非连续内存数据场景。本文将通过一个手动实现双向链表类 list 来讲解双向链表底层结构和实现原理。 1....总结 本文从底层实现角度详细讲解了如何手动实现一个双向链表容器 list。我们设计了双向链表数据结构,通过节点、迭代器、基本插入、删除操作,最终实现了一个功能完整链表容器。...4.迭代器操作与遍历:通过 begin() 和 end() 函数,我们可以使用 C++ 标准范围遍历方式遍历链表所有元素。...这使得链表容器使用方式与 C++ 标准库中其他容器一致,降低了使用门槛。 5.拷贝构造与赋值运算符:为了确保链表可以被正确拷贝,我们实现了拷贝构造函数和赋值操作符。

    9510

    双向链表增删改查

    双向链表,我们曾经拿了一幅非常形象图片来形容他,就像几个人手拉手围成一个圈一样。在我们代码中呈现就是每个节点都有一个指向下一个节点指针,同时也有一个指向上一个节点指针。...(如图) 双向链表图形表示: 【实现代码】 因为插入和删除节点步骤跟单向循环链表差不多,只是多了一个前驱指针,我们这里值给出代码,具体插入和删除操作示例图就不一一列举了。...#ifndef _DLINK_LIST_H #define _DLINK_LIST_H //自定义双向链表数据类型 typedef void DLinkList; //自定义双向链表节点数据类型 typedef...打印链表长度 printf(“打印链表长度, Length = %d\n”, DLinkList_Length(dlist)); //销毁双向链表 DLinkList_Destroy(dlist);...} void main() { dLinkListTest(); system(“pause”); } 双向链表增加了前驱指针,在功能上完全是可以替代单向链表,并且通过前驱指针我们可以更高效遍历所有元素

    13210

    c++链表-C++链表

    C++链表   链表是由一系列连接在一起结点构成,其中每个结点都是一个数据结构。   ...链表一种复杂数据结构,其数据之间相互关系使得链表分成三种:单链表、循环链表双向链表。   ...除了数据之外,每个结点还包含一根后继指针指向链表下一个结点。   单个结点组成   非空链表第一个结点称为链表头。要访问链表结点,需要有一个指向链表指针。...从链表头开始,可以按照存储在每个结点中后继指针访问链表其余结点。最后一个结点中后继指针被设置为 以指示链表结束。   指向链表指针用于定位链表头部,所以也可以认为它代表了链表头。...链表尾结点由于无后续结点c++链表,其指针域为空,写作NULL。

    96320

    C++进阶】深入STL之list:高效双向链表使用技巧

    前言:双向链表链表数据结构一种重要变体,它允许我们在链表任何位置进行高效插入和删除操作,而无需像数组那样进行大量数据移动。...1. list基本概念 list 是 C++ 标准模板库 (STL) 中一个容器,它基于双向链表实现。...双向链表一种动态数据结构,由一系列节点组成,每个节点包含数据元素和两个指向其他节点指针 在介绍list使用之前,我们先来看看它结构: 实际上:list就是一个带头双向链表 2. list...双向迭代器能支持++,--, 单向迭代器只支持++ 这些迭代器是向上兼容,随机访问迭代器是特殊单向迭代器 总结 通过本篇文章,我们一同探索了C++标准模板库(STL)中list容器奥秘。...list以其基于双向链表特性,为我们提供了在序列容器中进行高效插入和删除操作强大工具。

    26210

    单循环链表-带头双向循环链表实现

    今天我们就来学习一下结构最复杂带头双向循环链表!!!...;   虽然名字听上去比较复杂单循环链表,但是实现起来比单链表(全名:不带头、不循环、单向链表)更加简单,也不需要过多考虑特殊情况;   两种链表比较:(上面是单链表,下面是带头双向循环链表)   结构分析...  首先链表头节点是不存储有效数据(该节点被称为哨兵位),其次我们只需要知道改头节点指针就能找到整个链表单循环链表,并且便于对整个链表进行维护;   当然既然是双向嘛,那节点一定有个指针域指向前一个节点...  该链表尾插,比单链表尾插简单太多了,不用遍历找尾:    // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType...// 双向链表在pos前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置节点 void

    60530

    c++链表-链表入门(C++

    从上链表基础知识学习,进行总结如下:   1.单链表介绍   单链表与数组不同,数组中只存储元素值,而单链表中除了数据值外还包括了指向下一个节点引用字段通常以next来表示。...SinglyListNode *next; SinglyListNode(int x) : val(x), next(NULL) {}   与数组区别,我们无法随机访问链表元素...2.链表添加   链表添加又分为在中间添加、在头部添加以及在尾部添加,首先是头部添加:   头结点是整个链表代表因此在头部进行添加节点时最重要是添加后更新head:   初始化一个cur;将该结点连接到...这样与数组进行对比我们只需要O(1)时间复杂度就可以将元素插入进链表。   ...因为cur节点下一个节点就是cur->nextc++链表,但是上一个节点需要遍历才可以找到c++链表,因此删除节点时间复杂度为O(N)。

    82920

    双向链表三种实现

    这篇文章,其实很像是“茴字四种写法”。这让人不由想起来孔乙己。在我印象中,大多数人对孔乙己是持嘲讽态度。 但是从技术上讲,我觉得”茴字四种写法”在满足需求前提下,有助于我们简化实现。...在我历史经验中,我一共写过三种双向链表。 在最开始实现时,就是按算法导论最朴素实现。...最近在Review几年前代码时,发现之前使用算法1写双向链表有bug. 这再次使我想对双向链表算法2进行改进,我仔细思考了一下双向链表特性。...双向链表主要有两个功能: 提供反向遍历 以O(1)时间复杂度删除某个节点 但是到目前为止, 我从来没有使用过双向链表特性1. 我使用双向链表惟一原因就是要快速删除某一个节点。...最终我发现,在整个逻辑中,prev指针惟一用处就是用来访问或修改前置节点next变量。 而headprev变量同样是多余

    51620
    领券