双向链表

双向链表(double linked list)目的是为了解决在链表中访问直接前驱和直接后继的问题。一个直接前驱一个直接后继，向前后搜索的开销都是O(1)

#ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H

#include"linearList.h"
#include<stdlib.h>
template<class T>
class DblNode{
public:
    T data;
    DblNode<T> *lLink,*rLink;
    DblNode(DblNode<T> *left = NULL,DblNode<T> *right=NULL)
        :lLink(left),rLink(right){}
    DblNode(T value,DblNode<T> *left = NULL,DblNode<T>* right=NULL)
        :data(value),lLink(left),rLink(right){}
};

template<typename T>
class DblList{
public:
    DblList(T uniqueVal);
    ~DblList();
    int Size()const;
    int Length()const;
    int Search(T& x)const;
    bool getData(int i,T& x)const;
    void setData(int i,T& x);
    bool IsEmpty(){return first->rLink==first;}
    bool IsFull()const;
    void Sort();
    void input();
    void output();
    DblNode<T> *getHead()const{return first;}
    void setHead(DblNode<T> *ptr);
    DblNode<T> *Search(const T& x);
    DblNode<T> *Locate(int i,int d=1);
    bool Insert(int i, T &x,int d=1);
    bool Remove(int i, T &x,int d=1);
    void push_back(T& x);
private:
    DblNode<T> *first;
};


#endif // DOUBLELINKEDLIST_H

#include"DoubleLinkedList.h"
#include<iostream>

using namespace std;

template<typename T>
DblList<T>::DblList(T uniqueVal){
    first = new DblNode<T>(uniqueVal);
    if(first==NULL){
        cerr << "Memory allocation error" << endl;
        exit(1);
    }
    first->rLink=first->lLink=first;
}

template<typename T>
DblList<T>::~DblList<T>()
{

}

template<class T>
int DblList<T>::Size() const
{
    return Length();
}

template<class T>
int DblList<T>::Length() const
{
    DblNode<T> *current = first->rLink;
    int count = 0;
    while(current != first){
        current = current->rLink;
        count++;
        return count;
    }
}

template<class T>
DblNode<T> *DblList<T>::Search(const T &x)
{
    DblNode<T> *current = first->rLink;
    while(current!=first&&current->data!=x)
        current = current->rLink;
    if(current!=first)
        return current;
    else
        return NULL;
}

/*
  d是方向，0反向，1正向
*/
template<class T>
DblNode<T> *DblList<T>::Locate(int i, int d)
{
    if(first->rLink == first || i==0)
        return first;
    DblNode<T> *current;
    if(d==0)
        current = first->lLink;
    else
        current = first->rLink;
    for(int j=1;j<i;j++)
        if(current == first)
            break;
        else if(d==0)
            current = current->lLink;
        else
            current = current->rLink;
    if(current!=first)
        return current;
    else
        return NULL;
}

template<class T>
bool DblList<T>::Insert(int i, T &x, int d)
{
    DblNode<T> *node = Locate(i,d);
    if(node==NULL)
        return false;
    DblNode<T> *newNode = new DblNode<T>(x);
    if(NULL==newNode){
        cerr << "Memory allocation error" << endl;
        exit(0);
    }
    if(d==1){
        newNode->rLink = node->rLink;
        node->rLink = newNode;
        newNode->rLink->lLink = newNode;
        newNode->lLink = node;
    }else{
        newNode->lLink = node->lLink;
        node->lLink = newNode;
        newNode->lLink->rLink = node;
        newNode->rLink = node;
    }
    return true;
}

template<typename T>
bool DblList<T>::Remove(int i, T &x, int d)
{
    DblNode<T> *node = Locate(i,d);
    if(node==NULL)
        return false;
    node->lLink->rLink = node->rLink;
    node->rLink->lLink = node->lLink;
    delete node;
    return true;
}

template<typename T>
void DblList<T>::push_back(T& x)
{
    DblNode<T> *node = Locate(0);
    while(node->rLink!=first){
        node = node->rLink;
    }
    DblNode<T> *newNode = new DblNode<T>(x);
    node->rLink = newNode;
    newNode->lLink = node;
    newNode->rLink = first;
}

template<typename T>
void DblList<T>::output()
{
    DblNode<int>* node = Locate(0);
    while(node->rLink!=first){
        cout << node->data << " ";
        node = node->rLink;
    }
    cout << node->data << " ";
}

int main()
{
    DblList<int> lst(1);
    const int size = 8;
    for(int i=2;i<=size;++i){
        lst.push_back(i);
    }
    lst.output();
    cout << endl;
    int m = 3,num=0;
    DblNode<int>* node = lst.getHead();
    DblNode<int>* pre = NULL;
    for(int i=0;i<size-1;++i){
        for(int j=1;j<m;++j){
            pre = node;
            node = node->rLink;
        }
        pre->rLink = node->rLink;
        delete node;
        node = pre->rLink;
    }
    cout << node->data;
}

1 2 3 4 5 6 7 8 
7