双链表结点及部分操作(C++描述)

待我称王封你为后i 2022-08-22 13:25 114阅读 0赞

双链表结构定义：

#ifndef DOUBLY_LINKED
    #define DOUBLY_LINKED
    
    //支持freelist的双链表结点定义
    template <typename E>
    class Link{
    private:
        static Link<E>* freelist;   //指向freelist头
    
    public:
        E element;
        Link* next;
        Link* prev;
    
        //构造函数
        Link(const E& it, Link* prevp, Link* nextp){
            element = it;
            prev = prevp;
            next = nextp;
        }
    
        Link(Link* prevp = NULL, Link* nextp = NULL){
            prev = prevp;
            next = nextp;
        }
    
        //重载new运算符
        void* operator new(size_t){
            if (freelist == NULL)
                return ::new Link;
            Link<E>* temp = freelist;
            freelist = freelist->next;
            return temp;
        }
    
        //重载delete运算符
        void operator delete(void* ptr){
            ((Link<E>*)ptr)->next = freelist;       //put on freelist
            freelist = (Link<E>*)ptr;
        }
    };
    
    //freelist头指针类外创建
    template <typename E>
    Link<E>* Link<E>::freelist = NULL;
    
    #endif

--------------------

部分操作  
本例curr被定义为当前结点的上一个结点(为了链表插入删除等操作简便)  
即curr->next为当前结点

//当前位置插入it
    void insert(const E& it){
        curr->next = curr->next->prev = 
            new Link<E>(it, curr, curr->next);
        cnt++;
    }
    
    //末尾添加添加一个元素it
    void append(const E& it){
        tail->prev = tail->prev->next =
            new Link<E>(it, tail->prev, tail);
        cnt++;
    }
    
    //删除并返回当前元素
    E remove(){
        if (curr->next == tail)
            return NULL;
        E it = curr->next->element;
        Link<E>* ltemp = curr->next;
        curr->next->next->prev = curr;
        delete ltemp;
        cnt--;
        return it;
    }
    
    //移动至前一个元素
    void prev(){
        if (curr != head)
            curr = curr->prev;
    }

--------------------

双链表和单链表相比唯一的缺点就是使用更多的空间，因为双链表每一个结点需要两个指针。