直接看实现吧：
1 #include2 #include 3 4 typedef int itemType; 5 struct Node; 6 typedef struct Node *pNode; 7 typedef pNode list; 8 typedef pNode position; 9 10 struct Node { 11 itemType item; 12 position prev, next; 13 }; 14 15 list 16 MakeEmpty(list l) 17 { 18 l->item = 0; 19 l->prev = NULL; 20 l->next = NULL; 21 } 22 23 int 24 IsEmpty(list l) 25 { 26 /* 27 if (l->next == NULL) { 28 return 1; 29 } else { 30 return 0; 31 } 32 */ 33 return l->next == NULL; 34 } 35 36 int 37 IsLast(position p, list l) 38 { 39 return p->next == NULL; 40 } 41 42 position 43 Find(itemType item, list l) 44 { 45 position p; 46 47 p = l->next; 48 while (p != NULL && p->item != item) { 49 p = p->next; 50 } 51 52 return p; 53 } 54 /* 55 position 56 FindPrevious(itemType item, list l) 57 { 58 position p; 59 60 p = l; 61 while (p->next != NULL && p->next->item != item) { 62 p = p->next; 63 } 64 65 return p; 66 } 67 */ 68 void 69 Delete(itemType item, list l) 70 { 71 position p, tmp; 72 73 p = Find(item, l); 74 75 if (p != NULL) { 76 if (p->next == NULL) { 77 p->prev->next = NULL; 78 } else { 79 p->next->prev = p->prev; 80 p->prev->next = p->next; 81 } 82 free(p); 83 } 84 } 85 86 void 87 Insert(itemType item, list l, position p) 88 { 89 position tmp; 90 91 tmp = (position)malloc(sizeof(struct Node)); 92 if (tmp == NULL) { 93 printf("Out of space!\n"); 94 return; 95 } 96 97 tmp->item = item; 98 tmp->next = p->next; 99 tmp->prev = p;100 p->next = tmp;101 }102 103 void104 DeleteList(list l)105 {106 position p, tmp;107 108 p = l->next;109 while (p != NULL) {110 tmp = p;111 p = p->next;112 free(tmp);113 } 114 free(l);115 }116 117 position118 Header(list l)119 {120 return l;121 }122 123 position124 First(list l)125 {126 return l->next;127 }128 129 position130 Advance( position p )131 {132 return p->next;133 }134 135 itemType136 Retrieve( position p )137 {138 return p->item;139 }140 141 void142 PrintList( list l)143 {144 position p;145 p = First(l);146 while (p != NULL) {147 printf("%d\t", Retrieve(p));148 p = Advance(p);149 }150 printf("\n");151 }152 153 int154 main(int argc, char** argv)155 {156 list l;157 // init158 l = (list)malloc(sizeof(struct Node));159 MakeEmpty(l);160 // insert some elememts161 position p;162 p = Header(l);163 for (int i = 0; i < 10; i++) {164 Insert(i, l, p);165 p = Advance(p);166 }167 // retrieve168 PrintList(l);169 // find and delete170 Delete(0, l);171 Delete(9, l);172 Delete(100, l);173 PrintList(l);174 175 printf("%d\n", l->next->next->prev->item);176 177 system("pause");178 return 0;179 }