[Data Structures] Bidirectional Chained Table Explained

When we have finished learning the single chained table, two-way chained table is much simpler, two-way chained table in the head insertion, tail insertion, head deletion, tail deletion, and arbitrary position insertion, arbitrary position deletion than the single-chained table is simple, today, follow the small Zhang together to learn it!

Classification of bi-directional linked tables

bi-directional non-headed linked list

doubly headed circular table

There are also bi-directional headed acyclic linked tables, bi-directional unheaded acyclic linked tables, with an emphasis on using bi-directional headed acyclic linked tables, headed that is, with sentinel bits.

doubly headed circular table

Headed bidirectional circular chain table: the most complex structure, generally used to store data separately. In practice, the data structure used in the chain table is a two-way circular chain table with head. In addition, although the structure of this structure is complex, but the use of code to realize the structure will bring a lot of advantages, the realization of the opposite is simple, after we realize the code will know.

Interface Implementation of Bidirectional Circular Chain Tables

ListNode* ListCreate(int x)//create new node
ListNode* createhead()// Creates a sentinel
void ListPushBack(ListNode* phead, int x)// Tail insert
void SListPrint(ListNode* phead)// Print the list
void SListPushFront(ListNode* phead, int x)// Header
void SListPopBack(ListNode* phead)// Delete tail
void SListPopFront(ListNode* phead)// Header deletion
void SListInsert(ListNode* pos, int x)//pos insert
void SListErase(ListNode* pos)// Delete pos;
ListNode* SListFind(ListNode* phead, int x)//find the first x in the chain table

0. Node structure creation

typedef struct ListNode
{
	int data; // Data
	struct ListNode* next;//next node address
	struct ListNode* prev;//previous node address
}ListNode;

1. Create a new node

ListNode* ListCreate(int x)//create new node
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));// request space for new node
	if (newnode == NULL)
	{
		perror("malloc error");//not requested, malloc returns NULL to newnode
		
	}
	newnode->data = x;// data from new node to x
	newnode->next = NULL;// the address of the next node of the new node is empty
	newnode->prev = NULL;// the address of the previous node of the new node is empty
	return newnode;// the address of the new node to return back to the
}

2. Creation of sentry positions

This sentinel bit serves as the head node of the chain table and holds no data

ListNode* createhead()
{
	ListNode* head = ListCreate(-1);// Sentry bit node's data is given a random -1
	head->next = head;
	head->prev = head;
	return head;//return the head node address of the sentinel bit
}

When there is no new node with data, first let his last node address, and the next off node address are deposited into the HEAD’s own address

3. Tail plug

void ListPushBack(ListNode* phead, int x)// Tail insert
{
	ListNode* newnode = ListCreate(int x);
	ListNode* tail = phead->prev;//record the address of the tail node
	newnode->prev = tail;// the new node's prev holds the address of the tail node -1
	newnode->next = phead;//next of the new node holds the address of the head node's sentinel bit -> 2
	phead->prev = newnode;//prev of the head node holds the address of the new node -> 4
	tail->next = newnode;//next of the tail node holds the address of the new node -> 3

}

Analysis:
Because of the use of tail to record the address of the tail node, so 1, 2, 3, 4 can be switched to any order, if there is no record, remember to save the new node of the prev,next, first, and then modify the head->prev, head->prev->next; to prevent the modification process, the tail node’s address is lost.

The same applies to inserting a new node after the sentinel position

4. Print double linked tables

void SListPrint(ListNode* phead)// Print the list
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
    }
	printf("\n");


}

Analysis: Define a pointer cur traversing the entire chain table, because it is a circular chain table, will certainly point to the sentinel position, the sentinel position node data is not used, so cur pointer from the head node sentinel position of the next node to start traversing until cur==phead, the cycle is over, each time to print cur->data, and then move cur to the next node.

5. Head Plugs

void SListPushFront(ListNode* phead, int x)// Header
{
	ListNode* newnode = ListCreate(x);
	
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;

}

Analysis:
attention (heed): Save newnode->next; and newnode->prev; first.
At this point, if you do 4 first, the address of the head->next becomes the newnode, and the previous address of the head->next is lost.
Another way is to save * next=phead->next; then 1, 2, 3, 4, the order can be switched.

6. Delete the end

void SListPopBack(ListNode* phead)// Delete tail
{
	ListNode* last = phead->prev->prev;//record the address of the last node of the tail node
	phead->prev = last;//head node sentinel bit of prev deposited into last's address
	last->next = phead;//last's next is deposited into phead's address

}

Analysis:When to delete the tail node, we can first record the address of the last node of the tail node, because to delete the tail node, the change is the last node of the tail node lastnext depositphead’s address, thephead’sprev deposit is the address of the last
In addition to the sentinel position there is also a node of the tail deletion of the remaining sentinel position head node, the same applies to the above code

7. Head Deletion

void SListPopFront(ListNode* phead)// Header deletion
{
	ListNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
}

Analysis:First save the next node address of the sentinel bit to next, then deposit next->next in next of phead; deposit next->next->prev in first address of phead

