双线链表

双向链表的特点：
1、以节点为单位，每个节点有上个节点指针和下个节点指针
2、至少包含头节点和尾节点
3、添加节点时先改变新增节点的上下节点指针指向，后修改前后节点的指针指向为当前节点
4、删除节点时修改当前节点的前后节点指向，然后删除当前节点
5、迭代器用来封装节点数据，并提供了操作符的能力，如*，++，==，!=
6、列表的操作有：取头，取尾，删头，删尾，删指定位置，加头，加尾，加指定位置

template
class List
{
private:

struct Node
{
    Object data;
    Node *prev;
    Node *next;

    Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
        : data(d), prev(p), next(n)
    {

    }
};

public:

class const_iterator
{
public:
    const_iterator() : current(NULL)
    {

    }

    const Object &operator* () const
    {
        return retrieve();
    }

    const_iterator & operator++ ()
    {
        current = current->next;
        return *this;
    }

    const_iterator operator++ (int)
    {
        const_iterator old = *this;
        ++(*this);
        return old;
    }

    bool operator == (const const_iterator &rhs) const
    {
        return current == rhs.current;
    }

    bool operator != (const const_iterator &rhs) const
    {
        return !(*this == rhs);
    }

protected:
    Node *current;
    Object &retrieve() const
    {
        return current->data;
    }
    const_iterator(Node *p) : current(p)
    {

    }

    friend class List < Object >;
};

class iterator : public const_iterator
{
public:
    iterator()
    {

    }

    Object & operator* ()
    {
        return retrieve();
    }

    iterator &operator++()
    {
        current = current->next;
        return *this;
    }

    iterator operator++ (int)
    {
        iterator old = *this;
        ++(*this);
        return old;
    }

protected:
    iterator(Node *p) : const_iterator(p)
    {

    }

    friend class List < Object >;
};

public:

List()
{
    init();
}
~List()
{
    clear();
    delete head;
    delete tail;
}
List(const List &rhs)
{
    init();
    *this = rhs;
}

const List &operator = (const List &rhs)
{
    if (this == &rhs)
    {
        return *this;
    }
    clear();
    for (const_iterator itr = rhs.begin(); itr != rhs.end(); ++itr)
    {
        push_back(*itr);
    }

    return *this;
}

iterator begin()
{
    return iterator(head->next);
}

const_iterator begin() const
{
    return const_iterator(head->next);
}

iterator end()
{
    return iterator(tail);
}

const_iterator end() const
{
    return const_iterator(tail);
}

int size() const
{
    return theSize;
}
bool empty() const
{
    return size() == 0;
}

void clear()
{
    while (!empty())
        pop_front();
}

Object &front()
{
    return *begin();
}

const Object & front() const
{
    return *begin();
}
Object &back()
{
    return *--end();
}
const Object &back() const
{
    return *--end();
}
void push_front(const Object &x)
{
    insert(begin(), x);
}
void push_back(const Object &x)
{
    insert(end(), x);
}
void pop_front()
{
    erase(begin());
}
void pop_back()
{
    erase(--end());
}

iterator insert(iterator itr, const Object &x)
{
    Node *p = itr.current;
    theSize++;
    return iterator(p->prev = p->prev->next = new Node(x, p->prev, p));
}
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 = start; itr != end;)
    {
        itr = erase(itr);
    }

    return end;
}

private:

int theSize;
Node *head;
Node *tail;
void init()
{
    theSize = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    tail->prev = head;
}

};

int main()
{

List<int> nList;
nList.push_back(1);
nList.push_back(2);
nList.push_back(3);
nList.push_back(4);
for (List<int>::const_iterator itr = nList.begin(); itr != nList.end(); itr++)
{
    LOG_INFO("itr vaule:" << *itr);
}

//
for (List<int>::iterator itr = nList.begin(); itr != nList.end(); )
{
    nList.erase(itr++);
}

LOG_INFO("List size:" << nList.size());
reutrn 0;

}
本