数据结构基础(12) --双向循环链表的设计与实现 - c++编程基础

双向链表的操作特点：

(1) “查询” 和单链表相同;

(2)“插入” 和“删除”时需要同时修改两个方向上的指针。

但是对于双向循环链表则在表尾插入非常的迅速, 只需O(1)的时间,因为有指向前面的指针, 因此双向循环链表会很容易的找到位于表尾的元素,因此双向循环链表比较适用于频繁在表尾插入的情况.

空链表:

双向循环链表节点构造:

class DoubleListNode
{
private:
    Type data;
    DoubleListNode *prev;   //前向指针域
    DoubleListNode *next;   //后项指针域
};

因为需要将其用于DoubleList类,因此需要将其改造如下:

template 
  
   
class DoubleListNode
{
    //友元声明
    friend class DoubleList
   
    ; friend class ListIterator
    
     ; template 
     
       friend ostream &operator<<(ostream &os, const DoubleList
      
        &list); private: DoubleListNode(const Type &dataValue) :data(dataValue),prev(NULL),next(NULL) {} Type data; DoubleListNode *prev; //前向指针域 DoubleListNode *next; //后项指针域 };

双向循环链表构造:

template 
  
   
class DoubleList
{
    friend class ListIterator
   
    ; template 
    
      friend ostream &operator<<(ostream &os, const DoubleList
     
       &list); public: DoubleList(); ~DoubleList(); void push_back(const Type &data); void push_front(const Type &data); void insert(int position, const Type &data); void pop_front(); void pop_back(); void remove(const Type &removeData); bool search(const Type &searchData) const; bool isEmpty() const { return (first->next == first); } private: //将节点x插入到节点previous后面 void insertPrivate(DoubleListNode
      
        *previous, DoubleListNode
       
         *x); void removePrivate(DoubleListNode
        
          *x); private: DoubleListNode
         
           *first; };

链表的构造与析构:

//构造链表
template 
  
   
DoubleList
   
    ::DoubleList() { first = new DoubleListNode
    
     (0); first->next = first; first->prev = first; }

//析构链表
template 
  
   
DoubleList
   
    ::~DoubleList() { DoubleListNode
    
      *deleteNode = NULL; //保存链表尾元素 DoubleListNode
     
       *tmp = first; //first首先指向第一个真实的元素 first = first->next; //一路到达链表结尾 while (first != tmp) { deleteNode = first; first = first -> next; delete deleteNode; } // 释放掉链表的空节点(表头) delete tmp; }

链表元素插入与删除的两大主力:

//同为private成员
//插入节点
template 
  
   
void DoubleList
   
    ::insertPrivate(DoubleListNode
    
      *previous, DoubleListNode
     
       *x) { x->prev = previous; x->next = previous->next; previous->next->prev = x; previous->next = x; }

//删除节点
template 
  
   
void DoubleList
   
    ::removePrivate(DoubleListNode
    
      *x) { if (x == first) throw std::range_error("permission denied to delete first pointer"); x->prev->next = x->next; x->next->prev = x->prev; delete x; }

提供给客户的插入:

//插入到表尾
template 
  
   
void DoubleList
   
    ::push_back(const Type &data) { DoubleListNode
    
      *newNode = new DoubleListNode
     
      (data); //找到first的前一个节点 DoubleListNode
      
        *previous = first->prev; //插入 insertPrivate(previous, newNode); } //插入到表头 template 
       
         void DoubleList
        
         ::push_front(const Type &data) { DoubleListNode
         
           *newNode = new DoubleListNode
          
           (data); //插入到first之后 insertPrivate(first, newNode); } //插入到任意位置(依position指定) template 
           
             void DoubleList
            
             ::insert(int position, const Type &data) { if (position == 1) return push_front(data); int count = 1; //previous 代表着要插入位置之前的一个位置 DoubleListNode
             
               *previous = first->next; //如果position过大, 则previous查找到first就会停止 //此时应该将该元素插入到链表结尾 while (count < position-1 && previous != first) { ++ count; previous = previous->next; } //如果查找到了链表结尾或此时链表为空, 因此插入到表尾 if (previous == first) return push_back(data); //如果找到了合适的插入位置 DoubleListNode
              
                *newNode = new DoubleListNode
               
                (data); insertPrivate(previous, newNode); }

提供给客户的删除:

//删除表尾元素
template 
  
   
void DoubleList
   
    ::pop_back() { removePrivate(first->prev); } //删除表头元素 template 
    
      void DoubleList
     
      ::pop_front() { removePrivate(first->next); } //删除元素值为removeData的所有元素 template 
      
        void DoubleList
       
        ::remove(const Ty

数据结构基础(12) --双向循环链表的设计与实现(一)