学习总结第二十九天——双向链表的C++实现

由于每日总结实在断更得厉害，改为不定期（几天）的总结。

---

这段时间继续刷算法，并且尝试用我并不熟悉的C去实现一些数据结构，一举两得。算法方面，一直还在基本数据结构的基础上停留，不过通过运用C模板类的编辑，可以在加深这些结构的印象的时候又学会了C类的使用。中途不停犯错不停查，收获良多。双向链表可以双向遍历，相比单向链表要方便很多，下面是使用C模板实现双向链表的类：

template <typename T> struct DoubleNode
{
public:
  T data;
  DoubleNode<T> *prev = nullptr;
  DoubleNode<T> *next = nullptr;
};

template <typename T> class LinkedList
{
private:
  DoubleNode<T> *head_node = nullptr;
  DoubleNode<T> *end_node = nullptr;
public:
  void insert_begin(T insert_data);
  void insert_end(T insert_data);
  void delete_begin();
  void delete_end();
  void insert_node_before(T insert_data, int index);
  void insert_node_after(T insert_data, int index);
  void delete_node(int index);
  T & operator[] (int index);
  ~LinkedList ();
};

template <typename T>void LinkedList<T>::insert_begin(T insert_data)
{
  DoubleNode<T> *new_node = new DoubleNode<T>();
  new_node->data = insert_data;
  new_node->next = this->head_node;
  this->head_node = new_node;
  if (this->end_node == nullptr)
  {
    this->end_node = new_node;
  }
}

template <typename T>void LinkedList<T>::insert_end(T insert_data)
{
  DoubleNode<T> *new_node = new DoubleNode<T>();
  new_node->data = insert_data;
  if (this->head_node==nullptr)
  {
    this->head_node = new_node;
  }
  else
  {
    DoubleNode<T> *in_node = this->head_node;
    while (in_node->next != nullptr)
    {
      in_node = in_node->next;
    }
    in_node->next =new_node;
    in_node->next->prev =new_node;
  }
  this->end_node = new_node;
}

template <typename T>void LinkedList<T>::delete_begin()
{
  if (this->head_node == nullptr)
  {
    return;
  }
  DoubleNode<T> *del_node = this->head_node;
  this->head_node = del_node->next;
  delete del_node;
}

template <typename T>void LinkedList<T>::insert_node_before(T insert_data, int index)
{
  DoubleNode<T> *in_node=this->head_node;
  DoubleNode<T> *new_node = new DoubleNode<T>();
  new_node->data = insert_data;
  if(this->head_node == nullptr && index == 0)
  {
    this->head_node = new_node;
    this->end_node = new_node;
    return;
  }
  for (int i = 1;i<index;i++)
  {
    if (in_node == nullptr)
    {
      return;
    }
    in_node = in_node->next;
  }
  new_node->prev = in_node;
  new_node->next = in_node->next;
  in_node->next->prev = new_node;
  in_node->next = new_node;
}

template <typename T> T& LinkedList<T>::operator[] (int index)
{
  DoubleNode<T> *get_node = this->head_node;
  //if (get_node == nullptr)
  //  return ;
  for (int i=0;i < index ;i++)
  {
    get_node = get_node->next;
  //  if (get_node == nullptr)
  //  {
  //    return;
  //  }
  }
  return get_node->data;
}

template <typename T>void LinkedList<T>::insert_node_after(T insert_data, int index)
{
  DoubleNode<T> *in_node = this->head_node;
  DoubleNode<T> *new_node = new DoubleNode<T>();
  new_node->data = insert_data;
  for (int i = 0;i<index;i++)
  {
    if (in_node == nullptr)
    {
      return;
    }
    in_node = in_node->next;
  }
  new_node->prev = in_node;
  new_node->next = in_node->next;
  in_node->next = new_node;
  if (new_node->next == nullptr)
  {
    this->end_node = new_node;
  }
}

template <typename T>void LinkedList<T>::delete_node(int index)
{
  DoubleNode<T> del_node = this->head_node;
  if (del_node == nullptr)
  {
    return;
  }
  for (int i = 0;i < index;i++)
  {
    del_node = del_node->next;
    if (del_node == nullptr)
    {
      return;
    }
  }
  if (del_node->prev == nullptr)
  {
    this->head_node = del_node->next;
  }
  if (del_node->next == nullptr)
  {
    this->end_node = del_node->prev;
  }
  del_node->prev->next = del_node->next;
  del_node->next->prev = del_node->prev;
  delete del_node;
}

template <typename T> LinkedList<T>::~LinkedList ()
{
  DoubleNode<T> *now_head = this->head_node;
  DoubleNode<T> *del_node = now_head;
  while (del_node != nullptr) {
    now_head = now_head->next;
    delete del_node;
    del_node = now_head;
  }
}

这个链表实现了前插后插，前删后删等功能。下次任务：实现一个随机背包