定义一个列表（List）模板类，实现列表的初始化、插入、删除操作：
1 template <typename T>
2 struct ListNode //listnode模板类
3 {
4 T data; //数值
5 ListNode<T> * pred; //前驱 引用
6 ListNode<T> * succ; //后继 引用
7 };
8
9 template <typename T>
10 class List
11 {
12 private:
13 int size; //规模
14 ListNode<T> *header; //头哨兵
15 ListNode<T> *trailer; //尾哨兵
16 public:
17 List();
18 ListNode<T> * insertAsFirst(T e); //e当做首节点插入
19 ListNode<T> * insertAsLast(T e); //e当做末节点插入
20 ListNode<T> * insertAsPred(ListNode<T> *p, T e); //e当做节点的前驱插入
21 ListNode<T> * insertAsSucc(ListNode<T> *p, T e); //e当做节点的后继插入
22 T remove(ListNode<T> *p);
23 T find(T e, int n, T p);
24 T & operator[] (int r);
25 int getsize();
26 };
27
28 template <typename T>
29 List<T>::List()
30 {
31 header = new ListNode<T>; //分配节点
32 trailer = new ListNode<T>; //创建头哨兵 尾哨兵
33 header->pred = NULL; header->succ = trailer; //前驱和后继的引用分别指向对方，实现互联
34 trailer->pred = header; trailer->succ = NULL;
35 size = 0;
36 }
37
38 template <typename T>
39 ListNode<T> * List<T>::insertAsFirst(T e) //e当做首节点插入
40 {
41 ListNode<T> * x = new ListNode<T>;
42 ListNode<T> * p = header->succ;
43
44 x->data = e;
45 x->pred = header;
46 x->succ = p;
47 header->succ = x;
48 p->pred = x;
49 size++;
50 return x;
51 }
52
53 template <typename T>
54 ListNode<T> * List<T>::insertAsLast(T e) //e当做末节点插入
55 {
56 ListNode<T> * x = new ListNode<T>;
57 ListNode<T> * p = trailer->pred;
58
59 x->data = e;
60 x->pred = p;
61 x->succ = trailer;
62 p->succ = x;
63 trailer->pred = x;
64 size++;
65 return x;
66 }
67
68 template <typename T>
69 ListNode<T> * List<T>::insertAsPred(ListNode<T> *p, T e) //e当做节点的前驱插入
70 {
71 ListNode<T> * x = new ListNode<T>;
72 ListNode<T> * q = p->pred;
73
74 x->data = e;
75 x->pre = q;
76 x->succ = p;
77 q->succ = x;
78 p->pred = x;
79 size++;
80 return x;
81 }
82
83 template <typename T>
84 ListNode<T> * List<T>::insertAsSucc(ListNode<T> *p, T e) //e当做节点的后继插入
85 {
86 ListNode<T> * x = new ListNode<T>;
87 ListNode<T> * q = p->succ;
88
89 x->data = e;
90 x->pre = p;
91 x->succ = q;
92 q->pred = x;
93 p->succ = x;
94 size++;
95 return x;
96 }
97
98 template <typename T>
99 T List<T>::remove(ListNode<T> *p)
100 {
101 T e;
102 ListNode<T> * m = p->pred;
103 ListNode<T> * n = p->succ;
104 e = p->data;
105 m->succ = n;
106 n->pred = m;
107
108 delete p;
109 size--;
110 return e;
111 }
112
113 template <typename T>
114 T List<T>::find(T e, int n, T p)
115 {
116 while (0 < n--)
117 if (e == (p = p->pred)->data) return p;
118 return NULL;
119 }
120
121 template <typename T>
122 T & List<T>::operator[] (int r)
123 {
124 ListNode<T> * p = header->succ;
125 while(r>0)
126 {
127 p = p->succ;
128 r--;
129 }
130 return p->data;
131 }
132
133 template <typename T>
134 int List<T>::getsize()
135 {
136 return size;
137 }