C language implementation of sequential list and linked list (single, single cycle and double cycle)

This blog is mainly about the implementation of sequence list and leading node linked list (single linked list, single cycle linked list and double cycle linked list).

The code will also be attached to the last side of the linked list of non leading nodes.
 
 
 
 
1, Sequence table: a sequence table is a linear structure that uses a storage unit with continuous physical addresses to store data elements. For example, commonly used arrays.

1. Definition of sequence table

typedef struct Seqlist
{
	size_t size;//count
	size_t capacity;//capacity
	ElementType *base;//Data type, ElementType=int. the macro replacement here is to facilitate the storage of different data. You only need to change the macro
}Seqlist;

 
 
 
2. Initialization of sequence table

void SeqlistInit(Seqlist *plist)
{
	assert(plist != NULL);
	plist->capacity = SEQNUMBER;//Size of capacity, using macros
	plist->size = 0;
	plist->base = (ElementType *)malloc(sizeof(ElementType)*SEQNUMBER);
}

 
 
 
3. Addition of sequence table: head insertion, tail insertion, position insertion and value insertion

void SeqlistPushFront(Seqlist *plist, ElementType x)//Head insert
{
	assert(plist != NULL);
	if (IsFull(plist))//Here, a function is called to determine whether the size and capacity are equal
	{
		printf("The sequence table is full,%d Cannot insert\n", x);
		return;
	}
	for (size_t i = plist->size; i > 0; i--)//Method drawing explanation
	{
		plist->base[i] = plist->base[i - 1];
	}
	plist->base[0] = x;//Put your head in the front
	plist->size++;//The count should be increased after insertion
}

void SeqlistPushBack(Seqlist *plist, ElementType x)//Tail insertion
{
	assert(plist != NULL);
	if (IsFull(plist) && !SeqlistInc(plist))
	{
		printf("The sequence table is full,%d Cannot insert\n", x);
		return;
	}
	plist->base[plist->size] = x;//Just insert it directly
	plist->size++;//The count should be increased after insertion
}


void SeqlistInsertPos(Seqlist *plist, int pos, ElementType x)//Position insertion
{
	assert(plist != NULL);
	if (IsFull(plist))//Cannot insert when full
	{
		printf("The sequence table is full,%d Cannot insert\n", x);
		return;
	}
	if ( pos<0 || pos>(int)plist->size)//If the position is wrong, the front of the sequence table is empty. It cannot be inserted where the front is empty (except the first one). It should be continuous
	{
		printf("Enter the location of the%d Illegal,%d Cannot insert\n",pos,x);
		return;
	}
	for (size_t i = plist->size; i > (size_t) pos; i--)//Correct position, insert
	{
		plist->base[i] = plist->base[i - 1];
	}
	plist->base[pos] = x;
	plist->size++;
}


void SeqlistInsertVal(Seqlist *plist, ElementType x)//Value insertion, sort before insertion
{
	assert(plist != NULL);
	qsort(plist->base, plist->size, sizeof(ElementType), cmp);//The library function, qsort, is used here
	if (IsFull(plist) && !SeqlistInc(plist))
	{
		printf("The sequence table is full,%d Cannot insert\n", x);
		return;
	}
	size_t end = plist->size - 1;
	while (end >= 0 && x < plist->base[end])
	{
		plist->base[end + 1] = plist->base[end];
		end--;
	}
	plist->base[end + 1] = x;
	plist->size++;
}


Sequence table insertion: the basic idea is to move the data back and finally overwrite the values at the insertion place.
 
 
 
4 . Deletion of sequence table: header deletion, tail deletion and position deletion

void SeqlistPopFront(Seqlist *plist)//Header deletion
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		printf("The data is empty and cannot be deleted\n");
		return;
	}
	for (size_t i = 0; i < plist->size; i++)
	{
		plist->base[i] = plist->base[i + 1];//The following data is overwritten forward
	}
	plist->size--;//The number of elements decreases
}

void SeqlistPopBack(Seqlist *plist)//Tail deletion
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		printf("The data is empty and cannot be deleted\n");
		return;
	}
	plist->size--;//The number of direct is reduced and the last position is set to invalid
}

