单链表的另一个缺陷
单向性
- 只能从头结点开始高效访问链表中的数据元素
缺陷
- 如果需要逆序访问单链表中的数据元素将及其低效
int main()
{
LinkList<int> i;
for (int i=0; i<5; ++i) // O(n)
{
l.insert(0, i);
}
for (int i=length()-1; i>=0; --i)
{
cout << l.get(i) << endl;
}
return 0;
}
双向链表
设计思路
在 “单链表” 的结点中增加一个指针 pre，用于指向当前结点的前驱结点。
双向链表的继承层次结构
LinkList 的定义
template <typename T>
class DualLinkList : public List<T>
{
protected:
struct Node : public Object
{
T value;
Node *next;
Node *pte;
};
mutable struct : public Object
{
char reserved[sizeof(T)];
Node *next;
Node *pre;
}m_header;
};
编程实验：双向链表的实现
文件：DualLinkList.h
#ifndef DUALLINKLIST_H
#define DUALLINKLIST_H
#include "List.h"
#include "Exception.h"
namespace DTLib
{
template <typename T>
class DualLinkList : public List<T>
{
public:
DualLinkList()
{
m_header.next = nullptr;
m_header.pre = nullptr;
m_length = 0;
m_step = 1;
m_current = nullptr;
}
bool insert(const T &e) override // O(n)
{
return insert(m_length, e);
}
bool insert(int i, const T &e) override // O(n)
{
bool ret = ((0 <= i) && (i <= m_length));
if (ret)
{
Node *node = create();
if (node != nullptr)
{
Node *current = position(i);
Node *next = current->next;
node->value = e;
node->next = next;
current->next = node;
if (current != reinterpret_cast<Node*>(&m_header))
{
node->pre = current;
}
else
{
node->pre = nullptr;
}
if (next != nullptr)
{
next->pre = node;
}
++m_length;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
}
}
return ret;
}
bool remove(int i) override // O(n)
{
bool ret = ((0 <= i) && (i < m_length));
if (ret)
{
Node *current = position(i);
Node *toDel = current->next;
Node *next = toDel->next;
if (m_current == toDel)
{
m_current = toDel->next;
}
current->next = toDel->next;
if (next != nullptr)
{
next->pre = current;
}
--m_length;
destroy(toDel);
}
return ret;
}
bool set(int i, const T &e) override // O(n)
{
bool ret = ((0 <= i) && (i < m_length));
if (ret)
{
position(i)->next->value = e;
}
return ret;
}
virtual T get(int i) const // O(n)
{
T ret;
if (!get(i, ret))
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
}
return ret;
}
bool get(int i, T &e) const override // O(n)
{
bool ret = ((0 <= i) && (i < m_length));
if (ret)
{
e = position(i)->next->value;
}
return ret;
}
int find(const T &e) override // O(n)
{
int ret = -1;
int i = 0;
Node *node = m_header.next;
while (node)
{
if (node->value == e)
{
ret = i;
break;
}
else
{
node = node->next;
++i;
}
}
return ret;
}
int length() const override // O(1)
{
return m_length;
}
void clear() override // O(n)
{
while (m_length > 0)
{
remove(0);
}
m_current = nullptr;
}
virtual bool move(int i, int step = 1) // O(n)
{
bool ret = ((0 <= i) && (i < m_length) && (step > 0));
if (ret)
{
m_current = position(i)->next;
m_step = step;
}
return ret;
}
virtual bool end() // O(1)
{
return (m_current == nullptr);
}
virtual T current() // O(1)
{
if (!end())
{
return m_current->value;
}
else
{
THROW_EXCEPTION(InvalidOpertionExcetion, " No value at current posotion ...");
}
}
virtual bool next() // O(n)
{
int i = 0;
while ((i < m_step) && !end())
{
m_current = m_current->next;
++i;
}
return (i == m_step);
}
virtual bool pre()
{
int i = 0;
while ((i < m_step) && !end())
{
m_current = m_current->pre;
++i;
}
return (i == m_step);
}
~DualLinkList() // O(n)
{
clear();
}
protected:
struct Node : public Object
{
T value;
Node *next;
Node *pre;
};
mutable struct : public Object
{
char reserved[sizeof (T)];
Node *next;
Node *pre;
}m_header;
int m_length;
int m_step;
Node *m_current;
Node *position(int i) const // O(n)
{
Node *ret = reinterpret_cast<Node*>(&m_header);
for (int p=0; p<i; ++p)
{
ret = ret->next;
}
return ret;
}
virtual Node *create() // N(1)
{
return new Node();
}
virtual void destroy(Node *pn) // N(1)
{
delete pn;
}
};
}
#endif // DUALLINKLIST_H
文件：main.cpp
#include <iostream>
#include "DualLinkList.h"
using namespace std;
using namespace DTLib;
int main()
{
DualLinkList<int> dl;
for (int i=0; i<5; ++i)
{
dl.insert(0, i);
dl.insert(0, 5);
}
for (int i=0; i<dl.length(); ++i)
{
cout << dl.get(i) << endl;
}
cout << "--------------" << endl;
dl.move(dl.length()-1);
while (!dl.end())
{
if (dl.current() == 5)
{
cout << dl.current() << endl;
dl.remove(dl.find(dl.current()));
}
else
{
dl.pre();
}
}
cout << "--------------" << endl;
for (dl.move(0); !dl.end(); dl.next())
{
cout << dl.current() << endl;
}
return 0;
}
输出：
5 4 5 3 5 2 5 1 5 0 -------------- 5 5 5 5 5 -------------- 4 3 2 1 0
小结
- 双向链表是为了弥补单链表的缺陷而重新设计的
- 在概念上，双向链表不是单链表，没有继承关系
- 双向链表中的游标能够直接访问当前结点的前驱和后继
- 双向链表是线性表概念的最终实现（更接近理论上的线性表）
以上内容整理于狄泰软件学院系列课程，请大家保护原创！
课后练习
文件：DualStaticLinkList.h
#ifndef DUALSTATICLINKLIST_H
#define DUALSTATICLINKLIST_H
#include "DualLinkList.h"
#include <cstdlib>
namespace DTLib
{
template <typename T, int N>
class DualStaticLinkList : public DualLinkList<T>
{
public:
DualStaticLinkList() // O(n)
{
for (int i=0; i<N; ++i)
{
m_used[i] = 0;
}
}
int capacity() // O(1)
{
return N;
}
~DualStaticLinkList() // O(n)
{
this->clear();
}
protected:
using Node = typename DualLinkList<T>::Node;
struct SNode : public Node
{
void *operator new(unsigned int size, void *loc) // O(1)
{
(void)size;
return loc;
}
};
unsigned char m_space[sizeof(SNode) * N];
char m_used[N];
Node *create() // O(n)
{
SNode *ret = nullptr;
for (int i=0; i<N; ++i)
{
if (m_used[i] == 0)
{
ret = reinterpret_cast<SNode*>(m_space) + i;
ret = new(ret)SNode;
m_used[i] = 1;
break;
}
}
return ret;
}
void destroy(Node *pn) // O(n)
{
SNode *space = reinterpret_cast<SNode*>(m_space);
SNode *psn = dynamic_cast<SNode*>(pn);
for (int i=0; i<N; ++i)
{
if (psn == (space + i))
{
m_used[i] = 0;
psn->~Node();
break;
}
}
}
};
}
#endif // DUALSTATICLINKLIST_H
文件：DualCircleList.h
#ifndef DUALCIRCLELIST_H
#define DUALCIRCLELIST_H
#include "DualLinkList.h"
namespace DTLib
{
template <typename T>
class DualCircleList : public DualLinkList<T>
{
public:
bool insert(const T &e) override // O(n)
{
return insert(this->m_length, e);
}
bool insert(int i, const T &e) override // O(n)
{
bool ret = true;
i = i % (this->m_length + 1);
ret = DualLinkList<T>::insert(i, e);
if (ret && (i == 0))
{
last_to_first();
}
return ret;
}
bool remove(int i) override // O(n)
{
bool ret = true;
i = mod(i);
if (i == 0)
{
Node *toDel = this->m_header.next;
if (toDel != nullptr)
{
this->m_header.next = toDel->next;
--this->m_length;
if (this->length() > 0)
{
last_to_first();
if (this->m_current == toDel)
{
this->m_current = this->m_current->next;
}
}
else
{
this->m_header.next = nullptr;
this->m_current = nullptr;
}
this->destroy(toDel);
}
else
{
ret = false;
}
}
else
{
ret = DualLinkList<T>::remove(i);
}
return ret;
}
bool set(int i, const T &e) override // O(n)
{
return DualLinkList<T>::set(mod(i), e);
}
T get(int i) const override // O(n)
{
return DualLinkList<T>::get(mod(i));
}
bool get(int i, T &e) const override // O(n)
{
return DualLinkList<T>::get(mod(i), e);
}
int find(const T &e) const // O(n)
{
int ret = -1;
Node *slider = this->m_header.next;
for (int i=0; i<this->m_length; ++i)
{
if (slider->value == e)
{
ret = i;
break;
}
slider = slider->next;
}
return ret;
}
void clear() override // O(n)
{
while (this->m_length > 1)
{
remove(1); // 注意：为了效率，没有调用 remove(0)！
}
if(this->m_length == 1)
{
Node *toDel = this->m_header.next;
this->m_header.next = nullptr;
this->m_current = nullptr;
this->m_length = 0;
this->destroy(toDel);
}
}
bool move(int i, int step = 1)
{
return DualLinkList<T>::move(mod(i), step);
}
bool end() // O(n)
{
return ((this->m_length == 0) || (this->m_current == nullptr));
}
~DualCircleList() // O(n)
{
clear();
}
protected:
using Node = typename DualLinkList<T>::Node;
Node *last() const // O(n)
{
return this->position(this->m_length - 1)->next;
}
void last_to_first() const // O(n)
{
Node *pfirst = this->m_header.next;
Node *plast = this->last();
n
plast->next = pfirst;
pfirst->pre =plast;
}
int mod(int i) const // O(1)
{
return (this->m_length == 0) ? 0 : (i % this->m_length);
}
};
}
#endif // DUALCIRCLELIST_H
文件：main.cpp
#include <iostream>
#include "DualCircleList.h"
using namespace std;
using namespace DTLib;
int main()
{
DualCircleList<int> dl;
for (int i=0; i<5; ++i)
{
dl.insert(0, i);
dl.insert(0, 5);
}
for (int i=0; i<dl.length(); ++i)
{
cout << dl.get(i) << endl;
}
cout << "--------------" << endl;
dl.move(dl.length()-1);
for (int i=0; i<dl.length(); ++i)
{
if (dl.current() == 5)
{
cout << dl.current() << endl;
dl.remove(dl.find(dl.current()));
}
else
{
dl.pre();
}
}
cout << "--------------" << endl;
dl.move(0);
for (int i=0; i<dl.length(); ++i)
{
cout << dl.current() << endl;
dl.next();
}
return 0;
}
输出：
5 4 5 3 5 2 5 1 5 0 -------------- 5 5 5 5 5 -------------- 4 3 2 1 0
原文地址：https://segmentfault.com/a/1190000021597636
