C语言双向链表的实现

文章目录

• • 双向链表简介
  • 结构体构建
  • 创建结点
  • 头插法插入结点
  • 正反向打印链表
  • 删除指定元素
  • 完整代码及用例测试
  • 执行结果
  • 双向链表优缺点分析

双向链表简介

我们知道，单链表（singly linked list）只有一个指向直接后继的指针来表示结点间的逻辑关系，可以方便地查找下一个结点，但是找前驱结点就非常困难。这时，我们就需要用上双向链表(doubly linked list)来解决这个问题。

结构体构建

第一个动作和单链表类似，我们使用结构体来定义出这种数据类型。代码：

typedef struct DLinkNode{
	int data;
	struct DLinkNode *prev;
	struct DLinkNode *next;
}DLNode,*DLNodePtr;
DLNodePtr head;//定义一个全局的头指针

创建结点

为了便于后续 *** 作，我们写一个创建结点的函数。在之后需要创建结点的 *** 作中直接调用此函数，减少代码的重复性。代码：

DLNodePtr GetNewNode(int x){
	DLNodePtr newNode = (DLNodePtr)malloc(sizeof(DLNodePtr));
	newNode->data = x;
	newNode->prev = NULL;
	newNode->next = NULL;
	return newNode;
}

头插法插入结点

//头插法插入节点
void InsertAtHead(int x){
	DLNodePtr temp = GetNewNode(x);
	//1.链表为空，则将head设置为新节点的地址
	if(head==NULL){
		head = temp;
		return ;
	} 
	//2.链表不为空，在头部插入
	head->prev = temp;
	temp->next = head;
	head = temp; 
} 

正反向打印链表

//正向打印
void Print(){
    DLNodePtr p = head;
    printf("正向输出："); 
    while(p!=NULL){
    	printf("%d ",p->data);
    	p=p->next;
	}
	printf("\n");
} 
//反向打印
void ReversePrint() {
	DLNodePtr p = head;
	if(p==NULL){
		return ;
	}
	//到达最后一个结点
	while(p->next!=NULL){
		p = p->next;
	} 
	printf("反向打印：");
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->prev;
	}
	 printf("\n");
}

删除指定元素

void deleteElement(int n){
	DLNodePtr p,q,r;
	p = head;
	while(p->next!=NULL&&p->next->data!=n){
		p = p->next;
	}
	if(p->next==NULL){
		printf("不存在此元素"); 
	}
	q = p->next;
	r = q->next;
	p->next = r;
	if(r!=NULL){
		r->prev = p;
	}
	
	free(q);
} 

完整代码及用例测试

#include 
#include
typedef struct DLinkNode{
	int data;
	struct DLinkNode *prev;
	struct DLinkNode *next;
}DLNode,*DLNodePtr;
DLNodePtr head;//定义一个全局的头指针 
DLNodePtr GetNewNode(int x){
	DLNodePtr newNode = (DLNodePtr)malloc(sizeof(DLNodePtr));
	newNode->data = x;
	newNode->prev = NULL;
	newNode->next = NULL;
	return newNode;
} 
//头插法插入节点
void InsertAtHead(int x){
	DLNodePtr temp = GetNewNode(x);
	//1.链表为空，则将head设置为新节点的地址
	if(head==NULL){
		head = temp;
		return ;
	} 
	//2.链表不为空，在头部插入
	head->prev = temp;
	temp->next = head;
	head = temp; 
} 
//正向打印
void Print(){
    DLNodePtr p = head;
    printf("正向输出："); 
    while(p!=NULL){
    	printf("%d ",p->data);
    	p=p->next;
	}
	printf("\n");
} 
//反向打印
void ReversePrint() {
	DLNodePtr p = head;
	if(p==NULL){
		return ;
	}
	//到达最后一个结点
	while(p->next!=NULL){
		p = p->next;
	} 
	printf("反向打印：");
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->prev;
	}
	 printf("\n");
}
//删除指定元素
void deleteElement(int n){
	DLNodePtr p,q,r;
	p = head;
	while(p->next!=NULL&&p->next->data!=n){
		p = p->next;
	}
	if(p->next==NULL){
		printf("不存在此元素"); 
	}
	q = p->next;
	r = q->next;
	p->next = r;
	if(r!=NULL){
		r->prev = p;
	}
	
	free(q);
} 
//主函数
int main (){
	InsertAtHead(1);
	InsertAtHead(3);
	InsertAtHead(5);
	InsertAtHead(9);
	InsertAtHead(99);
	Print();
	ReversePrint();
	deleteElement(5);
	Print();
	ReversePrint();
	
}

执行结果

双向链表优缺点分析

1.优点：
反转双向链表非常容易。
它可以在执行期间轻松分配或重新分配内存。
与单链表一样，它是最容易实现的数据结构。
这个双向链表的遍历是双向的，这在单链表中是不可能的。
与单链表相比，删除节点很容易。单链表删除需要一个指向要删除的节点和前一个节点的指针，但在双链表中，它只需要要删除的指针。
2.缺点：
与数组和单链表相比，它使用额外的内存（增加了指针）。
由于内存中的元素是随机存储的，因此元素是按顺序访问的，不允许直接访问。