20120918-双向链表类定义《数据结构与算法分析》

将新的节点插入双向链表的时候:

iterator insert(iterator itr,const Object & x)//向双向链表中插入一个x节点
{
    Node *p = itr.current;
    theSize++;
    return iterator(p->prev = p->prev->next = new Node(x,p->prev,p));
}

LIST类的删除节点的过程:

//删除双向链表中的一个节点
iterator erase(iterator itr)
{
    Node *p = itr.current;
    iterator retVal(p->next);
    p->prev->next=p->next;
    p->next->prev=p->prev;
    delete p;
    theSize--;

    return retVal;
}

iterator erase(iterator start,iterator end)
{
    for(iterator itr = from;itr != to; )
        itr = erase(itr);

    return to;
}

传递给erase insert的迭代器可能没有初始化  或者  这个迭代器是错误的表达,因此需要一个检测:

protected:
    const List<Object> *theList;
    Node *current;

    const_iterator(const List<Object> & lst,Node *p):
        theList(&lst),current(p)'
        {
        }
        void assertIsValid() const
        {
            if(theList == NULL || current == NULL || current == theList->head)
                throw IteratorOutOfBoundsException();
        }

带有附加错误检测的insert类:

iterator insert(iterator itr.const Object & x)
{
    itr.assertIsValid();
    if(itr.theList !=this)
        throw IteratorMismatchException();

    Node *p = itr.current;
    theSize++;
    return iterator(*this,p->prev=p->prev->next=new Node (x,p->prev,p));
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP在线

php的字符串常用函数

1. str_word_count 统计单词个数 2. count_chars 得到字符串里面字符的有关情况 3. str_len 得到字符串长度,就是...

51360
来自专栏后端技术探索

Base64编码原理,快速掌握

Base64编码,是我们程序开发中经常使用到的编码方法。它是一种基于用64个可打印字符来表示二进制数据的表示方法。它通常用作存储、传输一些二进制数据编码方法!也...

8800
来自专栏noteless

[十一]基础数据类型之Character

该类提供了几种方法来确定字符的类别(小写字母、数字等),并将字符从大写转换为小写,反之亦然

10910
来自专栏陈树义

Oracle常用函数集锦

1、wmsys.wm_concat函数 将列转为行。例子: --表里的数据如下 SQL> select * from idtable; ID N...

37760
来自专栏Albert陈凯

Scala集合练习题

//创建一个List val list0 = List(1,7,9,8,0,3,5,4,6,2) //将list0中每个元素乘以10后生...

51090
来自专栏blackheart的专栏

[C#1] 8-数组

1.数组概述 声明数组: //每个元素初始化为0,虽然数组元素是值类型,但是却是分配在托管堆中的; int[] myArray=new int[100]; //...

20270
来自专栏Hongten

java中的移位运算符:<<,>>,>>>总结

value >>> num     --   num 指定要移位值value 移动的位数。

26050
来自专栏PHP在线

php总结

php5.3新增魔术方法__invoke在对象实例化之后,像调用变量函数一样调用。 class testClass{ function __invoke(...

35090
来自专栏JackeyGao的博客

Leetcode 算法 -4. Median of Two Sorted Arrays

解题思路: 先把列表碾平 , 由于两个列表元素类型相同直接相加即可. 然后排序. 计算中间位置, 可以通过判断奇偶数来分别处理开始index和结束index....

8830
来自专栏Jackson0714

C# 正则表达式

13120

扫码关注云+社区

领取腾讯云代金券