void SeqlistEraseBack(Seqlist *plist, int pos)//Location deletion
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		printf("The sequence table is empty and cannot be deleted!\n");
		return;
	}
	if (pos < 0 || pos > (int)plist->size)
	{
		printf("Enter the location of the%d Illegal, cannot delete\n",pos);
		return;
	}
	for (size_t i = (size_t)pos; i < plist->size ; i++)
	{
		plist->base[i] = plist->base[i + 1];//The following data is overwritten forward
	}
	plist->size--;//The number of elements decreases
}

Deletion of sequence table: the basic idea is to overwrite the following data one by one, and finally reduce the number.
 
 
 
5. Query of sequence table: location search and binary search

int SeqlistFind(Seqlist *plist, ElementType x)//Location search
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		printf("Data is empty, unable to find!\n");
	}
	size_t pos = 0;
	while (pos < plist->size && x != plist->base[pos])//The location should be legal. If the data is not equal to, continue to execute
	{
		pos++;
	}
	if (pos == plist->size)//After jumping out, if the location is illegal, the data must not exist
	{
		return -1;
	}
	return pos;//Data found, return to location
}

void SeqlistBinaryFind(Seqlist *plist, ElementType x)
{
	assert(plist != NULL);
	size_t start = 0;
	size_t end = plist->size;
	size_t mid = 0;
	while (start <= end)//Binary search
	{
		mid = (start + end) / 2;
		if (x < plist->base[mid])//Smaller than the middle, go left and end becomes mid-1
		{
			end = mid - 1;
		}
		else if (x > plist->base[mid])//Larger than the middle, go to the right, and start becomes mid+1
		{
			start = mid + 1;
		}
		else//eureka
		{
			printf("Data search succeeded, as follows:>%d\n", plist->base[mid]);
			return;
		}
	}
	printf("Failed to find data%d non-existent\n", x);//Jump out of the loop, that is, the data does not exist
}

 
 
 
5. The order of table space can be directly sorted, and the order of table space can be exchanged

void SeqlistSort(Seqlist *plist)//For data sorting, qsort is used here
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		printf("The data cannot be sorted because it is empty!\n");
	}
	qsort(plist->base, plist->size, sizeof(ElementType), cmp);//Use the qsort library function directly
}
//Qsort needs to write a comparison function and pass it as a parameter to qsort
int cmp(const void *a, const void *b)
{
	return *(ElementType *)a - *(ElementType *)b;
}

The bubbling method can also be used here to compare and exchange.
 
 
 
6. Reverse sequence table: reverse sequence table

void SeqlistReverse(Seqlist *plist)//Data reverse order
{
	assert(plist != NULL);
	size_t start = 0;
	size_t end = plist->size - 1;
	while (start < end)//Value exchange for each bit
	{
		plist->base[end] ^= plist->base[start];
		plist->base[start] ^= plist->base[end];
		plist->base[end] ^= plist->base[start];
		start++, end--;
	}
}

Data XOR will exchange bits, which can achieve the effect of data exchange.
For example:

 
 
 
7. Delete duplicate elements in the sequence table

//For example: 1 2 2 2 3 3 4
void SeqlistEraseAll(Seqlist *plist,ElementType x)//Delete the specified element
{
	assert(plist != NULL);
	if (plist->size <= 0)
	{
		return;
	}
	SeqlistSort(plist);//sort
	size_t pos = SeqlistFind(plist, x);//Find the first place to appear
	size_t count = 0;//How many counts
	int tmp = 0;
	for (size_t i = pos; i < plist->size; i++)
	{
		tmp = 1;//Flag bit
		if (x == plist->base[i])
		{
			tmp = 0;
			count++;
		}
		if (tmp == 1)
		{
			break;//When you get here, it means that there is no equality. Jump out
		}
	}
	tmp = count;//Number of reserved
	int number = count + pos;//Remember where to start the replacement
	for (; count > 0; count--)
	{
		plist->base[pos++] = plist->base[number++];//The following data is overwritten to the front
	}
	plist->base[pos-1] = plist->base[number-1];//After the cycle is completed, it will be replaced less once
	plist->size -= tmp;
}

Advantages of sequence table:

  1. Easy to implement
  2. Random access

What if we need more space than our capacity?
Dynamic development can be used to reopen space, such as:

