gt;);
}
删除节点：
1. 查找待删除节点
2. 断开其prev和next指针
然后delete掉tmp_ptr指针，此处用的智能指针，当离开该作用域后，2号节点的引用计数为0，会自动释放2号节点的空间
template<typename T>
inline void LinearList<T>::delete_node(int64_t index, T & data)
{
if (index < 0 || index > _length)
{
index = _length;
}
std::shared_ptr<Node<T>> tmp_ptr;
delete_node_ptr(index, tmp_ptr);
data = tmp_ptr->data();
}
template<typename T>
inline void LinearList<T>::delete_node_ptr(int64_t index, std::shared_ptr<Node<T>>& data)
{
_ASSERTE(!(index < 0 || index > _length));
std::shared_ptr<Node<T>> tmp_ptr(_head->next());
// 查找待删除节点
for (int64_t i = 0; i < index; ++i)
{
tmp_ptr = tmp_ptr->next();
}
tmp_ptr->prev() == nullptr ? nullptr : tmp_ptr->prev()->set_next(tmp_ptr->next());
tmp_ptr->next() == nullptr ? nullptr : tmp_ptr->next()->set_prev(tmp_ptr->prev());
data = tmp_ptr;
--_length;
_size -= sizeof(Node<T>);
_current = _head;
_current_index = 0;
}
查看某个节点：
此处为了降低遍历时的时间复杂度，故添加了一个游标指针以及游标下标，用于指向刚访问过的节点，故在遍历时不用每次都从头结点遍历到尾节点。
inline T LinearList<T>::get_element(int64_t index)
{
std::shared_ptr<Node<T>> result_ptr = get_ptr(index);
if (!result_ptr)
{
throw new std::exception("could not found.");
}
return result_ptr->data();
}
template<typename T>
inline std::shared_ptr<Node<T>> LinearList<T>::get_ptr(int64_t index)
{
_ASSERTE(!(index < 0 || index > _length - 1));
int64_t max_index = _length - 1;
int64_t min_index = 0;
int64_t low_index = 0;
int64_t high_index = max_index;
low_index = index >= _current_index ? _current_index : min_index;
high_index = index >= _current_index ? max_index : _current_index;
if ((index - low_index) <= (high_index - index)) // 正向遍历
{
_current = low_index == min_index ? _head->next() : _current;
_current_index = low_index == min_index ? min_index : _current_index;
while (_current && index != _current_index)
{
_current = _current->next();
++_current_index;
}
}
else // 逆向遍历
{
_current = high_index == max_index ? _tail : _current;
_current_index = high_index == max_index ? max_index : _current_index;
while (_current && index != _current_index)
{
_current = _current->prev();
--_current_index;
}
}
return _current;
}
主函数：
int main() {
LinearList<int> linear_list;
for (int64_t i = 0; i < 10; i++)
{
linear_list.insert_node(i, i);
}
std::cout << "逆向遍历节点：" << std::endl;
for (int64_t i = linear_list.length() - 1; i >= 0; --i)
{
std::cout << linear_list.get_element(i) << " ";
}
std::cout << std::endl << std::endl;
std::cout << "正向遍历节点：" << std::endl;
for (int64_t i = 0; i < linear_list.length(); ++i) {
std::cout << linear_list.get_element(i) << " ";
}
std::cout << std::endl << std::endl;
std::cout << "删除第2个节点： " << std::endl;
int data;
linear_list.delete_node(2, data);
std::cout << data << std::endl << std::endl;
std::cout << "逆向遍历节点：" << st