一、雙向連結清單簡介
1、單連結清單的缺陷
單連結清單隻能從頭結點開始通路連結清單中的資料元素,如果需要逆序通路單連結清單中的資料元素将極其低效。
2、雙向連結清單的結構
雙連結清單是連結清單的一種,由節點組成,每個資料結點中都有兩個指針,分别指向直接後繼和直接前驅。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yY4YTZwEmYjF2MzMDM5YDNzQ2MilDO5gjMmZWNzUWYz8CXxIzLcFDM4EDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLxM3Lc9CX6MHc0RHaiojIsJye.png)
3、雙向連結清單類的基本結構
template <typename T>
class DualLinkedList:public List<T>
{
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<Node*>(&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 <typename T>
class DualLinkedList:public List<T>
{
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<Node*>(&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<Node*>(&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;
}
};
轉載出處