数据结构之列表：双向链表的实现

马谦马谦马谦

615
文章

17
评论

2018年3月25日16:57:24数据结构和算法评论297字数 433阅读1分26秒阅读模式

双向链表是链表的一个分支，相比单向链表来说多了个一个前向指针pre，指向当前节点的前一个节点，查找起来更为灵活。

二、链表节点实现

双向链表的节点可以继承单向链表的节点，添加一个pre成员即可。两者声明和实现方式都差不多：

template <typename T>
class CDoubleList;

template <typename T>
class CListNode {
public:
    CListNode() :
        pre(0), next(0), list(0) {}
    CListNode(T data, CDoubleList<T>* list = 0, CListNode<T>* pre = 0, CListNode<T>* next = 0) :
        data(data), list(list), pre(pre), next(next) {}
    ~CListNode() {
        // if (next) delete next;
        pre = 0;
        next = 0;
        list = 0;
    };

    CListNode<T> * getPre() const { return pre; }
    void setPre(CListNode<T> * val) { pre = val; }
    CListNode<T> * getNext() const { return next; }
    void setNext(CListNode<T> * val) { next = val; }
    CDoubleList<T>* getList() const { return list; }
    void setList(CDoubleList<T>* val) { list = val; }
    T getData() const { return data; }
    void setData(T val) { data = val; }
private:
    T data;
    CListNode<T> * pre;
    CListNode<T> * next;
    CDoubleList<T>* list;
};

template <typename T>

class CDoubleList;

template <typename T>

class CListNode {

public:

CListNode() :

pre(0), next(0), list(0) {}

CListNode(T data, CDoubleList<T>* list = 0, CListNode<T>* pre = 0, CListNode<T>* next = 0) :

data(data), list(list), pre(pre), next(next) {}

~CListNode() {

// if (next) delete next;

pre = 0;

next = 0;

list = 0;

};

CListNode<T> * getPre() const { return pre; }

void setPre(CListNode<T> * val) { pre = val; }

CListNode<T> * getNext() const { return next; }

void setNext(CListNode<T> * val) { next = val; }

CDoubleList<T>* getList() const { return list; }

void setList(CDoubleList<T>* val) { list = val; }

T getData() const { return data; }

void setData(T val) { data = val; }

private:

T data;

CListNode<T> * pre;

CListNode<T> * next;

CDoubleList<T>* list;

};

二、链表实现

2.1 类声明

双向链表和单链表非常相似，因此没有添加很多操作函数。

在单项链表中，root节点用来指向第一个节点的地址，在双向链表中依旧可以这么使用，同时还可以使用root.pre表示最后一个节点。

#pragma once
#include "CListNode.h"
#include <vector>

typedef unsigned int uint;

template <typename T>
class CDoubleList
{
public:
    CDoubleList();
    ~CDoubleList();

    CListNode<T>* push_back(T data);
    CListNode<T>* insertAtHead(T data);
    CListNode<T>* insertAtPre(CListNode<T>* node, T data);
    CListNode<T>* insertAtSucc(CListNode<T>* node, T data);
    bool remove(CListNode<T>* node);
    bool isExist(CListNode<T>* node);
    uint size() const;

    // 遍历
    std::vector<T> traversal() const;
private:
    CListNode<T>* insert(CListNode<T>* node, T data);
    // root和tail的next指针分别指向
    // 第一个节点和最后一个节点
    CListNode<T> root;
    uint len;
};

#pragma once

#include "CListNode.h"

#include <vector>

typedef unsigned int uint;

template <typename T>

class CDoubleList

{

public:

CDoubleList();

~CDoubleList();

CListNode<T>* push_back(T data);

CListNode<T>* insertAtHead(T data);

CListNode<T>* insertAtPre(CListNode<T>* node, T data);

CListNode<T>* insertAtSucc(CListNode<T>* node, T data);

bool remove(CListNode<T>* node);

bool isExist(CListNode<T>* node);

uint size() const;

// 遍历

std::vector<T> traversal() const;

private:

CListNode<T>* insert(CListNode<T>* node, T data);

// root和tail的next指针分别指向

// 第一个节点和最后一个节点

CListNode<T> root;

uint len;

};

2.2 构造和析构

// 初始化时，`root.pre`和`root.next`都指向空
template <typename T>
CDoubleList<T>::CDoubleList()
{
    len = 0;
    root.setList(this);
}

// 析构时删除所有的节点
template <typename T>
CDoubleList<T>::~CDoubleList()
{
    CListNode<T>* p = root.getNext(), *q;
    while (p) {
        q = p->getNext();
        delete p;
        p = q;
    }
    root.setNext(0);
    root.setPre(0);
    len = 0;
}

// 初始化时，`root.pre`和`root.next`都指向空

template <typename T>

CDoubleList<T>::CDoubleList()

{

len = 0;

root.setList(this);

}

