Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Why the circle? In a one-way linked list, to access any node of the list, we traverse from the first node. If we are at any node in the middle of the list, we cannot access the node before the given node. This problem can be solved by slightly changing the structure of single-linked lists. In a one-way linked list, the next part (the pointer to the next node) is NULL. If we use this link to point to the first node, then we can reach the previous node.

In this article, we explained the use of one-way lists to implement and insert nodes in a circular list.

Implementation To implement a circular unidirectional list, we use an external pointer to the last node of the list. If we have a pointer last to the last node, then last -> next will point to the first node.

The pointer last points to node Z and last -> next points to node P.

Why do we use a pointer to the last node instead of the first node? * To insert a node at the beginning, we need to traverse the entire list. In addition, the entire list must be traversed in order to insert at the end. If we use a pointer to the last node instead of the start * pointer, we don’t need to traverse the entire list in either case. Therefore, regardless of the length of the list, insertion at the beginning or end takes a constant time.

You can add nodes in any of the following ways:

  • Insert an empty list
  • Insert at the beginning of the list
  • Insert at the end of the list
  • Insert between nodes

Insert into an empty list initially, when the list is empty, the last pointer will be NULL.

After insertion, T is the last node, so the pointer last points to node T. And T is the first and last node, so T points to itself. Insert a node into an empty list,

struct Node *addToEmpty(struct Node *last, int data)
{
	if(last ! =NULL)
	return last;

	struct Node *temp =
		(struct Node*)malloc(sizeof(struct Node));

	temp -> data = data;
	last = temp;
	temp -> next = last;

	return last;
}
Copy the code

Insert at the beginning of the list To insert a node at the beginning of the list, do the following: \

  1. Create a node, such as T. \
  2. T -> next = last -> next. \
  3. The previous one -> the next one = T.

The function that inserts a node at the beginning of the list,

struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
	return addToEmpty(last, data);

struct Node *temp
		= (struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = last -> next;
last -> next = temp;

return last;
}
Copy the code

Insert at the end of the list To insert a node at the end of the list, do the following:

  1. Create a node, such as T.
  2. Make T -> next = last -> next;
  3. Last -> next = T.
  4. The last = T.

A function that inserts a node at the end of the list

struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
	return addToEmpty(last, data);

struct Node *temp =
		(struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = last -> next;
last -> next = temp;
last = temp;

return last;
}
Copy the code

To insert a node between two nodes, perform the following steps:

  1. Create a node, such as T.
  2. Search for the node after which T is inserted, for example, P.
  3. Make T -> next = P -> next;
  4. P -> next = T.

Suppose we need to insert 12 after the value of 10,

Insert the node function at the end of the List,

struct Node *addAfter(struct Node *last, int data, int item)
{
	if (last == NULL)
	return NULL;

	struct Node *temp, *p;
	p = last -> next;
	do
	{
		if (p ->data == item)
		{
			temp = (struct Node *)malloc(sizeof(struct Node));
			temp -> data = data;
			temp -> next = p -> next;
			p -> next = temp;
			if (p == last)
				last = temp;

			return last;
		}
		p = p -> next;
	} while(p ! = last -> next); cout << item <<" not present in the list." << endl;
	return last;
}
Copy the code

Here is a complete program that uses all of the above methods to create a circular one-way linked list.

#include<bits/stdc++.h>
using namespace std;

struct Node
{
	int data;
	struct Node *next;
};

struct Node *addToEmpty(struct Node *last, int data)
{
	if(last ! =NULL)
	return last;

	struct Node *temp =
		(struct Node*)malloc(sizeof(struct Node));

	temp -> data = data;
	last = temp;

	last -> next = last;

	return last;
}

struct Node *addBegin(struct Node *last, int data)
{
	if (last == NULL)
		return addToEmpty(last, data);

	struct Node *temp =
			(struct Node *)malloc(sizeof(struct Node));

	temp -> data = data;
	temp -> next = last -> next;
	last -> next = temp;

	return last;
}

struct Node *addEnd(struct Node *last, int data)
{
	if (last == NULL)
		return addToEmpty(last, data);
	
	struct Node *temp =
		(struct Node *)malloc(sizeof(struct Node));

	temp -> data = data;
	temp -> next = last -> next;
	last -> next = temp;
	last = temp;

	return last;
}

struct Node *addAfter(struct Node *last, int data, int item)
{
	if (last == NULL)
		return NULL;

	struct Node *temp, *p;
	p = last -> next;
	do
	{
		if (p ->data == item)
		{
			temp = (struct Node *)malloc(sizeof(struct Node));
			temp -> data = data;
			temp -> next = p -> next;
			p -> next = temp;

			if (p == last)
				last = temp;
			return last;
		}
		p = p -> next;
	} while(p ! = last -> next); cout << item <<" not present in the list." << endl;
	return last;

}

void traverse(struct Node *last)
{
	struct Node *p;

	if (last == NULL)
	{
		cout << "List is empty." << endl;
		return;
	}

	p = last -> next;

	do
	{
		cout << p -> data << "";
		p = p -> next;

	}
	while(p ! = last->next); }int main(a)
{
	struct Node *last = NULL;

	last = addToEmpty(last, 6);
	last = addBegin(last, 4);
	last = addBegin(last, 2);
	last = addEnd(last, 8);
	last = addEnd(last, 12);
	last = addAfter(last, 10.8);

	traverse(last);

	return 0;
}
Copy the code

Output:

2 4 6 8 10 12
Copy the code