Each node of a unidirectional (singly linked) circular list (SCL) contains one pointer field to the next node. The last node pointer field contains the address of the root element.

The OC node can be represented as a structure similar to a singly linked linear list

struct list
{
intfield; // data field
struct list *ptr; // pointer to the next element
};

The main actions performed on the elements of the CCS:

• List initialization
• Adding a node to the list
• Removing a node from the list
• Displaying List Items
• Interchange of two list nodes

Because the list is cyclic, there is no need to implement a separate function to remove the root of the list.

List initialization is designed to create a root node of the list, whose pointer to the next element field contains the address of the root element itself.

1
2
3
4
5
6
7
8
9

struct list * init(int a) // a- value of the first node
{
struct list *lst;
// allocate memory for the root of the list
lst = (struct list*)malloc(sizeof (struct list));
lst->field = a;
lst->ptr = lst; // pointer to the root node itself
return(lst);
}

Adding a node to the CSC

The function to add a node to the list takes two arguments:

• Pointer to the element to be added after
• The data for the element to be added.

The procedure for adding an element can be represented by the following diagram:


Adding an element to the CCA includes the following steps:

• creating the node to be added and filling in its data field;
• reinstalling the pointer of the node preceding the added one to the added node;
• setting the pointer of the added node to the next node (the one pointed to by the previous node).

Thus, the function of adding a node to the CCS has a form completely similar to the function of adding a node to a singly linked linear list:

1
2
3
4
5
6
7
8
9
10

struct list * addelem(list *lst, int number)
{
struct list *temp, *p;
temp = (struct list*)malloc(sizeof (list));
p = lst->ptr; // store a pointer to the next element
lst->ptr = temp; // the previous node points to the one being created
temp->field = number; // saving the data field of the added node
temp->ptr = p; // created node points to the next element
return(temp);
}

The return value of the function is the address of the added node.

Deleting a CCA node

The pointer to the node to be deleted is passed as arguments to the deletion function of the CCA node. Since the list is cyclic, there is no need to pass a pointer to the root of the list.

The function returns a pointer to the node following the one being removed.

Removing a node can be represented by the following scheme:

Deleting a CCA node includes the following steps:

• setting the pointer of the previous node to the node following the one being deleted;
• freeing the memory of the node to be deleted.

1
2
3
4
5
6
7
8
9
10
11
12

struct list * deletelem(list *lst)
{
struct list *temp;
temp=lst;
while (temp->ptr != lst) // loop through the list starting from the root
{ // until we find the node preceding lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // rearrange the pointer
free(lst); // free the memory of the node to be deleted
return(temp);
}

The output of the elements of the CCA

The function of outputting the elements of the CCS is similar to the function for the RL, except for the condition for terminating the bypass of the elements.
As an argument, a pointer to the root of the list is passed to the element output function.
The function performs a sequential traversal of all nodes with the output of their values.

1
2
3
4
5
6
7
8
9

void listprint(list*lst)
{
struct list *p;
p = lst;
do(
printf("%d " , p->field); // output value of node p
p = p->ptr; // move to the next node
) while (p != lst); // traversal termination condition
}

For CSC, you can also call the function to display the elements of the list starting from any node.

Interchange of OCS nodes

As arguments, the CCA interchange function takes two pointers for the exchanged nodes, as well as a pointer to the root of the list. The function returns the address of the root node of the list.

The interchange of nodes of the list is carried out by reinstalling the pointers. To do this, you must define the predecessor and successor nodes for each replaced. In this case, two situations are possible:

• the nodes being replaced are neighbors;
• the replaced nodes are not neighbors, that is, there is at least one element between them.

When replacing neighboring nodes, resetting the pointers looks like this:


When replacing nodes that are not neighbors, resetting the pointers looks like this:

When reinstalling pointers, there is no need to check the root node (unlike the similar function for lst2->ptr = lst1;
lst1->ptr = next2;
prev1->ptr = lst2;
}
else if (lst1 == next2)
{
// exchange neighboring nodes
lst1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst2;
}
else
{
// exchange distant nodes
prev1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst1;
lst1->ptr = next2;
}
if (lst1 == head)
return(lst2);
if (lst2 == head)
return(lst1);
return(head);
}

