设计双向链表
要求
题目要我们实现有关双向链表的基本操作，即以下几个函数（与设计单链表相比，由于多了一个指向前一个节点的指针，因此链接两节点的操作要更加复杂，读者可以通过画图进行理解，事半功倍）:
MyLinkedList* myLinkedListCreate() //创建双向链表 int myLinkedListGet(MyLinkedList* obj, int index) //得到下标为index的节点的值，如果index无效则返回-1 void myLinkedListAddAtHead(MyLinkedList* obj, int val) //链表头插 void myLinkedListAddAtTail(MyLinkedList* obj, int val) //链表尾插 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) //在下标index处插入值为val的节点，如果index等于链表长度，则相当于尾插 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) //删除下标为index的节点，如果index无效，则不操作 void myLinkedListFree(MyLinkedList* obj) //销毁链表
解析函数形参
同昨天的题目一样，设计单链表，题目所给函数传递的是一级指针，因此我们就要使用带哨兵位的双向链表
实现代码
typedef struct List { struct List *next; struct List *prev; int val; } MyLinkedList; //创建双向链表 MyLinkedList* myLinkedListCreate() { MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList)); obj->prev = obj->next = NULL; //令哨兵位的prev和next指针都初始化为空 return obj; } //返回下标为index的节点的数据，若index无效，则返回-1 int myLinkedListGet(MyLinkedList* obj, int index) { int count = 0; MyLinkedList *cur = obj->next; //obj不存储有效数据，因此从next开始计数 while(cur) { if(count == index) return cur->val; cur = cur->next; count++; } return -1; } //头插 void myLinkedListAddAtHead(MyLinkedList* obj, int val) { //创建新节点 MyLinkedList *newHead = (MyLinkedList *)malloc(sizeof(MyLinkedList)); newHead->val = val; //如果链表为空 if(obj->next == NULL) { //直接将新节点接到哨兵位obj后 obj->next = newHead; newHead->next = NULL; newHead->prev = obj; } //如果链表不为空 else { //将新节点嵌入obj和第一个节点之间 obj->next->prev = newHead; newHead->next = obj->next; newHead->prev = obj; obj->next = newHead; } } //尾插 void myLinkedListAddAtTail(MyLinkedList* obj, int val) { //创建新节点 MyLinkedList *newHead = (MyLinkedList *)malloc(sizeof(MyLinkedList)); newHead->val = val; //找到链表的尾 MyLinkedList *cur = obj; while(cur->next) cur = cur->next; //使新节点成为链表的尾 newHead->prev = cur; cur->next = newHead; newHead->next = NULL; } //在下标为index插入节点 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { //如果index为0，直接头插 if(index == 0) { myLinkedListAddAtHead(obj,val); return; } //创建新节点 MyLinkedList *newHead = (MyLinkedList *)malloc(sizeof(MyLinkedList)); newHead->val = val; MyLinkedList *cur = obj->next; //obj不存储有效数据，因此从next开始计数 int count = 0; while(cur) { if(count == index) { //实现插入 cur->prev->next = newHead; newHead->prev = cur->prev; newHead->next = cur; cur->prev = newHead; } cur = cur->next; count++; } //如果index等于链表长度，则直接尾插 if(count == index && cur == NULL) { myLinkedListAddAtTail(obj,val); return; } } //删除下标为index的节点，若index无效，则不操作 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { int count = 0; MyLinkedList *cur = obj->next; //obj不存储有效数据，因此从next开始计数 while(cur) { if(count == index) { //实现删除 cur->prev->next = cur->next; //如果cur的下一个节点为空，那么就不需要将cur下一个节点的prev指针指向cur前一个节点的操作（因为NULL没有prev） if(cur->next) cur->next->prev = cur->prev; free(cur); return; } count++; cur = cur->next; } return; } //销毁链表 void myLinkedListFree(MyLinkedList* obj) { MyLinkedList *cur = obj->next; while(cur && cur->next) { MyLinkedList *temp = cur; //保存cur节点，便于销毁 //重新链接链表 cur->next->prev = cur->prev; cur->prev->next = cur->next; cur = cur->next; free(temp); } free(cur); //销毁最后一个有效节点 obj->next = NULL; //将哨兵位的next指针置空 }
