数据结构（七）——双向链表-创新互联
数据结构（七）——双向链表
一、双向链表简介
1、单链表的缺陷
单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。
2、双向链表的结构
双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
3、双向链表类的基本结构
template
class DualLinkedList:public List
{
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;
} 二、双向链表的操作
1、双向链表的插入操作
bool insert(int index, const T& value)
{
//判断目标位置是否合法
bool ret = (0 <= index) && (index <= m_length);
if(ret)
{
//创建新的结点
Node* node = createNode();
if(node != NULL)
{
//当前结点定位到目标位置
Node* current = position(index);
//当前结点的下一个结点
Node* next = current->next;
//修改插入结点的值
node->value = value;
//将当前位置的下一个结点作为插入结点的下一个结点
node->next = next;
//将要插入结点作为当前结点的下一个结点
current->next = node;
if(current != reinterpret_cast(&m_header))
{
node->pre = current;
}
else
{
node->pre = NULL;
}
if(next != NULL)
{
next->pre = node;
}
m_length++;//链表结点长度加1
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
}
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
}
return ret;
}
bool insert(const T& value)
{
return insert(m_length, value);
} 2、双向链表的删除操作
bool remove(int index)
{
//判断目标位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//当前结点指向头结点
Node* current = position(index);
//使用toDel指向要删除的结点
Node* toDel = current->next;
Node* next = toDel->next;
if(m_current == toDel)
{
m_current = next;
}
//将当前结点的下一个结点指向要删除结点的下一个结点
current->next = next;
if(next != NULL)
next->pre = current;
m_length--;//链表结点长度减1
destroy(toDel);//释放要删除的结点的堆空间
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}三、双向链表的实现
template
class DualLinkedList:public List
{
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;
protected:
Node* position(int index)const
{
//指针指向头结点
Node* ret = reinterpret_cast(&m_header);
//遍历到目标位置
for(int i = 0; i < index; i++)
{
ret = ret->next;
}
return ret;
}
public:
DualLinkedList()
{
m_header.next = NULL;
m_header.pre = NULL;
m_length = 0;
m_step = 1;
m_current = NULL;
}
virtual ~DualLinkedList()
{
clear();
}
bool insert(int index, const T& value)
{
//判断目标位置是否合法
bool ret = (0 <= index) && (index <= m_length);
if(ret)
{
//创建新的结点
Node* node = createNode();
if(node != NULL)
{
//当前结点定位到目标位置
Node* current = position(index);
//当前结点的下一个结点
Node* next = current->next;
//修改插入结点的值
node->value = value;
//将当前位置的下一个结点作为插入结点的下一个结点
node->next = next;
//将要插入结点作为当前结点的下一个结点
current->next = node;
if(current != reinterpret_cast(&m_header))
{
node->pre = current;
}
else
{
node->pre = NULL;
}
if(next != NULL)
{
next->pre = node;
}
m_length++;//链表结点长度加1
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory...");
}
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid...");
}
return ret;
}
bool insert(const T& value)
{
return insert(m_length, value);
}
bool remove(int index)
{
//判断目标位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//当前结点指向头结点
Node* current = position(index);
//使用toDel指向要删除的结点
Node* toDel = current->next;
Node* next = toDel->next;
if(m_current == toDel)
{
m_current = next;
}
//将当前结点的下一个结点指向要删除结点的下一个结点
current->next = next;
if(next != NULL)
next->pre = current;
m_length--;//链表结点长度减1
destroy(toDel);//释放要删除的结点的堆空间
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}
bool set(int index, const T& value)
{
//判断目标位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//将当前结点指向头结点
Node* current = position(index);
//修改目标结点的数据域的值
current->next->value = value;
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}
bool get(int index, T& value)const
{
//判断目标位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//当前结点指向头结点
Node* current = position(index);
//遍历到目标位置
//获取目标结点的数据域的值
value = current->next->value;
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid...");
}
return ret;
}
//重载版本
T get(int index)const
{
T ret;
if(get(index, ret))
return ret;
}
int length()const
{
return m_length;
}
int find(const T& value)const
{
int ret = -1;
//指向头结点
Node* node = m_header.next;
int i = 0;
while(node)
{
//找到元素，退出循环
if(node->value == value)
{
ret = i;
break;
}
else
{
node = node->next;
i++;
}
}
return ret;
}
void clear()
{
//遍历删除结点
while(m_header.next)
{
//要删除的结点为头结点的下一个结点
Node* toDel = m_header.next;
//将头结点的下一个结点指向删除结点的下一个结点
m_header.next = toDel->next;
m_length--;
destroy(toDel);//释放要删除结点
}
}
virtual bool move(int pos, int step = 1)
{
bool ret = (0 <= pos) && (pos < m_length) && (0 < step);
if(ret)
{
m_current = position(pos)->next;
m_step = step;
}
return ret;
}
virtual bool end()
{
return m_current == NULL;
}
virtual T current()
{
if(!end())
{
return m_current->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "Invalid Operation...");
}
}
virtual bool next()
{
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);
}
virtual Node* createNode()
{
return new Node();
}
virtual void destroy(Node* node)
{
delete node;
}
}; 另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站栏目：数据结构（七）——双向链表-创新互联
网站路径：http://hbruida.cn/article/dgsoco.html
