数据结构-无头链表，双向链表，双向循环链表

无头链表

头插

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
//使用二级指针方法
//无头链表：第一个节点存放数据
struct Node
{
	int data;
	struct Node* next;
};
//创建节点
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	if (!newNode)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
//头插
void insertNodeByhead(struct Node** list,int data)
{
	struct Node* newNode = createNode(data);
	newNode->next = (*list);//新节点指向原来的表头
	(*list) = newNode;//然后现在新的节点又变成表头
}

尾插

//尾插
void insertNodeByTail(struct Node* list,int data)
{
	struct Node* newNode = createNode(data);
	struct Node* pMove = list;
	while (pMove->next != NULL)
	{
		pMove = pMove->next;
	}
	pMove->next = newNode;
}

指定位置删除

//指定位置删除
void delNode(struct Node** list,int num)
{
	struct Node* posNodeFront = *list;
	if (posNodeFront == NULL)
	{
		printf("链表为空");
		return;
	}
	if ((posNodeFront->next == NULL) && (posNodeFront->data != num))
	{
		printf("找不到指定位置！\n");
		return;
	}
	if (posNodeFront->data == num)
	{
		struct Node* posNode = posNodeFront->next;
		*list = posNode;
		free(posNodeFront);
		posNodeFront == NULL;
		return;
	}
	struct Node* posNode = posNodeFront;
	while (posNode->data != num)
	{
		posNodeFront = posNode;
		posNode = posNodeFront->next;
		if (posNode == NULL)
		{
			printf("找不到指定位置\n");
		}
	}
	posNodeFront->next = posNode->next;
	free(posNode);
	posNode = NULL;
}

另一种写法，封装方式：

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
struct Node
{
	int data;
	struct Node* next;
};
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
//创建链表
struct List
{
	struct Node* frontNode;
	struct Node* tailNode;
	int size;
};
struct List* creatList()
{
	struct List* list = (struct List*)malloc(sizeof(struct List));
	list->frontNode = list->tailNode = NULL;
	list->size = 0;
	return list;
}
//头插
void insertNodeByHead2(struct List* list,int data)
{
	struct Node* newNode = createNode(data);
	if (list->size == 0)//第一个节点既是表尾元素表头节点
		list->tailNode = newNode;
	else
		newNode->next = list->frontNode;
	list->frontNode = newNode;
	list->size++;
}
//尾插
void insertNodeByTail2(struct List* list, int data)
{
	struct Node* newNode = createNode(data);
	if (list->size == 0)
		list->frontNode = newNode;
	else
		list->tailNode->next = newNode;
		list->tailNode = newNode;
	list->size++;
}
void PrintNode(struct List* list)
{
	struct Node* pMove = list->frontNode;
	while (pMove)
	{
		printf("%d\t", pMove->data);
		pMove = pMove->next;
	}
	printf("\n");
}
int main()
{
	struct List* list = creatList();
	insertNodeByHead2(list, 111);
	insertNodeByHead2(list, 424);
	insertNodeByHead2(list, 333);
	insertNodeByHead2(list, 3343);
	PrintNode(list);
 
    return 0;
}

双向链表

头插

尾插

指定位置插入

代码

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
struct Node
{
	int data;
	struct Node* left;
	struct Node* right;
};
 
//创建节点
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}
 
struct List
{
	//万金油
	int size;
	struct Node* firstNode;//第一个节点
	struct Node* lastNode;//第二个节点（尾节点）
};
 
//任何东西都是从无到有
struct List* createlist()
{
	//申请内存
	struct List* list = (struct List*)malloc(sizeof(struct List));
 
	//初始化
	list->size = 0;
	list->firstNode = list->lastNode = NULL;
	return list;
}
//头插
void insertNodeByHead(struct List* list,int data)
{
	struct Node* newNode = createNode(data);
	if (list->firstNode == NULL)
		list->lastNode = newNode;
	else
	{
		list->firstNode->left = newNode;
		newNode->right = list->firstNode;
	}
	list->firstNode = newNode;
	list->size++;
}
//尾插
void insertNodeByTail(struct List* list, int data)
{
	struct Node* newNode = createNode(data);
	if (list->lastNode == NULL)
		list->firstNode = newNode;
	else
	{
		list->lastNode->right = newNode;
		newNode->left=list->lastNode;
	}
	list->lastNode = newNode;
	list->size++;
}
//指定位置插入
void insertNodePos(struct List* list, int data, int num)
{
	if (list->size == 0)
	{
		printf("链表为空");
		return;
	}
	else if (list->firstNode->data == num)
	{
		insertNodeByHead(list, data);
	}
	else
	{
		struct Node* posNode = list->firstNode->right;
		struct Node* posNodeFront = list->firstNode;
		while ((posNode!=NULL) && (posNode->data != num))
		{
			posNodeFront = posNode;
			posNode = posNode->right;
		}
		if (posNode==NULL)
		{
			printf("找不到\n");
			return;
		}
		else
		{
			struct Node* newNode = createNode(data);
			posNodeFront->right = newNode;
			newNode->left = posNodeFront;
			newNode->right = posNode;
			posNode->left = newNode;
			list->size++;
		}
	}
}
 
