数据结构 --- c语言实现双向链表_c语言双向链表的代码

双向链表的组成

双向链表主要分为三部分

• 前项指针

• 后项指针

• 数据域

• 一般情况下，创建单一个体，前项指针和后项指针都赋值为空

• 一般采用记录头节点和记录尾节点，再封装的方式写双向链表

双向链表的结构体描述(节点)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct Node
{
	int data;            //数据域
	struct Node* front;  //前项指针
	struct Node* tail;   //后项指针
}NODE,*LPNODE;

再定义一个结构体(链表) 

• 通过记录头节点和尾节点的方式去描述链表

typedef struct DList 
{
	LPNODE frontNode;    //头节点
	LPNODE tailNode;     //尾节点
	int curSize;         //当前节点个数
}DLIST,*LPDLIST;

创建节点

把用户的数据变成一个结构体变量

LPNODE createNode(int data) 
{
    //申请内存
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
    //断言处理
	assert(newNode);
    //前项指针、后项指针置为空
	newNode->front = NULL;
	newNode->tail = NULL;
    //给数据做初始化
	newNode->data = data;
	return newNode;
}

创建链表

• 描述链表最初的状态

LPDLIST createDList() 
{
	LPDLIST list = (LPDLIST)malloc(sizeof(DLIST));    //用结构体变量描述最初状态 做动态内存申请
	assert(list);
	list->frontNode = NULL;                           //链表刚开始是空的 头尾节点指向空
	list->tailNode = NULL;
	list->curSize = 0;                                //当前元素个数为0
	return list;
}

头插法

①新节点的后项指针指向原来链表的头节点

②原来链表的头节点的前项指针指向新节点

③把原来的头节点移到新节点的位置

//要插入的链表 插入的数据
void push_front(LPDLIST list,int data) 
{
    //创建新节点
	LPNODE newNode = createNode(data);
    //list为空 没办法做插入
	if (list == NULL)
		return;
    //只有一个节点 插入的节点既是头节点也是尾节点
	if (list->curSize == 0) 
	{
        //头节点和尾节点都是指向这个节点
		list->frontNode = newNode;
		list->tailNode = newNode;
		list->curSize++;
	}
	else 
	{
        //新节点的后项指针指向原来链表的头节点
		newNode->tail = list->frontNode;
        //原来链表的头节点的前项指针指向新节点
		list->frontNode->front = newNode;
        //把原来的头节点移到新节点的位置 
		list->frontNode = newNode;
		list->curSize++;
	}
}
 
    //测试代码
    LPDLIST list = createDList();
	push_front(list, 1);              //1
	push_front(list, 2);              //2 1
	printByFront(list);               //1 2 通过前项指针做打印 从后往前
	printByTail(list);                //2 1 通过后项指针做打印 从前往后

打印链表

可以通过前项指针去做打印，也可以通过后项指针去做打印

通过前项指针做打印

从最后一个节点往前走，由于记录头节点和尾节点，所以就非常简单啦