bool SeqlistInc(Seqlist *plist)//Capacity expansion
{
	assert(plist != NULL);
	ElementType *s = (ElementType *)realloc(plist->base, 2 * plist->capacity * sizeof(ElementType));
	if (NULL != s)
	{
		plist->base = s;
		plist->capacity = 2 * plist->capacity;
		return true;
	}
	return false;
}

However, there will also be disadvantages. During dynamic development, the space is doubled. If only the capacity of one original space needs to be exceeded, it will cause a great waste of space.

 
 
 
 
2, Single linked list: linked list is a discontinuous and non sequential storage structure in physical storage structure. The logical order of data elements is realized through the pointer link order in the linked list.

The following is a single linked list of the leading nodes
 
 
 
1. Definition of single linked list:

typedef struct SlistNode
{
	ElementType data;//data
	struct SlistNode *next;//Pointer to next
}SlistNode;

 
 
 
2. Initialization of single linked list:

void SlistIniHead(SList *phead)
{
	assert(phead != NULL);
	(*phead) = (SlistNode*)malloc(sizeof(SlistNode));//With a header node, the header node does not put data and cannot be changed
	(*phead)->next = NULL;
}

 
 
 
3. Addition of single linked list: head insertion, tail insertion and value insertion

void SlistHeadPushFront(SList *phead, ElementType x)//Header node
{
	assert(phead != NULL);
	SlistNode *p = (SlistNode *)malloc(sizeof(SlistNode));//Application space
	assert(p != NULL);
	p->data = x;
	SlistNode *q = *phead;
	p->next = q->next;//The next node of p is the next node of the header
	q->next = p;//The next in the head is p
}

void SlistHeadPushBack(SList *phead, ElementType x)//Headed node
{
	assert(phead != NULL);
	SlistNode *q = *phead;
	while (q->next != NULL)//Last node found
	{
		q = q->next;
	}
	SlistNode *p = (SlistNode *)malloc(sizeof(SlistNode));
	p->data = x;
	p->next = NULL;//The tail is empty
	q->next = p;//The front node points to p
}

void SlistHeadInsertVal(SList *phead, ElementType x)//Value insertion
{
	assert(phead != NULL);
	SlistHeadSort(phead);//Sort first
	SlistNode *p = (SlistNode *)malloc(sizeof(SlistNode));
	assert(p != NULL);
	p->data = x;
	SlistNode *q = (*phead)->next,*prev = NULL;
	while (q != NULL && q->data < x)//Find where to insert
	{
		prev = q;//Precursor node
		q = q->next;
	}
	if (prev == NULL)
	{
		p->next = (*phead)->next;
		(*phead)->next = p;
	}
	else
	{
		p->next = prev->next;
		prev->next = p;
	}
}

In value insertion, because the linked list does not support random access, position insertion cannot be carried out.
 
 
 
4. Deletion of single linked list: header deletion, tail deletion and value deletion

void SlistHeadPopFront(SList *phead)
{
	assert(phead != NULL);
	if ((*phead)->next == NULL)//The linked list is empty and cannot be deleted
	{
		return;
	}
	SlistNode *p = (*phead)->next;//Delete the next of the head node and point to the next of the first node
	(*phead)->next = p->next;
	free(p);//Release, because the nodes of the linked list are opened up by malloc, all need to be released
}

void SlistHeadPopBack(SList *phead)//Tail deletion
{
	assert(phead != NULL);
	if ((*phead)->next == NULL)//The linked list is empty and cannot be deleted
	{
		return;
	}
	SlistNode *p = (*phead)->next;
	SlistNode *prev = NULL;//precursor
	while (p->next != NULL)
	{
		prev = p;
		p = p->next;
	}
	prev->next = NULL;//The next setting of the precursor is empty
	free(p);//Release tail node
}

void SlistHeadEraseVal(SList *phead, ElementType x)//Value deletion
{
	assert(phead != NULL);
	SlistNode *p = SlistHeadFind(phead, x);//Locate the location where the value was deleted
	if (p == NULL)
	{
		printf("Data does not exist and cannot be deleted!\n");
		return;
	}
	SlistNode *q = (*phead)->next,*prev;
	if (q == p)//The first node is the released node, which changes the direction of the head node
	{
		(*phead)->next = q->next;
		free(q);
		return;
	}
	else
	{
		while (q != NULL)
		{
			prev = q;//precursor
			q = q->next;
			if (q == p)//Equal
			{
				prev->next = q->next;
				free(q);
				return;
			}
		}
	}
}

