链表 linked list网站首页 技术交流

链表 linked list

yexiuuu 2025-03-25 00:01:02

简介链表 linked list

Inserting a node at beginning

#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int x);
void Print();
 
int main()
{
	int n,i,x;
	printf("How many numbers:");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
	 	printf("Input one number:");
	 	scanf("%d",&x);
	 	Insert(x);
	}
	Print();
	return 0;
} 
 
void Insert(int x)
{
	Node* temp = (Node*)malloc(sizeof(Node));    //C++: Node* temp = new Node();
	temp->data = x;
	temp->next = head;
	head = temp;
} 

void Print()
{
	Node* p = head;
	printf("List is:");
	while(p != NULL)
	{
		printf("  %d",p->data);
		p = p->next;
	}
}

//If head is local variable, return value
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;
 
Node* Insert(Node* head,int x);
void Print(Node* head);
 
int main()
{
	int n,i,x;
	Node* head = NULL;
	printf("How many numbers:");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
	 	printf("Input one number:");
	 	scanf("%d",&x);
	 	head = Insert(head,x);
	}
	Print(head);
	return 0;
} 
 
Node* Insert(Node* head,int x)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = x;
	temp->next = head;
	head = temp;
	return head;
} 

void Print(Node* head)
{
	Node* p = head;
	printf("List is:");
	while(p != NULL)
	{
		printf("  %d",p->data);
		p = p->next;
	}
}

//If head is local variable, call by reference
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;
 
void Insert(Node** head,int x);
void Print(Node** head);
 
int main()
{
	int n,i,x;
	Node* head = NULL;
	printf("How many numbers:");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
	 	printf("Input one number:");
	 	scanf("%d",&x);
	 	Insert(&head,x);
	}
	Print(&head);
	return 0;
} 
 
void Insert(Node** head,int x)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = x;
	temp->next = *head;
	*head = temp;
} 

void Print(Node** head)
{
	Node* p = *head;
	printf("List is:");
	while(p != NULL)
	{
		printf("  %d",p->data);
		p = p->next;
	}
}

Inserting a node at nth position

#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int data,int n);
void Print();
 
int main()
{
	Insert(2,1);
	Insert(3,2);
	Insert(4,1);
	Insert(5,2);
	Print();	//List is 4 5 2 3
	return 0;
} 
 
void Insert(int data,int n)
{
	Node* temp1 = (Node*)malloc(sizeof(Node));    //C++: Node* temp = new Node();
	temp1->data = data;
	temp1->next = NULL;
	if(n==1){
		temp1->next = head;
		head = temp1;
		return;
	}
	Node* temp2 = head;
	for(int i=0;i<n-2;i++){
		temp2 = temp2->next;
	}
	temp1->next = temp2->next;
	temp2->next = temp1;
} 

void Print()
{
	Node* p = head;
	printf("List is:");
	while(p != NULL)
	{
		printf(" %d",p->data);
		p = p->next;
	}
}

Delete a node at nth position

#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int data,int n);
void Print();
void Delete(int n);
 
int main()
{
	Insert(2,1);
	Insert(3,2);
	Insert(4,1);
	Insert(5,2);
	Print();	//List is 4 5 2 3
	int n;
	printf("\nEnter the position of deletion:");
	scanf("%d",&n);
	Delete(n);
	Print();
	return 0;
} 
 
void Insert(int data,int n)
{
	Node* temp1 = (Node*)malloc(sizeof(Node));
	temp1->data = data;
	temp1->next = NULL;
	if(n==1){
		temp1->next = head;
		head = temp1;
		return;
	}
	Node* temp2 = head;
	for(int i=0;i<n-2;i++){
		temp2 = temp2->next;
	}
	temp1->next = temp2->next;
	temp2->next = temp1;
} 

void Print()
{
	Node* p = head;
	printf("List is:");
	while(p != NULL)
	{
		printf(" %d",p->data);
		p = p->next;
	}
}

void Delete(int n)
{
	Node* temp1 = head;
	if(n==1){
		head = temp1->next;
		free(temp1);
		return;
	}
	for(int i=0;i<n-2;i++){
		temp1 = temp1->next;
	}
	Node* temp2 = temp1->next;
	temp1->next = temp2->next;
	free(temp2);	//C++: delete temp2;
}

//Delete a node with a specific value
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int data,int n);
void Print();
void Delete(int x);
 
int main()
{
	Insert(2,1);
	Insert(3,2);
	Insert(4,1);
	Insert(5,2);
	Print();	//List is 4 5 2 3
	int x;
	printf("\nEnter the value you want to delete:");
	scanf("%d",&x);
	Delete(x);
	Print();
	return 0;
} 
 
void Insert(int data,int n)
{
	Node* temp1 = (Node*)malloc(sizeof(Node));
	temp1->data = data;
	temp1->next = NULL;
	if(n==1){
		temp1->next = head;
		head = temp1;
		return;
	}
	Node* temp2 = head;
	for(int i=0;i<n-2;i++){
		temp2 = temp2->next;
	}
	temp1->next = temp2->next;
	temp2->next = temp1;
} 

void Print()
{
	Node* p = head;
	printf("List is:");
	while(p != NULL)
	{
		printf(" %d",p->data);
		p = p->next;
	}
}

void Delete(int x)
{
	Node* temp1 = head;
	if(temp1->data == x){
		head = temp1->next;
		free(temp1);
		return;
	}
	Node* temp2 = temp1->next;
	while(temp2->data != x){
		temp1 = temp1->next;
		temp2 = temp1->next;
	}
	temp1->next = temp2->next;
	free(temp2);
}

