c++实现双向链表

  1 #ifndef DOUBLE_LINK_HXX
  2 #define DOUBLE_LINK_HXX
  3 
  4 #include <iostream>
  5 using namespace std;
  6 
  7 template<class T> 
  8 struct DNode 
  9 {
 10     public:
 11         T value;
 12         DNode *prev;
 13         DNode *next;
 14     public:
 15         DNode() { }
 16         DNode(T t, DNode *prev, DNode *next) {
 17             this->value = t;
 18             this->prev  = prev;
 19             this->next  = next;
 20            }
 21 };
 22 
 23 template<class T> 
 24 class DoubleLink 
 25 {
 26     public:
 27         DoubleLink();
 28         ~DoubleLink();
 29 
 30         int size();
 31         int is_empty();
 32 
 33         T get(int index);
 34         T get_first();
 35         T get_last();
 36 
 37         int insert(int index, T t);
 38         int insert_first(T t);
 39         int append_last(T t);
 40 
 41         int del(int index);
 42         int delete_first();
 43         int delete_last();
 44 
 45     private:
 46         int count;
 47         DNode<T> *phead;
 48     private:
 49         DNode<T> *get_node(int index);
 50 };
 51 
 52 template<class T>
 53 DoubleLink<T>::DoubleLink() : count(0)
 54 {
 55     // 创建“表头”。注意：表头没有存储数据！
 56     phead = new DNode<T>();
 57     phead->prev = phead->next = phead;
 58     // 设置链表计数为0
 59     //count = 0;
 60 }
 61 
 62 // 析构函数
 63 template<class T>
 64 DoubleLink<T>::~DoubleLink() 
 65 {
 66     // 删除所有的节点
 67     DNode<T>* ptmp;
 68     DNode<T>* pnode = phead->next;
 69     while (pnode != phead)
 70     {
 71         ptmp = pnode;
 72         pnode=pnode->next;
 73         delete ptmp;
 74     }
 75 
 76     // 删除"表头"
 77     delete phead;
 78     phead = NULL;
 79 }
 80 
 81 // 返回节点数目
 82 template<class T>
 83 int DoubleLink<T>::size() 
 84 {
 85     return count;
 86 }
 87 
 88 // 返回链表是否为空
 89 template<class T>
 90 int DoubleLink<T>::is_empty() 
 91 {
 92     return count==0;
 93 }
 94 
 95 // 获取第index位置的节点
 96 template<class T>
 97 DNode<T>* DoubleLink<T>::get_node(int index) 
 98 {
 99     // 判断参数有效性
100     if (index<0 || index>=count)
101     {
102         cout << "get node failed! the index in out of bound!" << endl;
103         return NULL;
104     }
105 
106     // 正向查找
107     if (index <= count/2)
108     {
109         int i=0;
110         DNode<T>* pindex = phead->next;
111         while (i++ < index) {
112             pindex = pindex->next;
113         }
114 
115         return pindex;
116     }
117 
118     // 反向查找
119     int j=0;
120     int rindex = count - index -1;
121     DNode<T>* prindex = phead->prev;
122     while (j++ < rindex) {
123         prindex = prindex->prev;
124     }
125 
126     return prindex;
127 }
128 
129 // 获取第index位置的节点的值
130 template<class T>
131 T DoubleLink<T>::get(int index) 
132 {
133     return get_node(index)->value;
134 }
135 
136 // 获取第1个节点的值
137 template<class T>
138 T DoubleLink<T>::get_first() 
139 {
140     return get_node(0)->value;
141 }
142 
143 // 获取最后一个节点的值
144 template<class T>
145 T DoubleLink<T>::get_last() 
146 {
147     return get_node(count-1)->value;
148 }
149 
150 // 将节点插入到第index位置之前
151 template<class T>
152 int DoubleLink<T>::insert(int index, T t) 
153 {
154     if (index == 0)
155         return insert_first(t);
156 
157     DNode<T>* pindex = get_node(index);
158     DNode<T>* pnode  = new DNode<T>(t, pindex->prev, pindex);
159     pindex->prev->next = pnode;
160     pindex->prev = pnode;
161     count++;
162 
163     return 0;
164 }
165 
166 // 将节点插入第一个节点处。
167 template<class T>
168 int DoubleLink<T>::insert_first(T t) 
169 {
170     DNode<T>* pnode  = new DNode<T>(t, phead, phead->next);
171     phead->next->prev = pnode;
172     phead->next = pnode;
173     count++;
174 
175     return 0;
176 }
177 
178 // 将节点追加到链表的末尾
179 template<class T>
180 int DoubleLink<T>::append_last(T t) 
181 {
182     DNode<T>* pnode = new DNode<T>(t, phead->prev, phead);
183     phead->prev->next = pnode;
184     phead->prev = pnode;
185     count++;
186 
187     return 0;
188 }
189 
190 // 删除index位置的节点
191 template<class T>
192 int DoubleLink<T>::del(int index) 
193 {
194     DNode<T>* pindex = get_node(index);
195     pindex->next->prev = pindex->prev;
196     pindex->prev->next = pindex->next;
197     delete pindex;
198     count--;
199 
200     return 0;
201 }
202 
203 // 删除第一个节点
204 template<class T>
205 int DoubleLink<T>::delete_first() 
206 {
207     return del(0);
208 }
209 
210 // 删除最后一个节点
211 template<class T>
212 int DoubleLink<T>::delete_last() 
213 {
214     return del(count-1);
215 }
216 
217 #endif