Last Updated:

Dynamic List, Its Implementation, and Application [C++]

1. Introduction

Very often, when developing applications that operate with a large amount of input data, the question arises about their storage during program execution. It makes no sense to cite all of them, I will focus only on arrays. Undoubtedly, this type solves the issue of data storage, however, it is obvious that it is not without drawbacks. Chief among them is undoubtedly its fixed size. This property cannot be changed even for dynamically created arrays, which quite often forces programmers who use them exclusively to allocate memory "with a margin". Well, firstly, even the "reserve" is limited, and no one can guarantee that it will be enough, and secondly, on the contrary, the "reserve" may be enough so that a considerable part of the memory allocated to the program will be taken up in vain.

This problem is solved by another type of data storage, to which this article is devoted - a related list of dynamic variables, or more simply - a dynamic list. Components are added and removed at run time, and their number depends solely on the amount of available memory. However, this advantage has to be paid for by the disadvantage - if in the case of an array, we can access any component at any time, then in the case of a list, a maximum of 3 components are available to us at one time (it depends on the way the list is presented in the program). In most cases, this is a very reasonable price ...

In the article on the example of solving a simple problem, I will try to demonstrate working with dynamic lists, implement basic operations on it and its components. The article is intended for C\C++ programmers who are well acquainted with the syntax of the language, data types, have an idea and experience in using pointers. I'm programming in VS 2008, but in this case, the IDE doesn't really matter.

2. Problem Statement

To demonstrate the implementation of working with a dynamic list, let's solve the problem:

"The text file contains variable IDs and their numeric values (for example: x 15 abc 12.098 z -1.23). Move them to a dynamic list, for which to implement the following operations: search for the identifier in the list; Change the value of the specified identifier. Remove an identifier from the list, add a new identifier with the specified value to the list. At the end of the session, the list of identifiers and their values is transferred back to the file"

The task will allow us to learn how to implement all the basic operations on a dynamic list - creating a list, adding and removing list components (nodes), searching through the components of the list. The solution requires knowledge of file I/O, pointers, and structured data types. I will not create any shell for this task, although it would be useful, since there is a whole range of possible operations. However, this is not my primary concern within the scope of this article. I only implement all the operations in the form of separate functions and for the test I will refer to them once:

3. Solution

3.1. Standard Start

Let's get to the decision. We create a console project, and write a fairly standard code - organize file input. To read from the file, we use the getline() method, where as the third parameter we specify a space, which is a separator in our file.