Reserve a liked list using iteration迭代

//Reverse a liked list using iteration
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int data,int n);
void Print();
void Reverse();
 
int main()
{
	Insert(2,1);
	Insert(3,2);
	Insert(4,1);
	Insert(5,2);
	Print();	//List is 4 5 2 3
	Reverse();
	Print();	//List is 3 2 5 4
	return 0;
} 
 
void Insert(int data,int n)
{
	Node* temp1 = (Node*)malloc(sizeof(Node));
	temp1->data = data;
	temp1->next = NULL;
	if(n==1){
		temp1->next = head;
		head = temp1;
		return;
	}
	Node* temp2 = head;
	for(int i=0;i<n-2;i++){
		temp2 = temp2->next;
	}
	temp1->next = temp2->next;
	temp2->next = temp1;
} 

void Print()
{
	Node* p = head;
	printf("List is:");
	while(p != NULL)
	{
		printf(" %d",p->data);
		p = p->next;
	}
	printf("\n");
}

void Reverse()
{
	Node *prev,*current,*next;
	prev = NULL;
	current = head;
	next = NULL;
	while(current != NULL){
		next = current->next;
		current->next = prev;
		prev = current;
		current = next;
	}
	head = prev;
}

Print a liked list using recursion递归

//Print a liked list using recursion
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int data,int n);
void Print(Node* p);
void ReversePrint(Node* p);
 
int main()
{
	Insert(2,1);
	Insert(3,2);
	Insert(4,1);
	Insert(5,2);
	printf("List is:");
	Print(head);	//List is 4 5 2 3
	printf("ReverseList is:");
	ReversePrint(head);	//List is 3 2 5 4
	return 0;
} 
 
void Insert(int data,int n)
{
	Node* temp1 = (Node*)malloc(sizeof(Node));
	temp1->data = data;
	temp1->next = NULL;
	if(n==1){
		temp1->next = head;
		head = temp1;
		return;
	}
	Node* temp2 = head;
	for(int i=0;i<n-2;i++){
		temp2 = temp2->next;
	}
	temp1->next = temp2->next;
	temp2->next = temp1;
} 

void Print(Node* p)
{
	if(p==NULL){
		printf("\n");
		return;
	}    //递归需要退出条件 
	printf(" %d",p->data);
	Print(p->next);
}

void ReversePrint(Node* p)
{
	if(p==NULL) return;
	ReversePrint(p->next);
	printf(" %d",p->data);
}

反向打印：先调用再打印，栈帧不会消失，等递归结束后，再从栈顶开始打印

Reverse a linked list using recursion

//Reverse a linked list using recursion
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;
 
void Insert(int data,int n);
void Print(Node* p);
void Reverse(Node* p);
 
int main()
{
	Insert(2,1);
	Insert(3,2);
	Insert(4,1);
	Insert(5,2);
	Reverse(head);
	printf("ReverseList is:");
	Print(head);	//List is 3 2 5 4
	return 0;
} 
 
void Insert(int data,int n)
{
	Node* temp1 = (Node*)malloc(sizeof(Node));
	temp1->data = data;
	temp1->next = NULL;
	if(n==1){
		temp1->next = head;
		head = temp1;
		return;
	}
	Node* temp2 = head;
	for(int i=0;i<n-2;i++){
		temp2 = temp2->next;
	}
	temp1->next = temp2->next;
	temp2->next = temp1;
} 

void Print(Node* p)
{
	if(p==NULL){
		printf("\n");
		return;
	}    //递归需要退出条件 
	printf(" %d",p->data);
	Print(p->next);
}

void Reverse(Node* p)
{
	if(p->next == NULL){
		head = p;
		return;
	}
	Reverse(p->next);
	p->next->next = p;
	p->next = NULL;
}

Doubly liked list 双向链表

//Doubly liked list
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
 	struct Node* prev;
	int data;
 	struct Node* next;
};
typedef struct Node Node;

Node* head = NULL;

Node* GetNewnode(int x);
void InsertatHead(int x);
void InsertatTail(int x);
void Print();
void ReversePrint();
 
int main()
{
	InsertatHead(2);
	InsertatHead(1);
	InsertatTail(3);
	InsertatTail(4);
	Print();
	ReversePrint();
	return 0;
} 

Node* GetNewnode(int x)
{
	Node* Newnode = (Node*)malloc(sizeof(Node));
	Newnode->prev = NULL;
	Newnode->data = x;
	Newnode->next = NULL;
	return Newnode;
} 

void InsertatHead(int x)
{
	Node* Newnode = GetNewnode(x);
	if(head == NULL){
		head = Newnode;
		return;
	}
	head->prev = Newnode;
	Newnode->next = head;
	head = Newnode;
} 

void InsertatTail(int x)
{
	Node* Newnode = GetNewnode(x);
	if(head == NULL){
		head = Newnode;
		return;
	}
	Node* p = head;
	while(p->next != NULL){
		p = p->next;
	}
	Newnode->prev = p;
	p->next = Newnode;
}

void Print()
{
	Node* p = head;
	printf("List is");
	while(p != NULL){
		printf(" %d",p->data);
		p = p->next;
	}
	printf("\n");
}

void ReversePrint()
{
	Node* p = head;
	if(p == NULL) return;
	while(p->next != NULL){
		p = p->next;
	}
	printf("ReverseList is");
	while(p != NULL){
		printf(" %d",p->data);
		p = p->prev;
	}
	printf("\n");
}

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。