Data structure and algorithm learning notes (C language)

Circular linked list

1. Definition: circular linked list is another form of linked storage structure. Its feature is that the pointer field of the last node in the table points to the head node, and the whole linked list forms a ring. If the circular linked list is an empty list, the next pointer of the head node directly points to itself

A snake bites its tail, and an ant comes from it 🐍 Starting from any position of the body, you can climb the whole body of the side snake. Similarly, starting from any node in the circular linked list, you can find other nodes in the list.

If we want to access the tail node, we need to start from the pointer, go from node to node, and then go to the tail node. The time complexity is tail O(n);

If we want to merge two linear tables A and B, we need to make the next pointer of the tail node of A point to the first element node of B, then make the next pointer of the tail node of B point to the head node of A, and then release the head node of B. Where the tail nodes of two are to be accessed, the time complexity tail O(Length(A) + Length(B))

Improved form: do not set the head pointer, but set the tail pointer to point to the tail node

In this way, the tail node can be accessed in one step, and the header node can be accessed directly. The time complexity is O(1)

Consider merging linear tables A and B. for the same operation, the time complexity becomes O(1), and the code is as follows

p = tailA->next; /*Save header node of table A*/
tailA->next = tailB->next->next; /*Let the next pointer of the tail node of A point to the first node of B*/
q = tailB->next; /*Save header node of table B*/
tailB->next = p; /*Let the next pointer of the tail node of B point to the head node of A*/
free(q); /*Release the head node of B*/

It can be seen that setting the tail pointer to replace the head pointer has a lot of convenience. Similarly, if you grasp the tail pointer, the whole circular linked list can be picked up

C language describes the cyclic linked list code as follows

typedef struct CNode {
	Elemtype data;
	struct CNode *next;
}CNode, *TailCLinkList;

TailCLinkList is of CNode * type, that is, the pointer type pointing to the node, and it is fixed as the tail pointer. The pointers of ordinary nodes are distinguished by CNode *
2. Implementation of circular linked list

2.1 initialize the circular linked list

/*Create an empty circular linked list*/
Status InitCLinkList(TailCLinkList *L) {
	*L = (CNode *)malloc(sizeof(CNode));
	/*Create a head node (an empty linked list has only one head node and is a special tail node)*/
	if (!(*L)) exit(OVERFLOW);
	(*L)->next = *L;
	/*Let the next pointer field of the header node point to itself*/
	return OK;
}

2.2 clear the cycle linked list

void ClearCLinkList(TailCLinkList *L) 
{
	CNode *p, *q;
	p = (*L)->next->next; /*Let p point to the initial node*/
	while (p != (*L)->next) {
	/*When p does not loop to the head node*/
		q = p->next;
		free(p);
		p = q;
	}
	*L = p;
	/*Let * L refer to the space at the back node*/
	(*L)->next = *L;
	/*Let the next pointer field of the header node refer back to itself*/
}	

2.3 destroy the circular linked list

void DestroyCLinkList(TailCLinkList *L)
{
	CNode *p, *q;
	/*p Point to primitive node*/
	p = (*L)->next->next;
	/*If p has not reached the head node, the following loop is executed*/
	while (p != (*L)->next) {
		q = p->next;
		free(p);
		p = q;
	}
	/*After releasing the space of ordinary nodes, release the space of head nodes*/
	*L = p;
	free(*L);
	/*Modify * L to NULL*/
	*L = NULL;
}

2.4 return the number of elements in the circular linked list

int CLinkListLength(TailCLinkList L)
/*Note the number of elements. There are no stored elements in the header node data field*/
{
	int i = 0;
	CNode *p;
	p = L->next->next;
	while(p != (*L)->next) {
		++i;
		p = p->next;
	}
	return i;
}

2.5 return the value of the ith element in the circular linked list

Status GetElem(TailCLinkList L, int i, ElemtType *e)
{
	int j = 1;
	CNode *p;
	p = L->next->next;
	while (p != (*L)->next && j < i)
	{
		p = p->next;
		++j;
	}
	if (p = (*L)->next || j > i)
		return ERROR;
	/*The above if judgment indicates that the ith element does not exist*/
	/*That is, the table length is less than i or i < 1*/
	*e = p->data;
	return OK;
}

2.6 determine the position of elements equal to e in the circular linked list

#define NOT_FOUND 0
int LocateElem(TailCLinkList L, ElemType e)
/*If found, the number of elements is returned; otherwise, 0 is returned*/
{
	int i = 0;
	CNode *p;
	p = L->next->next;
	while (p != (*L)->next && p->data != e)
	{
		++i;
		p = p->next;
	}
	if (p = (*L)->next) return NOT_FOUND;
	return i;
}	

2.7 inserting elements into circular linked list

