数据结构（七）——双向链表

数据结构（七）——双向链表

一、双向链表简介

1、单链表的缺陷

单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。

创新互联公司自2013年创立以来，是专业互联网技术服务公司，拥有项目成都网站制作、成都网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元罗湖做网站,已为上家服务,为罗湖各地企业和个人服务,联系电话:13518219792

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;
    }
  };