Annotation: The lecture discusses definitions, ways of declaring, initialization and features of using circular lists, deques, red-black trees in solving problems, gives examples of solving problems for processing circular lists, deques, red-black trees.

The purpose of the lecture: learn algorithms and techniques for working with dynamic data structures, learn how to solve problems using dynamic data structures and algorithms for working with them in C++.

Structured Data Types, such as arrays, sets, records, are static structures, since their sizes remain unchanged during the entire execution of the program. It is often required that data structures change their sizes in the course of solving a problem. Such data structures are called dynamic, they include stacks, queues, lists, trees, and others. Describing dynamic structures using arrays, records, and files leads to wasteful use of memory and increases the time for solving problems.

Using structural types, pointers and dynamic variables, you can create a variety of dynamic memory structures. Features of pointers in the C ++ language allow you to build dynamic memory structures based on statically declared variables or on a mixture of static and dynamic variables. The idea of ​​organizing all dynamic structures is the same. Some structural type S is defined, one or more fields of which are declared as pointers to the same or some other structural type. The program declares a variable d of type S or a variable of type pointer to S in the case of a fully dynamic structure creation. The name of this variable is used as the name of the "root" (parent name) of the dynamic structure during program execution. When executing the program, as the dynamic structure is being built, dynamic variables of the corresponding types and are linked by reference starting with the variable d or the first dynamic variable, the pointer to which is contained in the variable d . This approach allows you to create a dynamic structure with any topology.

Cyclic (ring) lists

Cyclic (ring) list- it data structure, which is a sequence of elements, the last element of which contains a pointer to the first element of the list , and the first (in the case bidirectional list) to the last one.

The main feature of such an organization is that there are no elements in this list containing nulls, and, therefore, it is impossible to select extreme elements.

Circular lists, like linear lists, can be unidirectional and bidirectional.

Looks like a linear singly-linked list, but its last element contains a pointer linking it to the first element (Figure 32.1).

To completely traverse such a list, it is enough to have a pointer to an arbitrary element, and not to the first one, as in a linear singly-directed list. The concept of the "first" element here is rather conditional and is not always required. Although sometimes it is useful to highlight some element as "first" by setting a special pointer to it. This is required, for example, to prevent "looping" when viewing a list.

Rice. 32.1.

Basic operations carried out with a cyclic singly-directed list:

• list creation;
• printing (viewing) the list;
• inserting an element into a list;
• deleting an element from the list;
• search for an element in the list;
• checking if the list is empty;
• deleting the list.

To describe the algorithms for these basic operations, we will use the same declarations as for a linear singly linked list.

Let us present the functions of the listed basic operations when working with a cyclic singly-directed list.