/*Insert the element before bit i, after the head node when i == 1, and after the tail node when i = length + 1*/
Status CLinkListInsert(TailCLinkList *L, int i, ElemType e)
{
	int j = 1;
	CNode *p, *s;
	p = (*L)->next;
	/*p The purpose of starting from the head node is to unify the insertion from the head node and the insertion from other nodes*/
	while (p != *L && j < i)
	{
		p = p->next;
		++j;
	}
	if (j == i) {
		/*Both cases of i == 1 and i == length + 1 are included*/
		s = (CNode *)malloc(sizeof(CNode));
		/*The following code inserts a new node s, even before the first element node*/
		s->data = e;
		s->next = p->next;
		p->next = s;
		return OK;
	}
	return ERROR;
}	

2.8 delete elements in circular linked list

Status CLinkListInsert(TailCLinkList *L, int i, ElemType *e)
{
	int j = 1;
	CNode *p, *q;
	p = *L->next;
	while (p != *L && j < i) {
		p = p->next;
		++j;
	}
	if (p = *L || j > i) 
	/*Table length is less than i or i < 1*/
		return ERROR;
	/*p->next Indicates the location of the node to delete*/
	q = p->next;
	/*Get node data element*/
	*e = q->data;
	/*Delete node*/
	p->next = q->next;
	/*Release node*/
	free(q);
	return OK;
}
	

2.9 traversing the elements in the circular linked list

void CLinkListTraverse(TailCLinkList L)
{
	CNode *p;
	p = L->next->next;
	while (p != L->next) {
	/*It's a personal habit to separate elements with spaces*/
		printf("%c ", p->data);
		p = p->next;
	}
	printf("\n");
}

2.10 creating circular linked list by tail interpolation

/*Here, it is assumed that the data element is of character type and the storage space is sufficient*/
typedef char ElemType
void CreateCLinkList_Tail(TailCLinkList *L, int n)
{
	CNode *p;
	int i;
	char ch;
	/*Initialize and create an empty table with only header nodes*/
	*L = (CNode *)malloc(sizeof(CNode));
	(*L)->next = *L;
	/*Generate new nodes in turn and insert them at the end of the table*/
	for (i = 0; i < n; i++) {
		scanf("%c", &ch);
		/*You can also read characters with getchar()*/
		p = (CNode *)malloc(sizeof(CNode));
		p->data = ch;
		p->next = (*L)->next;
		(*L)->next = p;
		/*p Become tail node after insertion*/
		*L = p;
	}
}	

2.10 creating circular linked list by head interpolation

/*Here, it is assumed that the data element is of character type and the storage space is sufficient*/
typedef char ElemType
void CreateCLinkList_Head(TailCLinkList *L, int n)
{
	CNode *p;
	int i;
	char ch;
	/*Initialize and create an empty table with only header nodes*/
	*L = (CNode *)malloc(sizeof(CNode));
	(*L)->next = *L;
	/*First insert a node fixed as the tail of the circular linked list*/
	scanf("%c", &ch);
	p = (CNode *)malloc(sizeof(CNode));
	p->data = ch;
	p->next = *L;
	(*L)->next = p;
	*L = p;
	/*Generate new nodes in turn and insert them into the header*/
	for (i = 1; i < n; i++) {
		scanf("%c", &ch);
		/*You can also read characters with getchar()*/
		p = (CNode *)malloc(sizeof(CNode));
		p->data = ch;
		/*Let the next pointer of p point to the initial node*/
		p->next = (*L)->next->next;
		/*p After insertion, it becomes a primitive node*/
		(*L)->next->next = p;
	}
}	

Well, the circular linked list will be introduced here first. If you feel that the above code is not easy to understand, you can declare a CNode *head in each function as the head node of the circular linked list. During initialization, head = *L, then the tail is the head and the head is the tail. In other times, head = *L - > next, the head is behind the tail, so it is easier to understand after substitution

Next, we introduce the bidirectional linked list

Bidirectional linked list

1. Definition: a two-way linked list is to set a pointer field to its predecessor in each node of the single linked list. Therefore, each node in the two-way linked list has two pointer fields. One next pointer points to the direct successor and one prior pointer points to the direct precursor

Why learn two-way linked list? Imagine a situation where the boss asks you about the information of the i-th employee in a single chain list. You start from the first node and then visit it until the i-th element node. You say it's Zhang San. Then the boss asks you, who's the first one? You have to start from the first node and visit it to the i-1st element node. Oh, it's Li Si. The boss asks you again. In front of Li Si, you're very angry, I cursed the boss secretly in my heart and thought that I would print all of them. That's 500000 people. The boss fired you without saying a word!

The two-way linked list is generated to access the previous element of an element. It only needs the time of pos - > prior, O(1)!

The C language description of bidirectional linked list is as follows:

typedef struct DulNode {
	ElemType data;
	struct DulNode *prior, *next;
}DulNode, *DuLinkList;

Here, according to the previous agreement, the DuLinkList is the header pointer, and the pointers of ordinary nodes are distinguished by DulNode *

2. Implementation of bidirectional linked list