#include <fstream>
#include <iostream>
#include <cstdlib> 
//TODO: Description of the list
//TODO: List operations
using namespace std; int main() { char* fileName = new char[50]; char* buf_name = new char[20]; char* buf_value = new char [10]; cout << "Enter name of file -> "; cin >> fileName; ifstream* inp = new ifstream(fileName); if (!inp->good()) { cout << "File opening error!\n"; system("PAUSE"); return 0; } while (!inp->eof()) { inp->getline(buf_name, 20, ' '); inp->getline(buf_value, 10, ' ');

It seems that everything is clear here and nothing requires special attention. In the first section of TODO we will describe the types necessary to work with the list, in the second we will have functions to work with it. Now let's proceed directly to the description of the list, because in the program we have already come close to filling it out.

3.2. Description of the dynamic list

To begin with, recall (or learn for the first time)) that a dynamic list is a number of components (nodes) containing directly an information part (a number, a string or more complex data types), as well as a reference to the next component (it is possible that the node contains 2 references: to the next and to the previous, in this case, the list is called biconnected). Thus, we get the following structure describing the list component for our task:

struct comp {
charname[20]; // variable name
charvalue[10]; // Variable value
comp*next; // Link to the next element of the list
};  

The list itself is a collection of its nodes and is usually given by one or two references, to the first element and the last. Often, one of these links is enough, but in our case it will be more convenient to use both. So, we get a structure describing our list:

struct dyn_list {
comp*head; // The first element (head) of the list
comp*tail; // Last element (tail) of the list
};

It's not hard to see what it means to create an empty list. In fact, you do not need to do anything, except to set the reference to the first item of the list (head) to null. Let's design this as a function, in parallel creating another one that checks for this condition whether the list is empty.

 // Create an empty list
void constr_list(dyn_list &l) { l.head = NULL; } // Проверка списка на пустоту bool chk_empty(dyn_list l) { return (l.head==NULL); }

We can see that everything is simple. Of course, the type that describes the list could be formatted as a class, and the function that creates it could be made the constructor of this class, but I'll leave it to you as a homework :. Now in the main() function, describe a variable of type dyn_list and create an empty list. Then we move on to the next point.

 dyn_list vars; // Dynamic list
constr_list(vars);

3.3 Operations on list components

Well, before you do any operations with components, they need to be added to the list, which we will do now. First of all, we need to create a new component and fill in its information part. Since we will put it at the end of the list, the reference part of the node will be null. Now let's understand what should happen to the head and tail links in this operation. There are 2 cases here - our list is empty or there is at least one component in it. If empty, both head and tail will point to the newly created component. If the nodes in the list are present, it is obvious that first you need to associate the last node with the one being added (for this reference part of the component to which the tail points, assign the address of the one you want to add), and then "move" the tail. Here's how simple it all looks in C++:

 // Adding a new component to the list
void comp_in(dyn_list &l, char* n, char* v) { comp* c = new comp(); strcpy_s(c->name, 20, n); strcpy_s(c->value, 10, v); c->next = NULL; if (chk_empty(l)) l.head = c; else l.tail->next = c; l.tail = c; }

Now let's search for the component. You will search by variable name, if you wish, you can search by value. As arguments, we pass the list itself and the search text to the search function. Our function will return the address of the found node or NULL if nothing is found. Let's start with the component that the head points to and, moving forward, compare the name of the current variable with the one you are looking for. In the search function, we can not be afraid to move the head link, since we do not transmit it through the link.

 // Search for a component in the list by name
comp* search(dyn_list l, char *n) { while (l.head != NULL) { if (!strcmp(l.head->name,n)) return l.head; l.head = l.head->next; } return l.head; }

Now let's remove the component. As an argument, we pass a list by reference, as well as a link to the component that we are going to remove. In the function itself, we consider 2 cases. The first case is simple: if the component is the first (that is, the head points to it), then you just need to move the reference to the first element forward. Otherwise, we'll need a working node variable that we'll use to navigate through the list. We will move until the next node after the current one is the one that we are going to delete. Well, after that, "jump" the removed component, assigning the reference part of the previous component to the address next to the deleted component. All these words fit into just a few lines of source code:

 // Removing a component from the list
void comp_del(dyn_list &l, comp* c) { if (c == l.head) { l.head = c->next; return; } comp* r = new comp(); r = l.head; while (r->next != c) r = r->next; r->next = c->next; delete c; }

The last and simplest operation is to change the value of the information part of the node. We will change the value field. As parameters, we will pass the address of the component by reference, as well as the new value of the field being changed. Well, we will change everything in one line. Here's how simple it looks:

 // Changing the value of the component
void comp_edit(comp &c, char* v) { strcpy_s(c.value, 10, v); }

With the operations finished, now it remains to finish the program.

3.4. Testing functions and completing the program

Well, everything is simple here, in the loop we just have to turn to the function of adding a component to the list. After the cycle, we test the rest of our functions and output the entire list to the file. Here is the entire code of the main() function.

 int main()
{
	char* fileName = new char[50];
	char* buf_name = new char[20];
	char* buf_value = new char [10];
	dyn_list vars; // Dynamic list
  cout << "Enter name of file -> "; cin >> fileName; ifstream* inp = new ifstream(fileName); if (!inp->good()) { cout << "File opening error!\n"; system("PAUSE"); return 0; } constr_list(vars); while (!inp->eof()) { inp->getline(buf_name, 20, ' '); inp->getline(buf_value, 10, ' '); comp_in(vars, buf_name, buf_value); } inp->close(); comp* p = new comp(); p = search(vars, "z"); if (p) comp_del(vars, p); p = search(vars, "abc"); if (p) comp_edit(*p, "2"); ofstream* out = new ofstream(fileName); while (vars.head != NULL) { out->write(vars.head->name, strlen(vars.head->name)); out->write(" ",1); out->write(vars.head->value, strlen(vars.head->value)); out->write(" ",1); vars.head = vars.head->next; } out->close(); system("PAUSE"); return 0; }

Problem solved :

4. Conclusions

Despite the fact that someone might find it difficult to work with a dynamic list, in fact everything turns out to be not only quite simple, but also convenient - components are created and deleted dynamically, the size of the list is limited only by the available memory, after the component is no longer used, memory can be immediately freed up for other nodes.

In any case, whether to use related lists in your programs or not, you will have to decide, hopefully my article will help you at least a little with this. Thank you.