改进前
要是我问你会不会写双向循环链表，那你一定会不假思索的回答——我当然会。
但如果我让你十分钟之内完成它呢？
那你可能就会犹豫了，十分钟！？双向循环链表那么多的功能，怎么是10分钟能写完的东西呢？
如果你这样想了，那就请听我缓缓道来吧！
#define _CRT_SECURE_NO_WARNINGS #include"List.h" LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTPrint(LTNode* phead) { assert(phead); printf("guard<==>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); } bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; } void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyLTNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; } void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->prev); } void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTNode* next = phead->next; phead->next = next->next; next->next->prev = phead; free(next); } LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 在pos之前插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyLTNode(x); // prev newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } // 删除pos位置的值 void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); } void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
如图，我们第一时间想到的恐怕就是这样的写法，又臭又长。
面试中你如果打算这么写代码，那恐怕10分钟确实不太够。
简化冗杂的代码
为了尽可能地减少代码量，让我们能在10分钟内打出来，我们需要发掘其中可以简化的部分。
头插和尾插的代码可以直接用LTInsert函数来实现。
反正头插和尾插也不过是LTInsert函数在头部和尾部的实现而已。
紧接着就是头删和尾删，同理，它们也不过是LTErase函数在头部和尾部的实现而已。
实现之后大概就是这个样子
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef struct Node { int data; struct Node* next; struct Node* prev; }Node; Node* BuyListNode(int x); Node* SLInit(); void LTPopFront(Node* phead); void LTPushFront(Node* phead, int x); void LTPopBack(Node* phead); void LTDestroy(Node* phead); void LTPushBack(Node* phead, int x); void LTErase(Node* phead); void LTInsert(Node* pos, int x); int LTEmpty(Node* phead); void Print(Node* phead); Node* BuyListNode(int x) { Node* newnode = (Node*)malloc(sizeof(Node)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } Node* SLInit() { Node* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTInsert(Node* pos, int x) { assert(pos); Node* newnode = BuyListNode(x); Node* prev = pos->prev; newnode->next = prev->next; newnode->prev = prev; prev->next = newnode; pos->prev = newnode; } void LTPushFront(Node* phead, int x) { assert(phead); LTInsert(phead->next, x); } void LTPushBack(Node* phead, int x) { assert(phead); LTInsert(phead, x); } void LTPopFront(Node* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->prev); } void LTErase(Node* pos) { assert(pos); Node* prev = pos->prev; Node* next = pos->next; prev->next = next; next->prev = prev; } void LTPopBack(Node* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->prev); } void LTDestroy(Node* phead) { assert(phead); Node* cur = phead->next; while (phead != cur) { Node* next = cur->next; free(cur); cur = next; } free(phead); } int LTEmpty(Node* phead) { assert(phead); return phead == phead->next; } void Print(Node* phead) { Node* cur = phead->next; while (cur != phead) { Node* next = cur->next; printf("%d<==>", cur->data); cur = next; } printf("\n"); }
这样的代码量，我勉强能在10分钟之内打完，大家就更不用说了，5分钟足矣。
只要大家勤加练习，让面试官目瞪口呆指日可待！