2.1 initialization of bidirectional linked list

/*Create an empty two-way linked list*/
Status InitDuLinkList(DuLinklist *L)
{
	*L = (DuLinkList)malloc(sizeof(DulNode));
	if(!(*L)) exit(OVERFLOW);
	/*The empty linked list has only one header node, and the pointer fields are NULL*/
	(*L)->prior = NULL;
	(*L)->next = NULL;
	return OK;
}

Clearing the two-way linked list, destroying the two-way linked list, returning the number of elements in the two-way linked list, returning the value of the i-th element in the two-way linked list, determining the position of the element value equal to e in the two-way linked list, and traversing the element nodes in the two-way linked list are the same as those in the single linked list. You only need to start from the first node and go down the next pointer field. The prior pointer field is not used, If you are not familiar with the operation of single linked list, you can see my previous article

2.2 inserting elements

Status DuLinkListInsert(DuLinkList *L, int i, ElemType e)
{
	int j = 1;
	DulNode *p, *s;
	p = *L;
	/*Here is the starting point. j is the table length plus 1*/
	while (p && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	/*Table length + 1 < I or I < 1*/
	/*The insertion at the end of the table is special because tail - > next = = null, and there is no tail - > next - > prior*/
	if (p->next == NULL) {
		s = (DulNode *)malloc(sizeof(DulNode));
		s->data = e;
		s->prior = p;
		s->next = NULL;
		p->next = s;
		return OK;
	}
	s = (DulNode *)malloc(sizeof(DulNode));
	/*The following code inserts a new node s, even before the first element node*/
	s->data = e;
	s->prior = p;
	s->next = p->next;
	p->next->prior = s;
	/*Note that P - > next is used in the above two steps, which must be before the next step*/
	p->next = s;
	return OK;
}	

2.3 delete the node of the ith element and receive its data element with e

Status DuLinkListInsert(LinkList *L, int i, ElemType *e)
{
	int j = 1;
	DulNode *p, *q;
	p = *L;
	while (p->next && j < i) {
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i) 
	/*Table length is less than i or i < 1*/
		return ERROR;
	/*p->next Indicates the location of the node to be deleted, marked as q, with q - > priority = = P*/
	q = p->next;
	/*Deleting footer elements is special*/
	if (q->next = NULL) {
		*e = q->data;
		p->next = NULL;
		free(q);
		return OK;
	}
	/*Get node data element*/
	*e = q->data;
	/*Delete node*/
	p->next = q->next;
	q->next->prior = p;
	/*Release node*/
	free(q);
	return OK;
}
	

2.4 creating a two-way linked list by head interpolation

/*Here, it is assumed that the data element is of character type and the storage space is sufficient*/
typedef char ElemType;
void CreateDuLinkList_Head(DuLinkList *L, int n)
{
	DulNode *p;
	int i;
	char ch;
	/*Initialize and create an empty table with only header nodes*/
	*L = (DuLinkList)malloc(sizeof(DulNode));
	(*L)->prior = NULL;
	(*L)->next = NULL;
	/*The insertion of the first node as the footer is special*/
	scanf("%c", &ch);
	p = (DulNode *)malloc(sizeof(DulNode));
	p->data = ch;
	p->prior = *L;
	p->next = NULL;
	(*L)->next = p;
	/*Next, new nodes are generated in turn and inserted into the header*/
	for (i = 1; i < n; i++) {
		scanf("%c", &ch);
		/*You can also read characters with getchar()*/
		p = (DulNode *)malloc(sizeof(DulNode));
		p->data = ch;
		p->proir = *L;
		p->next = (*L)->next;
		(*L)->next->prior = p;
		(*L)->next = p;
	}
}	

2.5 creating bidirectional linked list by tail interpolation

/*Here, it is assumed that the data element is of character type and the storage space is sufficient*/
typedef char ElemType;
void CreateDuLinkList_Tail(DuLinkList *L, int n)
{
	DulNode *p, *q;
	int i;
	char ch;
	/*Initialize and create an empty table with only header nodes*/
	*L = (LinkList)malloc(sizeof(Node));
	p = *L;
	/*p Always a pointer to the tail node*/
	for (i = 0; i < n; i++) {
		scanf("%c", &ch);
		/*You can also read characters with getchar()*/
		q = (Node *)malloc(sizeof(Node));
		q->data = ch;
		q->prior = p;
		q->next = NULL;
		/*p The next pointer points to the new node. The new node is added to the table and becomes the end of the table*/
		p->next = q;
		/*Then the p pointer moves to the position of the new node, that is, the position of the end of the table*/
		p = q;
	}
	/*End of linked list creation*/
	p->next = NULL;
}

So far, all the operations of the two-way linked list have been realized. You can also combine the circular linked list and the two-way linked list to get the two-way circular linked list. The two-way circular linked list can be easily constructed on the basis of the realized circular linked list. Try it yourself! In the next chapter, we will learn the related applications of linked lists