您现在的位置是：首页 >技术教程 >假如面试官让你十分钟完成双向循环链表网站首页技术教程

• ? 博客内容：假如面试官让你十分钟完成双向循环链表，多一秒都不行

• ? 作  者：陈大大陈

• ? 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！

• ? 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 ? ? ?

改进前 

 要是我问你会不会写双向循环链表，那你一定会不假思索的回答——我当然会。

但如果我让你十分钟之内完成它呢？

那你可能就会犹豫了，十分钟！？双向循环链表那么多的功能，怎么是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("
");
}

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("
");
}

这样的代码量，我勉强能在10分钟之内打完，大家就更不用说了，5分钟足矣。

只要大家勤加练习，让面试官目瞪口呆指日可待！