void PrintNodeByRight(struct List* list)
{
	if (list->size == 0)
	{
		printf("链表为空无法打印");
	}
	else
	{
		//从前面开始打印
		struct Node* pMove = list->firstNode;//这里注意不要写成list->firstNode->right,不然打印第一个数据不会打印跳过list->firstNode的数据
		while (pMove)
		{
			printf("%d\t", pMove->data);
			pMove = pMove->right;
		}
		printf("\n");
	}
}
 
void PrintNodeByLeft(struct List* list)
{
	if (list->size == 0)
	{
		printf("链表为空无法打印");
	}
	else
	{
		//从后面开始打印
		struct Node* pMove = list->lastNode;
		while (pMove)
		{
			printf("%d\t", pMove->data);
			pMove = pMove->left;
		}
		printf("\n");
	}
}
 
int main()
{
	struct List* list = createlist();
	insertNodeByHead(list, 2);
	insertNodeByHead(list, 3);
	insertNodeByHead(list, 6);
	insertNodeByTail(list, 90);
	insertNodeByTail(list, 900);
	insertNodePos(list, 333,6);
	PrintNodeByRight(list);
	return 0;
}
 

双向循环链表

尾插

指定位置插入

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
struct Node
{
	int data;
	struct Node* left;
	struct Node* right;
};
 
//创建链表
struct Node* createlist()
{
	struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
	if (!headNode)
		printf("创建失败\n");
	else
		headNode->left = headNode->right = headNode;
 
		return headNode;
}
//创建节点
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	if (newNode == NULL)
		printf("创建新节点失败");
	else
	{
		newNode->left = newNode->right =NULL;
		newNode->data = data;
	}
	return newNode;
}
//尾插
void insertNodeByTail(struct Node* headNode, int data)
{
	struct Node* newNode = createNode(data);
	if (newNode == NULL)
	{
		return;
	}
	else
	{
		struct Node* TailNode = headNode->left;
		//这里顺序可以调乱
		headNode->left = newNode;
		newNode->right = headNode;
		newNode->left = TailNode;
		TailNode->right = newNode;	
	}
}
//指定位置插入
void insertNodeByPos(struct Node* headNode,int data,int num)
{
	if ((headNode->left = headNode->right) == headNode)
	{
		printf("链表为空\n");
		exit(0);
	}
	else
	{
		struct Node* newNode = createNode(data);
		struct Node* posNodeFront = headNode;
		struct Node* posNode = headNode->right;
		while (posNode != headNode && posNode->data != num)
		{
			posNodeFront = posNode;
			posNode = posNode->right;
		}
		if (posNode == headNode)
		{
			printf("找不到指定位置");
			exit(0);
		}
		
		else
		{
			//这里也是可以调乱顺序
			posNodeFront->right = newNode;
			newNode->left = posNodeFront;
			newNode->right = posNode;
			posNode->left = newNode;
		}
	}
}
//打印
void PrintNode(struct Node* headNode)
{
	if ((headNode->left = headNode->right)==headNode)
	{
		printf("链表为空，无法打印\n");
		exit(0);
	}
	struct Node* pMove = headNode->right;
	while (pMove!=headNode)
	{
		printf("%d\t", pMove->data);
		pMove = pMove->right;
	}
	printf("\n");
}
 
 
int main()
{
	struct Node* list = createlist();
	insertNodeByTail(list, 2);
	insertNodeByTail(list, 3);
	insertNodeByTail(list, 4);
	insertNodeByTail(list, 5);
	PrintNode(list);
	insertNodeByPos(list, 9,2);
	PrintNode(list);
 
	return 0;
}