In the single linked list deletion, whether it is header deletion, tail deletion or value deletion. You cannot change the head node, and you should pay attention to whether the deleted node is the next node of the head node. If you delete the tail node, you should locate the predecessor and empty the successor of the predecessor. When deleting a value, you can directly find the location of the deleted value to delete.
 
 
 
5. Single linked list query: find the value and find the return location

SlistNode *SlistHeadFind(SList *phead, ElementType x)
{
	assert(phead != NULL);
	SlistNode *p = (*phead)->next;
	while (p != NULL)//Circular search, binary search cannot be done here, because the linked list does not support random access
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->next;
	}
	return NULL;
}

 
 
 
6. Sorting of single linked list: the sorting of single linked list is different from that of sequential list. The sequential list can exchange values directly. In the linked list, the direction between nodes is generally changed to achieve the purpose of sorting.

void SlistHeadSort(SList *phead)
{
	assert(phead != NULL);
	SlistNode *tmp = (*phead)->next,*p = (*phead)->next, *prev = NULL;//p is the next node of the head node
	SlistNode *q = p->next;//q is the next node of p
	p->next = NULL;//Point next of p to disconnect
	while (q != NULL)
	{
		p = q;
		q = q->next;
		while (tmp != NULL && p->data > tmp->data)
		{
			prev = tmp;
			tmp = tmp->next;
		}
		if (prev == NULL)//If the precursor is empty, it means that the value of p is lower than that of tmp, and the next node of the head node needs to be replaced
		{
			p->next = (*phead)->next;
			(*phead)->next = p;
		}
		else
		{
			p->next = prev->next;
			prev->next = p;
		}
		tmp = (*phead)->next;//tmp continues to point to the next pointer of the header
		prev = NULL;
	}
}

At first, there are such nodes:

Disconnect the tail pointer of p:

Judge the value of tmp node and the value of p one by one. Here is also a precursor pointer to determine the insertion position of p node when the data of p node is smaller than tmp data.
 
 
 
7. Reverse of single linked list: similar to sorting, it is also directly disconnected, but without comparison, it is OK to exchange directly.

void SlistHeadReverse(SList *phead)//Inversion
{
	assert(phead != NULL);
	SlistNode *p = (*phead)->next;
	SlistNode *q = p->next;
	p->next = NULL;
	while (q != NULL)
	{
		p = q;
		q = q->next;
		p->next = (*phead)->next;
		(*phead)->next = p;
	}
}

 
 
 
8. Delete duplicate values in the single linked list

void SlistHeadEraseAll(SList *phead, ElementType x)
{
	assert(phead != NULL);
	SlistHeadSort(phead);//Sort first
	SlistNode *p = (*phead)->next, *tmp = NULL, *prev = *phead;
	while (p != SlistHeadFind(phead, x))//Find the first node with x, and prev is equal to the precursor of this node
	{
		prev = p;
		p = p->next;
	}
	while (p != NULL && p->data == x)//Release one by one
	{
		tmp = p;
		p = p->next;
		free(tmp);
	}
	prev->next = p;//The next node of the precursor is not equal to x
}

In the single linked list, because the transformation of the head node is not considered, the implementation should be simpler. If there is no head node, the change of the first node should be considered in the reverse sorting. And the linked list cannot be accessed randomly.

 
 
 
 
3, Single circular linked list: similar to single linked list, but the point at the tail node is not empty, but points to the head node again.

 
 
 
1. Creation of single cycle linked list:

typedef struct SCListNode
{
	ElementType data;
	struct SCListNode *next;
}SCListNode;

typedef SCListNode* SCList;

 
 
 
2. Initialization of single cycle linked list:

void SCListHeadIni(SCList *phead)//Linked list initialization
{
	*phead = _BuyNode(0);//Here, this buynode is a function defined when opening up nodes
	(*phead)->next = *phead;
}

SCListNode *_BuyNode(ElementType v)
{
	SCListNode *_s = (SCListNode *)malloc(sizeof(SCListNode));
	_s->data = v;
	_s->next = _s;
	return _s;
}

 
 
 
3. Addition of single cycle linked list: head insertion, tail insertion and value insertion

