单链表与双链表的结构笔记

通过代码的探索，了解链表基本的使用方法，以及带头插入和不带头插入，头插法和尾插法的区别

#include 
#include 
using namespace std;
//链表结构 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList; 

//双链表结构 
typedef struct DNode{
	int data;
	struct DNode *next,*prior;
}DNode,*DLinkList; 
//创建一个带头节点的单链表（头插法）
LinkList FrontLinkListWithHead(LinkList &L){
	LNode *s;int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->data = -1;
	L->next = NULL;
	while(true){
		scanf("%d",&x);
		if(x==2022)break;
		s = (LNode *)malloc(sizeof(LNode));
		s->next = L->next;
		s->data = x;
		L->next = s;
	}
	return L;
} 
//创建一个不带头节点的单链表（头插法）
LinkList FrontLinkListWithoutHead(LinkList &L){
	LNode *s;int x;
	L = (LinkList)malloc(sizeof(LNode));
	scanf("%d",&x);
	L->data = x;
	L->next = NULL;
	while(true){
		scanf("%d",&x);
		if(x==2022)break;
		s = (LNode *)malloc(sizeof(LNode));
		s->next = L;
		s->data = x;
		L = s;
	}
	return s;
} 
//创建一个带头节点的单链表（尾插法）
LinkList BackLinkListWithHead(LinkList &L){
	LNode *s,*p;int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->data = -1;
	L->next = NULL;
	p = L;
	while(true){
		scanf("%d",&x);
		if(x==2022)break;
		s = (LNode *)malloc(sizeof(LNode));
		s->next = NULL;
		s->data = x;
		p->next = s;
		p = s;
	}
	return L;
} 

//创建一个不带头节点的单链表（尾插法）
LinkList BackLinkListWithoutHead(LinkList &L){
	LNode *s,*p;int x;
	L = (LinkList)malloc(sizeof(LNode));
	scanf("%d",&x);
	L->data = x;
	L->next = NULL;
	p=L;
	while(true){
		scanf("%d",&x);
		if(x==2022)break;
		s = (LNode *)malloc(sizeof(LNode));
		s->next = NULL;
		s->data = x;
		p->next = s;
		p = s;
	}
	return L;
} 

//删除单链表中指定位置的元素(不算头节点的情况） 
void deletelinklist(LinkList &L,int i){
	LNode *p=L->next,*a;int k=1;
	while(++knext;
	}
	a = p->next;
	p->next = p->next->next;
	free(a);
} 

//创建一个带头节点的双链表（头插法）
DLinkList FrontDLinkListWithHead(DLinkList &L){
	 DNode *s; int x;
	 L = (DLinkList)malloc(sizeof(DNode));
	 L->data = -1;
	 L->prior = NULL;
	 L->next = NULL;
	 while(true){
	 	scanf("%d",&x);
	 	if(x==2022)break;
	 	s = (DNode *)malloc(sizeof(DNode));
	 	s->data = x;
	 	s->next = L->next;
	 	s->prior = L;
	 	if(L->next!=NULL){
	 		L->next->prior = s;
		}
		L->next = s; 
	 }
	 return L;
} 

//创建一个不带头节点的双链表（头插法）
DLinkList FrontDLinkListWithoutHead(DLinkList &L){
	 DNode *s; int x;
	 L = (DLinkList)malloc(sizeof(DNode));
	 scanf("%d",&x);
	 L->data = x;
	 L->prior = NULL;
	 L->next = NULL;
	 while(true){
	 	scanf("%d",&x);
	 	if(x==2022)break;
	 	s = (DNode *)malloc(sizeof(DNode));
	 	s->data = x;
	 	s->next = L;
	 	s->prior = NULL;
	 	L = s;
	 }
	 return s;
}

//创建一个带头节点的双链表（尾插法）
DLinkList BackDLinkListWithHead(DLinkList &L){
	DNode *s,*p;int x;
	L = (DLinkList)malloc(sizeof(DNode));
	L->data = -1;
	L->next = NULL;
	L->prior = NULL;
	p=L;
	while(true){
		scanf("%d",&x);
		if(x==2022)break;
		s = (DNode *)malloc(sizeof(DNode));
		s->next = NULL;
		s->prior = p;
		s->data = x;
		p->next = s;
		p = s;
	}
	return L;
} 

//创建一个不带头节点的双链表（尾插法）
DLinkList BackDLinkListWithoutHead(DLinkList &L){
	DNode *s,*p;int x;
	L = (DLinkList)malloc(sizeof(DNode));
	scanf("%d",&x);
	L->data = x;
	L->next = NULL;
	L->prior = NULL;
	p=L;
	while(true){
		scanf("%d",&x);
		if(x==2022)break;
		s = (DNode *)malloc(sizeof(DNode));
		s->next = NULL;
		s->prior = p;
		s->data = x;
		p->next = s;
		p = s;
	}
	return L;
} 

//打印单链表数据 
void printLinkList(LinkList L){
	while(L){
		if(L->data == -1){
			L = L->next;
			printf("本链表含有头节点:");
			continue; 
		}
		printf("%d,",L->data);
		L = L->next;
	}
} 

//打印双链表数据 
void printDLinkList(DLinkList L){
	while(L){
		if(L->data == -1){
			L = L->next;
			printf("本链表含有头节点:");
			continue; 
		}
		printf("%d,",L->data);
		L = L->next;
	}
} 

//删除双链表中指定位置的元素(不算头节点的情况） 
void deleteDlinklist(DLinkList &L,int i){
	DNode *p=L->next,*a;int k=1;
	while(++knext;
	}
	a = p->next;
	p->next->next->prior = p; 
	p->next = p->next->next;
	free(a);
}

int main(){
	//单链表的测试数据 
	LinkList L;
	L = FrontLinkListWithoutHead(L);
	printLinkList(L);
	printf("n");
	deletelinklist(L,3);
	printLinkList(L);
	printf("双链表测试开始n"); 
    //双链表的测试数据
	DLinkList L1;
	L1 = BackDLinkListWithHead(L1);
	deleteDlinklist(L1,3);
	printDLinkList(L1); 
	return 0; 
}

总结：带头插入与不带头插入的区别取决于第一个结点是否含有有效的数据，同时需要注意的是头插法与尾插法是否含有头节点的代码区别。头插法节点区别较大，以下为您展开讲解。

头插法：

当您使用头插法含有头节点时，您只需在头节点后面挂载元素，并使新的元素指向后续的元素即可。

当您使用头插法不包含头节点时，将头节点视为一个指针，这个指针始终指向第一个含有元素的节点。当您继续添加元素时，这个指针在最后会更新指向此节点的数据，注意最后返回的新生成节点的地址。

以上代码仅供参考，如有错误请大家指正，谢谢！