双向链表——C语言实现

双向链表

双向链表就是在链表的基础上，加上一个指向前节点的指针，这样就方便了从后面进行的操作。

实现很简单，直接看代码：

头文件：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

#define N 10

typedef struct ListNode
{
	struct ListNode* _next;
	struct ListNode* _prev;
	LTDataType _data;
}ListNode;

typedef struct List
{
	struct ListNode* _head;
	struct ListNode* _tail;
	int count;
}List;

void ListInit(List* lt);//初始化
void ListDestory(List* lt);//销毁
void ListPushBack(List* lt, LTDataType x);//在最后插入
void ListPushFront(List* lt, LTDataType x);//在前面插入
void ListPopBack(List* lt);//从最后出一个
void ListPopFront(List* lt);//从最前面出一个

ListNode* ListFind(List* lt, LTDataType x);//查找一个节点
void ListInsert(ListNode* pos, LTDataType x);//插入一个节点
void ListErase(ListNode* pos);//清空列表
int ListSize(List* lt);//返回大小
int ListEmpty(List* lt);//判空
void ListPrint(List* lt);//打印链表
void testLT();

实现：

#include "双向链表.h"

void ListInit(List* lt)//初始化
{
	assert(lt);
	lt->_head = (ListNode*)malloc(sizeof(ListNode)* N);
	lt->_tail = lt->_head;
	lt->count = 0;
}

void ListDestory(List* lt)//销毁
{
	if (lt->count == 0)
	{
		return;
	}
	ListNode* p;
	for (int i = 0; i < lt->count; i++)
	{
		p = lt->_head->_next;
		free(lt->_head);
		lt->_head = p;
	}
	free(lt->_head);
	lt->count = 0;
}
void ListPushBack(List* lt, LTDataType x)//在最后插入
{
	assert(lt);
	ListNode* ptmp = (ListNode*)malloc(sizeof(ListNode));
	ptmp->_data = x;
	
	lt->_tail->_next = ptmp;//把尾巴的后连上这个
	ptmp->_prev = lt->_tail;//把后面的前面连上尾巴
	lt->_tail = ptmp;//吧尾巴变成当前插入的最后一个
	lt->count++;
}

void ListPushFront(List* lt, LTDataType x)//在前面插入
{
	assert(lt);
	if (lt->_tail == lt->_head)
	{
		ListPushBack(lt, x);
		return;
	}

	ListNode* ptmp = (ListNode*)malloc(sizeof(ListNode));
	ptmp->_data = x;
	ptmp->_next = lt->_head->_next;
	lt->_head->_next->_prev = ptmp;
	lt->_head->_next = ptmp;
	ptmp->_prev = lt->_head;

	lt->count++;
}
void ListPopBack(List* lt)//从最后出一个
{
	assert(lt);
	ListNode* p;
	p = lt->_tail;
	lt->_tail = p->_prev;
	free(p);
	lt->count--;
}
void ListPopFront(List* lt)//从最前面出一个
{
	assert(lt);
	ListNode* p;
	p = lt->_head->_next;
	if (1 == lt->count)//最后一个
	{
		ListPopBack(lt);
		return;
	}
	lt->_head->_next = p->_next;
	p->_next->_prev = lt->_head;
	free(p);
	lt->count--;
}
//
//ListNode* BuyListNode(LTDataType x);//
ListNode* ListFind(List* lt, LTDataType x)//查找一个节点
{
	assert(lt);
	ListNode* p;
	p = lt->_head->_next;
	for (int i = 0; i < lt->count; i++)
	{
		if (x == p->_data)
		{
			return p;
		}
		p = p->_next;
	}
	return NULL;
}
//void ListInsert(ListNode* pos, LTDataType x);//插入一个节点
void ListErase(ListNode* pos)//删除某个点
{
	assert(pos);
	pos->_next->_prev = pos->_prev;
	pos->_prev->_next = pos->_next;
	free(pos);
}
int ListSize(List* lt)//返回大小
{
	return lt->count;
}
int ListEmpty(List* lt)//判空
{
	return lt->_tail == lt->_head;
}
void ListPrint(List* lt)//打印链表
{
	assert(lt);
	ListNode* p;
	p = lt->_head->_next;
	for (int i = 0; i < lt->count; i++)
	{
		printf("%d  ", p->_data);
		p = p->_next;
	}
	printf("\n");
}

void testLT(){
	List lt;
	ListInit(&lt);

	ListPushFront(&lt, 5);
	ListPushFront(&lt, 3);
	ListPushBack(&lt, 2);
	ListPushBack(&lt, 8);

	//ListDestory(&lt);
	ListPrint(&lt);
	//ListPopBack(&lt);
	//ListPrint(&lt);
	//ListPopFront(&lt);
	//ListPrint(&lt);
	//ListPopFront(&lt);
	//ListPrint(&lt);
	//ListPopFront(&lt);
	//ListPrint(&lt);

	ListDestory(&lt);
	ListPrint(&lt);
	if (ListFind(&lt, 6))
	{
		printf("%d", ListFind(&lt, 6)->_data);
	}
}