void SCListHeadPushFront(SCList *phead, ElementType x)//Head insertion
{
	assert(phead != NULL);
	SCListNode *p = _BuyNode(x);
	assert(p != NULL);
	SCListNode *head = *phead;
	if (head->next != *phead)//Determine whether the header node is a single loop
	{
		p->next = (*phead)->next;
		(*phead)->next = p;
	}
	else
	{
		p->next = *phead;
		(*phead)->next = p;
	}
}

void SCListHeadPushBack(SCList *phead, ElementType x)//Tail interpolation
{
	assert(phead != NULL);
	SCListNode *p = _BuyNode(x);
	assert(p != NULL);
	SCListNode *head = (*phead)->next;
	while (head->next != *phead)//Last node found
	{
		head = head->next;
	}
	head->next = p;
	p->next = *phead;//Node next pointing head
}

void SCListHeadInsertVal(SCList *phead, ElementType x)//Insert, sort before insert
{
	assert(phead != NULL);
	SCListHeadSort(phead);
	SCListNode *s = _BuyNode(x);
	SCListNode *p = (*phead)->next, *prev = NULL;
	while (p != *phead && p->data < x)//Find insertion location
	{
		prev = p;
		p = p->next;
	}
	if (prev == NULL)//The first position can be inserted
	{
		s->next = (*phead)->next;
		(*phead)->next = s;
	}
	else//The insertion position is found, and there is also a precursor. You can insert it
	{
		s->next = prev->next;
		prev->next = s;
	}
}

 
 
 
4. Deletion of single cycle linked list: header deletion, tail deletion and value deletion

void SCListHeadPopFront(SCList *phead)//Header deletion
{
	assert(phead != NULL);
	SCListNode *p = (*phead)->next;
	if (p == *phead)//There is only one header node and cannot be deleted
	{
		return;
	}
	(*phead)->next = p->next;//Change direction
	free(p);
}

void SCListHeadPopBack(SCList *phead)//Tail deletion
{
	assert(phead != NULL);
	SCListNode *p = (*phead)->next, *prev = NULL;
	if (p == *phead)//Only header nodes
	{
		return;
	}
	while (p->next != *phead)//Find tail node
	{
		prev = p;
		p = p->next;
	}
	if (prev == NULL)//There are only two nodes, and the replacement head node points to
	{
		(*phead)->next = *phead;
		free(p);
	}
	else 
	{
		prev->next = *phead;//Change direction, release
		free(p);
	}
}

void SCListHeadEraseVal(SCList *phead, ElementType x)//delete
{
	assert(phead != NULL);
	SCListNode *p = (*phead)->next, *prev=NULL;
	if (p == *phead)
	{
		return;
	}
	while (p != *phead && p->data != x)//Find the location where you want to delete the node
	{
		prev = p;
		p = p->next;
	}
	if (prev == NULL)//Next deletion of head node
	{
		(*phead)->next = p->next;
		free(p);
	}
	else//Find the middle deletion location
	{
		prev->next = p->next;
		free(p);
	}
}

When deleting the single cycle linked list, pay attention to the tail node. When deleting it finally, point the precursor to the head node again.

 
 
 
5. Single cycle linked list query: return node location

SCListNode* SCListHeadFind(SCList *phead, ElementType x)//Find data
{
	assert(phead != NULL);
	SCListNode *p = (*phead)->next;
	while (p != *phead)
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->next;
	}
	return NULL;
}

 
 
 
6. Sorting of single cycle linked list: change the order by pointing between nodes

void SCListHeadSort(SCList *phead)//Linked list sorting
{
	assert(phead != NULL);
	if (SCListLength(phead) <= 1)
	{
		return;
	}
	SCListNode *p = (*phead)->next,*tmp= (*phead)->next,*prev=NULL;
	SCListNode *q = p->next;
	p->next = *phead;//Disconnect and point to the head
	while (q != *phead)
	{
		p = q;
		q = q->next;
		while (tmp != *phead && p->data > tmp->data)//Find insertion location
		{
			prev = tmp;
			tmp = tmp->next;
		}
		if (prev == NULL)//First position insert
		{
			p->next = (*phead)->next;
			(*phead)->next = p;
		}
		else//Middle insertion
		{
			p->next = prev->next;
			prev->next = p;
		}
		tmp = (*phead)->next;//tmp continues to point to the next in the header
		prev = NULL;
	}
}

 
 
 
7. Reverse of single cycle linked list:

