【数据结构】双链表

        带头双向循环链表。

List.h

#pragma once
 
#include<stddef.h>//NULL
#include<stdlib.h>//free
#include<assert.h>//assert
 
typedef int SLDataType;
 
typedef struct SLNode
{
	SLDataType data;
	struct SLNode* prev;
	struct SLNode* next;
} SLNode;
 
SLNode* SLInit();
 
void SLPushFront(SLNode* head, SLDataType x);
void SLPushBack(SLNode* head, SLDataType x);
SLDataType SLPopBack(SLNode* head);
SLDataType SLPopFront(SLNode* head);
SLDataType SLErase(SLNode* Del);
void SLInsertBF(SLNode* AFnode, SLDataType x);
void SLInsertAF(SLNode* AFnode, SLDataType x);
void SLDestroy(SLNode** phead);

List.c

#include"List.h"
 
static SLNode* BuySLNode(SLDataType x)
{
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (NULL == newNode)
	{
		perror("malloc failed");
		exit(-1);
	}
	newNode->data = x;
	newNode->prev = newNode;
	newNode->next = newNode;
	return newNode;
}
 
 
 
 
SLNode* SLInit()
{
	return BuySLNode(0);
}
 
void SLPushFront(SLNode* head, SLDataType x)
{
	assert(head);
	//SLInsertBF(head->next, x);
	SLInsertAF(head, x);
}
 
void SLPushBack(SLNode* head, SLDataType x)
{
	assert(head);
	//SLInsertBF(head, x);
	SLInsertAF(head->prev, x);
}
 
SLDataType SLPopBack(SLNode* head)
{
	assert(head);
	assert(head->prev != head);
	return SLErase(head->prev);
}
 
 
SLDataType SLPopFront(SLNode* head)
{
	assert(head);
	assert(head->next != head);
	return SLErase(head->next);
}
 
SLDataType SLErase(SLNode* Del)
{
	assert(Del);
	Del->prev->next = Del->next;
	Del->next->prev = Del->prev;
	SLDataType ret = Del->data;
	free(Del);
	return ret;
}
 
void SLInsertBF(SLNode* AFnode, SLDataType x)
{
	assert(AFnode);
	SLNode* newnode = BuySLNode(x);
	AFnode->prev->next = newnode;
	newnode->prev = AFnode->prev;
	AFnode->prev = newnode;
	newnode->next = AFnode;
}
 
void SLInsertAF(SLNode* BFnode, SLDataType x)
{
	assert(BFnode);
	SLNode* newnode = BuySLNode(x);
	BFnode->next->prev = newnode;
	newnode->next = BFnode->next;
	BFnode->next = newnode;
	newnode->prev = BFnode;
}
 
void SLDestroy(SLNode** phead)
{
	while ((*phead)->next != *phead)
		SLPopBack(*phead);
	free(*phead);
}

test.c

#include<stdio.h>
#include"List.h"
 
void print(SLNode* head)
{
	SLNode* Head = head;
	head = head->next;
	printf("Head<->");
	while (Head != head)
	{
		printf("%d<->", head->data);
		head = head->next;
	}
	printf("Head\n");
}
 
 
void test1()
{
	SLNode* list1 = SLInit();
	SLPushBack(list1, 1);
	SLPushBack(list1, 2);
	SLPushBack(list1, 3);
	SLPushBack(list1, 4);
	SLPushFront(list1, 11);
	SLPushFront(list1, 22);
	print(list1);
	printf("Del = %d\n", SLPopBack(list1)); print(list1);
	printf("Del = %d\n", SLPopFront(list1)); print(list1);
 
	SLDestroy(&list1);
}
 
int main()
{
	test1();
 
	return 0;
}