//create a cyclic singly-directed list void Make_Circle_Single_List(int n, Circle_Single_List** Head,Circle_Single_List* Loop)( if (n > 0) ( (*Head) = new Circle_Single_List(); //allocate memory for a new element if (Loop = = NULL) Loop = (*Head); cout<< "Введите значение "; cin >> (*Head)->Data; //enter the value of the information field (*Head)->Next=NULL;//zero the address field Make_Circle_Single_List(n-1,&((*Head)->Next),Loop); ) else ( (*Head) = Loop; ) ) //Printing a circular one-way list void Print_Circle_Single_List(Circle_Single_List* Head) ( Circle_Single_List* ptr=Head; //auxiliary pointer do ( cout<< ptr->Data<< "\t"; ptr=ptr-> << "\n"; } /*вставка элемента после заданного номера в циклический однонаправленный список*/ Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head, int Number, int DataItem){ Circle_Single_List *Current = Head; //встали на первый элемент Circle_Single_List *NewItem = new(Circle_Single_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) (//list is empty NewItem->Next = NewItem; Head = NewItem; ) else (//list is not empty for (int i = 1; i< Number; i++) Current = Current->next; NewItem->Next = Current->Next; Current->Next = NewItem; ) return Head; ) /*remove the item with the given number from the circular singly list*/ Circle_Single_List* Delete_Item_Circle_Single_List (Circle_Single_List* Head, int Number)( if (Head != NULL)( Circle_Single_List *Current = Head; if (Head->< Number; i++) Current = Current->next; Circle_Single_List *ptr = Head; while (ptr->Next != Current) ptr = ptr->Next; //immediate removal of the element ptr->Next = Current->Next; if (Head = Current) Head = Current->Next; delete(Current); ) else( Head = NULL; delete(Current); ) ) return Head; ) //search for an element in a circular singly-directed list bool Find_Item_Circle_Single_List(Circle_Single_List* Head, int DataItem)( Circle_Single_List *ptr = Head; //auxiliary pointer do ( if (DataItem == ptr->Data) return true; else ptr = ptr- >Next; ) while (ptr != Head); return false; ) // check if the cyclic singly list is empty bool Empty_Circle_Single_List(Circle_Single_List* Head)( return (Head != NULL ? false: true); ) // delete the singly cyclic list void Delete_Circle_Single_List(Circle_Single_List* Head)( if (Head != NULL)( Head = Delete_Item_Circle_Single_List(Head, 1); Delete_Circle_Single_List(Head); ) ) Listing 1.

It looks like a linear bidirectional list, but any element of it has two pointers, one of which points to the next element in the list, and the second points to the previous element (Fig. 32.2).

Rice. 32.2.

Basic operations carried out with cyclic bidirectional list:

• list creation;
• printing (viewing) the list;
• inserting an element into a list;
• deleting an element from the list;
• search for an element in a list
• checking if the list is empty;
• deleting the list.

To describe the algorithms of these basic operations, we will use the same declarations as for the linear bidirectional list.

Let us present the functions of the listed basic operations when working with a cyclic bidirectional list.

//create a circular bidirectional list Circle_Double_List* Make_Circle_Double_List(int n, Circle_Double_List** Head,Circle_Double_List* Loop)( Circle_Double_List* ptr;//auxiliary pointer if (n > 0) ( (*Head) = new Circle_Double_List(); // allocate memory for the new element if (Loop == NULL) Loop = (*Head); cout<< "Введите значение "; cin >> (*Head)->Data; //enter the value of the information field (*Head)->Next=NULL;//zero the address field ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop); if ((*Head)->Next != NULL) (*Head)->Next->Prior = (*Head); if ((*Head)->Prior == NULL) (*Head)->Prior = ptr; if (ptr == NULL) return *Head; else return ptr; ) else ( (*Head) = Loop; return NULL; ) ) //printing a cyclic doubly list void Print_Circle_Double_List(Circle_Double_List* Head) ( Circle_Double_List* ptr=Head; //auxiliary pointer do ( cout<< ptr->Data<< "\t"; ptr=ptr->next; ) while (ptr!=Head); cout<< "\n"; } /*вставка элемента после заданного номера в циклический двунаправленный список*/ Circle_Double_List* Insert_Item_Circle_Double_List (Circle_Double_List* Head, int Number, int DataItem){ Circle_Double_List *Current = Head; //встали на первый элемент Circle_Double_List *NewItem = new(Circle_Double_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) (//list is empty NewItem->Next = NewItem; NewItem->Prior = NewItem; Head = NewItem; ) else (//list is not empty for (int i = 1; i< Number; i++) Current = Current->next; NewItem->Next = Current->Next; Current->Next = NewItem; NewItem->Prior = Current; NewItem->Next->Prior = NewItem; ) return Head; ) /*remove the item with the given number from the circular doubled list*/ Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head, int Number)( if (Head != NULL)( Circle_Double_List *Current = Head; if (Head->Next != Head) ( for (int i = 1; i< Number; i++) Current = Current->next; Circle_Double_List *ptr = Current->Next; Current->Prior->Next = Current->Next; Current->Next->Prior = Current->Prior; if (Head = Current) //remove the first Head = Current->Next; delete(Current); ) else( Head = NULL; delete(Current); ) ) return Head; ) //search for an element in a cyclic doubly list bool Find_Item_Circle_Double_List(Circle_Double_List* Head, int DataItem)( Circle_Double_List *ptr = Head; //auxiliary pointer do ( if (DataItem == ptr->Data) return true; else ptr = ptr- >Next; ) while (ptr != Head); return false; ) //Check if the circular doubly list is empty bool Empty_Circle_Double_List(Circle_Double_List* Head)( return (Head != NULL ? false: true); ) //remove the circular doubly list void Delete_Circle_Double_List(Circle_Double_List* Head)( if (Head != NULL)( Head = Delete_Item_Circle_Double_List(Head, 1); Delete_Circle_Double_List(Head); ) ) Listing 2.