void SCListHeadReverse(SCList *phead)//Reverse linked list
{
	assert(phead != NULL);
	if (SCListLength(phead) <= 1)
	{
		return;
	}
	SCListNode *p = (*phead)->next;
	SCListNode *q = p->next;
	p->next = *phead;//to break off
	while (q != *phead)
	{
		p = q;
		q = q->next;
		p->next = (*phead)->next;//Change direction
		(*phead)->next = p;
	}
}

 
 
 
8. Delete duplicate values in the single cycle linked list: sort first

void SCListHeadEraseAll(SCList *phead, ElementType x)//Clear duplicate elements
{
	assert(phead != NULL);
	SCListHeadSort(phead);//sort
	SCListNode *p = (*phead)->next, *prev = NULL,*q=NULL;
	while (p != SCListHeadFind(phead, x))//Find the first clear location
	{
		prev = p;
		p = p->next;
	}
	while (p != *phead && p->data == x)//eliminate
	{
		q = p;
		p = p->next;
		free(q);
	}
	if (prev == NULL)//The first one can be cleared
	{
		(*phead)->next = p;
	}
	else//Middle position
	{
		prev->next = p;
	}
}

In the single cycle linked list, it should be noted that the last node must cycle back, otherwise it will lead to an error.

 
 
 
 
4, Double cycle linked list: double cycle linked list is that each node has two pointers, a precursor and a successor.

Double cycle linked list of leading nodes:

 
 
 
1. Definition of double cycle linked list:

typedef struct DCListNode
{
	ElementType data;
	struct DCListNode *prev;//precursor
	struct DCListNode *next;//Successor
}DCListNode;

typedef DCListNode* DCList;

 
 
 
2. Initialization of double cycle linked list

void DCListHeadIni(DCList *phead)//Linked list initialization
{
	*phead = _BuyNode(0);//Head node
}

DCListNode *_BuyNode(ElementType v)
{
	DCListNode *_s = (DCListNode *)malloc(sizeof(DCListNode));
	_s->data = v;
	_s->next = _s->prev = _s;
	return _s;
}

 
 
 
3. Addition of double cycle linked list: head insertion, tail insertion and value insertion

void DCListHeadPushFront(DCList *phead, ElementType x)//Head insertion
{
	assert(phead != NULL);
	DCListNode *p = *phead;
	DCListNode *s = _BuyNode(x);
	assert(s != NULL);
	s->next = p->next;//The successor of the inserted node is equal to the successor of the head node
	s->prev = p;//Precursor equals header node
	s->next->prev = s;//The precursor of the next node is equal to s
	s->prev->next = s;//The successor of the precursor is equal to s
}

void DCListHeadPushBack(DCList *phead, ElementType x)//Tail interpolation
{
	assert(phead != NULL);
	DCListNode *p = *phead;
	DCListNode *s = _BuyNode(x);
	assert(s != NULL);
	s->prev = p->prev;//The precursor of the inserted node is equal to the precursor of the head node
	s->next = p;//The successor of the inserted node is equal to the head node
	s->prev->next = s;//The successor of s precursor is equal to s
	s->next->prev = s;s The successor precursor of is equal to s
}

void DCListHeadInsertVal(DCList *phead, ElementType x)//Insert, sort before insert
{
	assert(phead != NULL);
	DCListHeadSort(phead);//sort
	DCListNode *s = _BuyNode(x);
	DCListNode *p = (*phead)->next;
	DCListNode *q = p->next;
	while (p->data < x && p != *phead)//Find insertion location
	{
		p = p->next;
	}
	s->next = p;//The successor of the inserted node is equal to p
	s->prev = p->prev;//The precursor of s is equal to the precursor of p
	s->prev->next = s;//The successor of the precursor of S is equal to s
	s->next->prev = s;//The predecessor of S is equal to s
}


Because the bidirectional circular linked list has two pointers of predecessor and successor, it is particularly convenient to realize it. You only need to know the node, you can find the predecessor and successor of the node, which is well realized in insertion, deletion and sorting.

 
 
 
4. Deletion of double cycle linked list: header deletion, tail deletion and value deletion