// 析构时删除所有的节点

template <typename T>

CDoubleList<T>::~CDoubleList()

{

CListNode<T>* p = root.getNext(), *q;

while (p) {

q = p->getNext();

delete p;

p = q;

}

root.setNext(0);

root.setPre(0);

len = 0;

}

2.3 插入节点

// 在节点后插入
template<typename T>
inline CListNode<T>* CDoubleList<T>::insert(CListNode<T>* node, T data)
{
    if (!isExist(node)) return 0;
    // 创建新节点插入到指定节点后
    CListNode<T> *pNode = new CListNode<T>(data, this, node, node->getNext());
    if (!pNode->getNext())
        // 如果是在最后插入，更新尾节点
        root.setPre(pNode);
    else
        // 不是链表结尾插入，更新下一个节点的pre指针
        node->getNext()->setPre(pNode);

    node->setNext(pNode);
    len++;
    return pNode;
}

// 插入到末尾
template<typename T>
inline CListNode<T>* CDoubleList<T>::push_back(T data)
{
    // 插在尾节点之后
    return insertAtSucc(root.getPre() == 0 ? &root : root.getPre(), data);
}

// 插在链表开头
template<typename T>
inline CListNode<T>* CDoubleList<T>::insertAtHead(T data)
{
    return insert(&root, data);
}

// 作为前驱结点插入
template<typename T>
inline CListNode<T>* CDoubleList<T>::insertAtPre(CListNode<T>* node, T data)
{
    if (!isExist(node)) return 0;
    return insert(node->getPre(), data);
}

// 作为后继节点插入
template<typename T>
inline CListNode<T>* CDoubleList<T>::insertAtSucc(CListNode<T>* node, T data)
{
    return insert(node, data);
}

// 在节点后插入

template<typename T>

inline CListNode<T>* CDoubleList<T>::insert(CListNode<T>* node, T data)

{

if (!isExist(node)) return 0;

// 创建新节点插入到指定节点后

CListNode<T> *pNode = new CListNode<T>(data, this, node, node->getNext());

if (!pNode->getNext())

// 如果是在最后插入，更新尾节点

root.setPre(pNode);

else

// 不是链表结尾插入，更新下一个节点的pre指针

node->getNext()->setPre(pNode);

node->setNext(pNode);

len++;

return pNode;

}

// 插入到末尾

template<typename T>

inline CListNode<T>* CDoubleList<T>::push_back(T data)

{

// 插在尾节点之后

return insertAtSucc(root.getPre() == 0 ? &root : root.getPre(), data);

}

// 插在链表开头

template<typename T>

inline CListNode<T>* CDoubleList<T>::insertAtHead(T data)

{

return insert(&root, data);

}

// 作为前驱结点插入

template<typename T>

inline CListNode<T>* CDoubleList<T>::insertAtPre(CListNode<T>* node, T data)

{

if (!isExist(node)) return 0;

return insert(node->getPre(), data);

}

// 作为后继节点插入

template<typename T>

inline CListNode<T>* CDoubleList<T>::insertAtSucc(CListNode<T>* node, T data)

{

return insert(node, data);

}

2.5 删除节点

// 移除节点
template<typename T>
inline bool CDoubleList<T>::remove(CListNode<T>* node)
{
    if (!isExist(node))
        return false;

    // 更新前驱节点的next指针
    node->getPre()->setNext(node->getNext());
    if (node->getNext())
        // 判断是不是最后一个节点
        // 不是最后一个节点要更新下一个节点的前驱
        node->getNext()->setPre(node->getPre());
    else
        // 如果是最后一个节点，要更新尾节点的指针
        root.setPre(node->getPre() == &root ? 0 : node->getPre());
    delete node;
    len--;

    return true;
}

// 移除节点

template<typename T>

inline bool CDoubleList<T>::remove(CListNode<T>* node)

{

if (!isExist(node))

return false;

// 更新前驱节点的next指针

node->getPre()->setNext(node->getNext());

if (node->getNext())

// 判断是不是最后一个节点

// 不是最后一个节点要更新下一个节点的前驱

node->getNext()->setPre(node->getPre());

else

// 如果是最后一个节点，要更新尾节点的指针

root.setPre(node->getPre() == &root ? 0 : node->getPre());

delete node;

len--;

return true;

}

2.6 其他操作

// 节点是否存在
template<typename T>
inline bool CDoubleList<T>::isExist(CListNode<T>* node)
{
    return this == node->getList();
}

template<typename T>
inline uint CDoubleList<T>::size() const
{
    return len;
}

// 遍历链表
template <typename T>
inline std::vector<T> CDoubleList<T>::traversal() const
{
    std::vector<T> v;
    CListNode<T>*p = root.getNext();
    while (p) {
        v.push_back(p->getData());
        p = p->getNext();
    }

    return v;
}