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));
}
复制代码
本文转自博客园xingoo的博客,原文链接:20120918-双向链表类定义《数据结构与算法分析》,如需转载请自行联系原博主。
相关文章
|
3月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
10天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
26 4
|
2月前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
21天前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
23天前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
90 1
|
11天前
|
人工智能 算法 前端开发
无界批发零售定义及无界AI算法,打破传统壁垒,累积数据流量
“无界批发与零售”是一种结合了批发与零售的商业模式,通过后端逻辑、数据库设计和前端用户界面实现。该模式支持用户注册、登录、商品管理、订单处理、批发与零售功能,并根据用户行为计算信用等级,确保交易安全与高效。
|
17天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
21天前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
3月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
29 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法