8. The node pointed to by the pos pointer is prepended.

void SListInsert(ListNode* pos, int x)//pos insert
{
	ListNode* newnode = ListCreate(x);//apply for a new node to store the address in the newnode variable
	newnode->next = pos;//the next node of the new node holds the address of the node pointed to by the pos pointer
	newnode->prev = pos->prev;//prev of the new node holds the address of the previous node of the node pointed to by the pos pointer
	pos->prev->next=newnode;//next of the previous node of the node pointed to by the pos pointer saves the node pointed to by the newnode pointer
	pos->prev = newnode;//prev of the node pointed to by the pos pointer holds the address of the node pointed to by the newnode pointer
}

Analysis:

9. Delete the node pointed to by the pos pointer.

void SListErase(ListNode* pos)// Delete pos;
{
	ListNode* last = pos->prev;//record the address of the previous node that the pos pointer points to
	ListNode* next = pos->next;//record the address of the next node to which the pos pointer points to the node
	last->next = next; // Operation 1
	next->prev = last; // Operation 2

}

Analysis:

10. Find the first occurrence of x in the chain table

ListNode* SListFind(ListNode* phead,int x)
{
	ListNode* cur = phead->next;//cur pointer points first to the position of phead's next node
	while (cur ! = phead)// Loop through
	{
		if (cur->data == x)//first found
		{
			return cur; return the address of the node whose data is equal to x



		}
		cur = cur->next;//cur pointer to next node





	}
	return NULL;
}

Analysis: similar to print print the chain table, traversal loop, traversal from the beginning of the phead->next, when cur is not equal to the phead to continue the cycle, if cur->datax, then return the contents of cur, i.e. datax’s node address, the end of the loop is not found, that is, the link table is not equal to x’s node return NULL;

11. Destruction of bi-directional chains

void Destroy(ListNode* phead)
{
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

Analysis, define a pointer cur first point to the next node of the phead, start traversal, first save cur point to the node of the next node’s address to next, and then release the space pointed to by the cur pointer, and then let cur point to the next node’s address has been saved in next, and so on, the cycle of releasing all the nodes, the end of the cycle, the release of sentinel bits.

12. Complete source code

#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
ListNode* ListCreate(int x)//create new node
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc error");
		//return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
ListNode* createhead()
{
	ListNode* head = ListCreate(-1);
	head->next = head;
	head->prev = head;
	return head;
}
void ListPushBack(ListNode* phead, int x)// Tail insert
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	ListNode* tail = phead->prev;
	newnode->prev =tail;
	phead->prev = newnode;
	tail->next = newnode;
	newnode->next = phead;
	

}
void SListPrint(ListNode* phead)// Print the list
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->",cur->data);
		cur = cur->next;
    }
	printf("\n");


}
void SListPushFront(ListNode* phead, int x)// Header
{
	ListNode* newnode = ListCreate(x);
	
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;

}
void SListPopBack(ListNode* phead)// Delete tail
{
	ListNode* last = phead->prev->prev;
	phead->prev = last;
	last->next = phead;

}
void SListPopFront(ListNode* phead)// Header deletion
{
	ListNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
}
void SListInsert(ListNode* pos, int x)//pos insert
{
	ListNode* newnode = ListCreate(x);
	

	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev->next=newnode;
	pos->prev = newnode;
}
void SListErase(ListNode* pos)// Delete pos;
{
	ListNode* last = pos->prev;
	ListNode* next = pos->next;
	last->next = next;
	next->prev = last;

}
ListNode* SListFind(ListNode* phead,int x)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;



		}
		cur = cur->next;





	}
	return NULL;
}
// Destruction of double linked tables
void Destroy(ListNode* phead)
{
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
int main()
{
	ListNode* list;
	list = createhead();
	printf(" Tail insert :");
    ListPushBack(list,1);
	ListPushBack(list,2);
	ListPushBack(list,3);
	ListPushBack(list,4);
	SListPrint(list);
	printf(" Head insert :");
	SListPushFront(list, 8);
	SListPushFront(list, 7);
	SListPushFront(list, 6);
	SListPushFront(list, 5);
	SListPrint(list);
	printf(" Tail deletion :");
	SListPopBack(list);
	SListPopBack(list);
	SListPrint(list);
	printf(" Header deletion :");
	SListPopFront(list);
	SListPopFront(list);
	SListPopFront(list);
	SListPrint(list);
	printf("Inserting pos pointing to the front of the node:");
	SListInsert(list->next->next, 1000);
	SListPrint(list);
	printf("Deleting the node pointed to by pos:");
	SListErase(list->next->next);
	SListPrint(list);
	printf("Finding the position of the first x and printing it:");
	ListNode* p=SListFind(list, 8);
	printf("%d", p->data);
	printf("Modifying the node found:\n");
	p->data = 10000;
	SListPrint(list);
	printf("Destruction prints the data of the next node of the sentinel bit after destruction, if it is a random value it means it has been destroyed:");;
	Destroy(list);
	printf("%d",list->data);
	
	
}

13. Compile and run