Last update: 10/25/2016

Ring (circular, cyclic) lists are a kind of linked lists. They can be single-linked or double-linked. Their distinctive feature is that the conditional last element stores a reference to the first element, so the list is closed or circular.

For example, if our list consists of one head element head, then we can close such a list as follows:

head.next = head;

For implementation, let's take the element class that is used in a singly linked list:

Public class Node ( public Node(T data) ( Data = data; ) public T Data ( get; set; ) public Node Next ( get; set; ) )

Now let's define the ring list class:

Using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp( public class CircularLinkedList :IEnumerable // circular linked list ( Node head; // head/first element Node tail; // last/tail element int count; // number of elements in the list // adding an element public void Add(T data) ( Node node = new node (data); // if the list is empty if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = node; tail = node; ) count++; ) public bool Remove(T data) ( Node current = head; node previous = null; if (IsEmpty) return false; do ( if (current.Data.Equals(data)) ( // If the node is in the middle or at the end if (previous != null) ( // remove the current node, now previous refers not to current, but to current.Next previous .Next = current.Next; // If the node is the last one, // change the tail variable if (current == tail) tail = previous; ) else // if the first element is removed ( // if there is only one element in the list if(count= =1) ( head = tail = null; ) else ( head = current.Next; tail.Next = current.Next; ) ) count--; return true; ) previous = current; current = current.Next; ) while ( current != head); return false; ) public int Count ( get ( return count; ) ) public bool IsEmpty ( get ( return count == 0; ) ) public void Clear() ( head = null; tail = null; count = 0; ) public bool Contains(T data) ( Node current = head; if (current == null) return false; do ( if (current.Data.Equals(data)) return true; current = current.Next; ) while (current != head); return false; ) IEnumerator IEnumerable.GetEnumerator() ( return ((IEnumerable)this).GetEnumerator(); ) IEnumerator IEnumerable .GetEnumerator() ( Node current = head; do ( if (current != null) ( yield return current.Data; current = current.Next; ) ) while (current != head); ) ) )

The addition actually boils down to resetting the pointer to the last element of tail, and the new element is placed between tail and head:

Public void Add(T data) ( Node node = new node (data); // if the list is empty if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = node; tail = node; ) count++; )

When deleting, we reset the pointer to the next element of the previous element in relation to the one being deleted:

Public bool Remove(T data) ( Node current = head; node previous = null; if (IsEmpty) return false; do ( if (current.Data.Equals(data)) ( // If the node is in the middle or at the end if (previous != null) ( // remove the current node, now previous refers not to current, but to current.Next previous .Next = current.Next; // If the node is the last one, // change the tail variable if (current == tail) tail = previous; ) else // if the first element is removed ( // if there is only one element in the list if(count= =1) ( head = tail = null; ) else ( head = current.Next; tail.Next = current.Next; ) ) count--; return true; ) previous = current; current = current.Next; ) while ( current != head); return false; )

Application of the ring list:

CircularLinkedList circularList = new CircularLinkedList (); circularList.Add("Tom"); circularList.Add("Bob"); circularList.Add("Alice"); circularList.Add("Jack"); foreach (var item in circularList) ( Console.WriteLine(item); ) circularList.Remove("Bob"); Console.WriteLine("\n After deletion: \n"); foreach (var item in circularList) ( Console.WriteLine(item); )

Console output:

Tom Bob Alice Jack Removed: Tom Alice Jack

Lecture text.

Structured data types, such as arrays, sets, and records, are static structures because their sizes do not change during the entire execution of the program. It is often required that data structures change their sizes in the course of solving a problem. Such data structures are called dynamic, they include stacks, queues, lists, trees, and others. Describing dynamic structures using arrays, records, and files leads to wasteful use of memory and increases the time for solving problems.

Using structural types, pointers, and dynamic variables, you can create a variety of dynamic memory structures. Features of pointers in the C++ language allow you to build dynamic memory structures based on statically declared variables or on a mixture of static and dynamic variables. The idea of ​​organizing all dynamic structures is the same. Some structural type S is defined, one or more fields of which are declared as pointers to the same or some other structural type. The program declares a variable d of type S or a variable of type pointer to S in the case of a fully dynamic structure creation. The name of this variable is used as the name of the "root" (parent name) of the dynamic structure during program execution. When the program is executed, as the dynamic structure is built, dynamic variables of the appropriate types are requested and linked by references, starting with the variable d or the first dynamic variable, the pointer to which is contained in the variable d. This approach allows you to create a dynamic structure with any topology.

Cyclic (ring) list is a data structure that is a sequence of elements, the last element of which contains a pointer to the first element of the list, and the first (in the case of a bidirectional list) to the last.

The main feature of such an organization is that there are no elements in this list containing nulls, and, therefore, it is impossible to select extreme elements.

Circular lists, like linear lists, can be unidirectional or bidirectional.

Circular singly-directed list similar to a linear singly-linked list, but its last element contains a pointer that links it to the first element (Figure 1).

To completely traverse such a list, it is enough to have a pointer to an arbitrary element, and not to the first one, as in a linear singly-directed list. The notion of the "first" element here is rather conditional and is not always required. Although sometimes it is useful to highlight some element as "first" by setting a special pointer to it. This is required, for example, to prevent "looping" when viewing a list.

Rice. 1. Cyclic singly-directed list

Basic operations performed with a cyclic singly-directed list:

creation of a list;

printing (viewing) the list;

Inserting an element into a list

search for an element in the list;

Checking if the list is empty

deleting the list.

To describe the algorithms for these basic operations, we will use the same declarations as for a linear singly linked list.

Let us present the functions of the listed basic operations when working with a cyclic singly-directed list.

//create a circular singly-directed list

void Make_Circle_Single_List(int n,

Circle_Single_List** Head,Circle_Single_List* Loop)(

(*Head) = new Circle_Single_List();

cout<< "Введите значение ";

cin >> (*Head)->Data;

(*Head)->

Make_Circle_Single_List(n-1,&((*Head)->Next),Loop);

//print a circular singly-directed list

void Print_Circle_Single_List(Circle_Single_List* Head) (

Circle_Single_List* ptr=Head;

//auxiliary pointer

cout<< ptr->Data<< "\t";

ptr=ptr->Next;

) while (ptr!=Head);

cout<< "\n";

/*insert the element after the given number into a circular singly linked list*/

Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,

int Number, int DataItem)(

//stand on the first element

Circle_Single_List *NewItem = new(Circle_Single_List);

//created a new element

NewItem->Data = DataItem;

NewItem->Next = NewItem;

else (// list is not empty

for (int i = 1; i< Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

/*remove the element with the given number from the cyclic singly-directed list*/

Circle_Single_List* Delete_Item_Circle_Single_List

(Circle_Single_List* Head, int Number)(

if (Head != NULL)(

Circle_Single_List *Current = Head;

if (Head->Next != Head)(

for (int i = 1; i< Number; i++)

Current = Current->Next;

while (ptr->Next != Current)

ptr = ptr->Next;

//immediate removal of the element

ptr->Next = Current->Next;

if (Head = Current) Head = Current->Next;

delete(Current);

delete(Current);

//search for an element in a circular singly-directed list

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Head;

//auxiliary pointer

if (DataItem == ptr->Data) return true;

else ptr = ptr->Next;

while (ptr != Head);

//check if the cyclic singly list is empty

bool Empty_Circle_Single_List(Circle_Single_List* Head)(

//delete circular singly-directed list

void Delete_Circle_Single_List(Circle_Single_List* Head)(

if (Head != NULL)(

Head = Delete_Item_Circle_Single_List(Head, 1);

Delete_Circle_Single_List(Head);

Circular Doubly List similar to a linear bidirectional list, but any element of it has two pointers, one of which points to the next element in the list, and the second points to the previous element (Fig. 2).

Fig.2. Circular Doubly List

The main operations carried out with a cyclic doubly linked list:

creation of a list;

printing (viewing) the list;

Inserting an element into a list

removal of an element from the list;

search for an element in a list

Checking if the list is empty

deleting the list.

To describe the algorithms for these basic operations, we will use the same declarations as for a linear bidirectional list.

Let us present the functions of the listed basic operations when working with a cyclic bidirectional list.

//create a cyclic bidirectional list

Circle_Double_List* Make_Circle_Double_List(int n,

Circle_Double_List** Head,Circle_Double_List* Loop)(

Circle_Double_List* ptr;//auxiliary pointer

(*Head) = new Circle_Double_List();

//allocate memory for the new element

if (Loop == NULL) Loop = (*Head);

cout<< "Введите значение ";

cin >> (*Head)->Data;

//enter the value of the information field

(*Head)->Next=NULL;//zeroing the address field

ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop);

if ((*Head)->Next != NULL)

(*Head)->Next->Prior = (*Head);

if ((*Head)->Prior == NULL)

(*Head)->Prior = ptr;

if (ptr == NULL)

else return ptr;

//printing a circular bidirectional list

void Print_Circle_Double_List(Circle_Double_List* Head) (

Circle_Double_List* ptr=Head;

//auxiliary pointer

cout<< ptr->Data<< "\t";

ptr=ptr->Next;

) while (ptr!=Head);

cout<< "\n";

/*insert the element after the given number into the circular doubly list*/

Circle_Double_List* Insert_Item_Circle_Double_List

(Circle_Double_List* Head, int Number, int DataItem)(

//stand on the first element

Circle_Double_List *NewItem = new(Circle_Double_List);

//created a new element

NewItem->Data = DataItem;

if (Head == NULL) (//list is empty

NewItem->Next = NewItem;

NewItem->Prior = NewItem;

else (// list is not empty

for (int i = 1; i< Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

NewItem->Prior = Current;

NewItem->Next->Prior = NewItem;

/*remove the element with the given number from the cyclic doubly list*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (Head != NULL)(

Circle_Double_List *Current = Head;

if (Head->Next != Head)(

for (int i = 1; i< Number; i++)

Current = Current->Next;

Circle_Double_List *ptr = Current->Next;

Current->Prior->Next = Current->Next;

Current->Next->Prior = Current->Prior;

if (Head = Current) //remove the first one

Head = Current->Next;

delete(Current);

delete(Current);

//search for an element in a circular doubly list

bool Find_Item_Circle_Double_List(Circle_Double_List* Head,

Circle_Double_List *ptr = Head;

//auxiliary pointer

if (DataItem == ptr->Data)

else ptr = ptr->Next;

while (ptr != Head);

// check if the circular doubly list is empty

bool Empty_Circle_Double_List(Circle_Double_List* Head)(

return (Head != NULL ? false: true);

//remove the circular doubly list

void Delete_Circle_Double_List(Circle_Double_List* Head)(

if (Head != NULL)(

Head = Delete_Item_Circle_Double_List(Head, 1);

Delete_Circle_Double_List(Head);