void DCListHeadPopFront(DCList *phead)//Header deletion
{
	assert(phead != NULL);
	DCListNode *p = (*phead)->next;
	if (p != *phead)
	{
		p->prev->next = p->next;//Direct change of direction
		p->next->prev = p->prev;
		free(p);
	}
}

void DCListHeadPopBack(DCList *phead)//Tail deletion
{
	assert(phead != NULL);
	DCListNode *p = (*phead)->prev;
	if (p != *phead)
	{
		p->prev->next = p->next;//Change direction
		p->next->prev = p->prev;
		free(p);
	}
}

void DCListHeadEraseVal(DCList *phead, ElementType x)//delete
{
	assert(phead != NULL);
	DCListNode *p = DCListHeadFind(phead, x);//Find the location of this node
	if (p == NULL)
	{
		return;
	}
	p->prev->next = p->next;//delete
	p->next->prev = p->prev;
	free(p);
}

To delete a node in a double cycle linked list, you only need to locate the node, and then let the successor of the predecessor point to the successor, and the successor predecessor point to the predecessor.

 
 
 
5. Double cycle linked list query: value query, return position

DCListNode* DCListHeadFind(DCList *phead, ElementType x)//Find data
{
	assert(phead != NULL);
	DCListNode *p = (*phead)->next;
	while (p->data != x && p != *phead)//Find location
	{
		p = p->next;
	}
	if (p == *phead)//Is the header node and returns null
	{
		return NULL;
	}
	return p;
}

 
 
 
6. Sorting of double cycle linked list:

void DCListHeadSort(DCList *phead)//Linked list sorting
{
	assert(phead != NULL);
	if (DCListHeadLength(phead) <= 1)
	{
		return;
	}
	DCListNode *p = (*phead)->next;
	DCListNode *q = p->next;
	p->next = p->prev;//to break off
	p->prev->prev = p;//Disconnect, two nodes self cycle
	while (q != *phead)
	{
		p = q;
		q = q->next;
		DCListNode *tmp = (*phead)->next;
		while (p->data > tmp->data && tmp != *phead)//Find insertion location
		{
			tmp = tmp->next;
		}
		p->prev = tmp->prev;//Insert
		p->next = tmp;
		p->prev->next = p;
		p->next->prev = p;
	}

}

The sorting of this piece is the same as that of value insertion. First disconnect the two, then compare the size of the subsequent order value, and then insert.

 
 
 
7. Reverse of double cycle linked list:

void DCListHeadReverse(DCList *phead)//Reverse linked list
{
	assert(phead != NULL);
	if (DCListHeadLength(phead) <= 1)
	{
		return;
	}
	DCListNode *p = (*phead)->next;
	DCListNode *q = p->next;
	p->next = p->prev;
	p->prev->prev = p;//Disconnect, two nodes self cycle
	while (q != *phead)
	{
		p = q;
		q = q->next;
		p->prev = *phead;//insert
		p->next = (*phead)->next;
		p->prev->next = p;
		p->next->prev = p;
	}
}

The reverse of this block is similar to the head insertion method, which directly inserts the node behind the head node.

 
 
 
8. Delete the value of double cycle repetition:

void DCListHeadEraseAll(DCList *phead, ElementType x)//Clear the same elements as the input value in the linked list
{
	assert(phead != NULL);
	DCListHeadSort(phead);//sort
	DCListNode *p = (*phead)->next;
	if (p == *phead)//There is only one header node
	{
		return;
	}
	while (p->data != x && p != *phead)//Find delete location
	{
		p = p->next;
	}
	while (p->data == x)//If the node values are equal, it will be deleted all the time
	{
		DCListNode *tmp = NULL;;
		p->prev->next = p->next;//Change the direction of the precursor
		p->next->prev = p->prev;//Changed direction
		tmp = p;
		p = p->next;
		free(tmp);//release
	}
}

The implementation of double cycle linked list is very convenient, but the structure is the most complex.

If necessary, you can download the code here (the linked list has headless nodes): code
 
 
  
 
  
 
  
 
 
 
 
 
Conclusion: it is convenient to implement the sequence table, but the capacity is limited. If more space is opened up, it will cause a waste of space. In the linked list, there are many structures, including headless node linked list, single, single cycle, double, double cycle. The linked list is more commonly used is the headless node single linked list and the lead node double cycle linked list.

Posted by netcoord99 on Wed, 25 May 2022 17:48:50 +0300