Cyclic unidirectional list. Cyclic (circular) lists. A singly linked looping list implementation

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

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

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

The main actions performed on the elements of the OCP:

• List initialization
• Adding a node to the list
• Removing a node from the list
• Displaying list items
• Swapping two list nodes

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

Initialization of the list is intended to create the root node of the list, in which the field of the pointer to the next element 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 a bcc

The function for adding a node to the list takes two arguments:

• Pointer to the element after which the addition occurs
• The data for the added item.

The procedure for adding an element can be displayed in the following diagram:


Adding an item to the OCP includes the following steps:

• creating the added node and filling in its data field;
• resetting 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 ODC has a form completely analogous to the function of adding a node to a simply connected 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; // save a pointer to the next element
lst-> ptr = temp; // the previous node points to the newly created
temp-> field = number; // save the data field of the added node
temp-> ptr = p; // the created node points to the next element
return (temp);
}

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

Deleting an OCN node

A pointer to the deleted node is passed as arguments to the function for deleting an ODC node. Since the list is circular, there is no need to pass a pointer to the root of the list.

The function returns a pointer to the node following the deleted one.

Removing a node can be represented by the following diagram:

Removing an OTS node includes the following steps:

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

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) // traverse the list starting at the root
{ // until we find the node before lst
temp = temp-> ptr;
}
temp-> ptr = lst-> ptr; // rearrange the pointer
free (lst); // free the memory of the deleted node
return (temp);
}

Displaying elements of the OCP

The function of displaying the elements of the ODS is similar to the function for the OLS, except for the condition of the end of the traversal of elements.
A pointer to the root of the list is passed as an argument to the element display function.
The function sequentially bypasses all nodes and displays 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 the value of the node p
p = p-> ptr; // go to next node
) while (p! = lst); // condition for the end of the traversal
}

For ODCs, you can also call the function of displaying list items starting from any node.

Interchange of bcc nodes

As arguments, the OCD 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 the nodes of the list is carried out by reinstalling the pointers. To do this, it is necessary to define the preceding and following assemblies for each replaced one. In this case, two situations are possible:

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

When replacing adjacent nodes, the reinstallation of pointers looks like this:


When replacing nodes that are not adjacent, reinstallation of pointers looks like this:

When reinstalling pointers, there is no need to check the root node (in contrast to the similar function for lst2-> ptr = lst1;
lst1-> ptr = next2;
prev1-> ptr = lst2;
}
else if (lst1 == next2)
{
// swap neighboring nodes
lst1-> ptr = lst2;
lst2-> ptr = next1;
prev2-> ptr = lst2;
}
else
{
// spaced nodes are exchanged
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, methods of declaration, initialization and features of use in solving problems of circular lists, decks, red-black trees, examples of solving problems for processing ring lists, decks, red-black trees are given.

The purpose of the lecture: learn algorithms and techniques for working with dynamic data structures, learn 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 do not change during the entire program execution time. It is often required that data structures change their sizes during the solution of the problem. Such data structures are called dynamic, and they include stacks, queues, lists, trees, and others. The description of dynamic structures using arrays, records and files leads to wasteful use of memory and increases the time to solve 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 building 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 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 creation of the structure. The name of this variable during program execution is used as the name of the "root" (parent name) of the dynamic structure. When executing the program, as the dynamic structure is being built, dynamic variables of the corresponding types and are 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.

Looped (circular) lists

Cyclic (circular) list- this is 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 this organization is that there are no elements in this list containing null pointers, and, therefore, the extreme elements cannot be selected.

Cyclic lists, as well as linear ones, are unidirectional and bidirectional.

Similar to a linear, unidirectional list, but its last element contains a pointer that links it to the first element (Figure 32.1).

To completely traverse such a list, it is sufficient to have a pointer to an arbitrary element, and not to the first one, as in a linear unidirectional list. The concept of the "first" element is rather arbitrary here and is not always required. Although sometimes it is useful to highlight a certain element as "the first" by setting a special pointer to it. This is required, for example, to avoid looping through the list.

Rice. 32.1.

Basic operations performed with a circular unidirectional list:

• creating a list;
• printing (viewing) the list;
• inserting an item into a list;
• deleting an item from the list;
• search for an item 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 unidirectional list.

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

// create a cyclic unidirectional 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; // zeroing the address field Make_Circle_Single_List (n-1, & ((* Head) -> Next), Loop); ) else ((* Head) = Loop;)) // printing a cyclic unidirectional 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; ) / * deleting the item with the given number from the cyclic unidirectional 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; // direct 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 item in a circular unidirectional 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;) // checking the emptyness of a circular unidirectional list bool Empty_Circle_Single_List (Circle_Single_List * Head) (return (Head! = NULL? False: true);) // deleting a circular unidirectional 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 item has two pointers, one pointing to the next item in the list, and the other pointing to the previous item (Figure 32.2).

Basic operations carried out with cyclical bidirectional list:

• creating a list;
• printing (viewing) the list;
• inserting an item into a list;
• deleting an item from the list;
• search for an item 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 the 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 if (n> 0) ((* Head) = new Circle_Double_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; // 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) return * Head; else return ptr; ) else ((* Head) = Loop; return NULL;)) // printing a cyclic bidirectional 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; ) / * deleting the item with the given number from the cyclic bidirectional 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; ) // find an item in a cyclic bidirectional 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 bidirectional list is empty bool Empty_Circle_Double_List (Circle_Double_List * Head) (return (Head! = NULL? False: true);) // remove the circular bidirectional 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: 25.10.2016

Ring (circular, circular) lists are a kind of linked lists. They can be singly connected or doubly connected. Their distinctive feature is that the conditional last element stores a reference to the first element, so the list turns out to be closed or circular.

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

Head.next = head;

For implementation, let's take the class of an element 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 class of the ring list:

Using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp (public class CircularLinkedList : IEnumerable // circular linked list (Node head; // head / first element of 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, // change the variable tail 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); )))

Adding actually amounts to resetting the pointer to the last tail element, and placing the new element 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 deleted one:

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, // change the variable tail 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 After Removal: Tom Alice Jack