cpp-single-linked-list

Develop my own container — a singly linked list.

Read in other languages: English, Русский

Program Description

A learning project that allowed me to better understand the structure of C++ containers and use them effectively.

Build using Cmake

To build this project on linux you need:

1. If you don't have Cmake installed, install Cmake
   
2. If the "Debug" or "Release" folders are not created:
   

mkdir Debug
mkdir Release

3. Run the command for Debug and/or Release conf:
   

cmake -E chdir Debug/ cmake -G "Unix Makefiles" ../ -DCMAKE_BUILD_TYPE:STRING=Debug
cmake -E chdir Release/ cmake -G "Unix Makefiles" ../ -DCMAKE_BUILD_TYPE:STRING=Release 

4. Go to "Debug" or "Release" folder and build:
   

cmake --build .

5. To Run program - in the debug or release folder run:
   

./single_linked_list

System requirements:

1. C++17(STL)
2. GCC (MinG w64) 11.2.0

Technology stack:

1. forward_list
   
2. Template classes
   
3. Iterators begin, end, before_begin
   
4. iterator_category, value_type, difference_type, pointer, reference
   
5. swap
   
6. Three levels of exception security
   

Before you start:

0. Installation and configuration of all required components in the development environment to run the application
   
1. The use case and tests are shown in main.cpp .
   

Detailed description of the project:

A singly linked list -

is one of the basic linked data structures. To understand how it works is to take the first step towards developing more complex structures. In the standard library, a singly linked list is represented by a template of the forward_list class.

The list item is called a "node". The list item can be represented as a Node structure, which contains the value of the item and a pointer to the next node.

The template class of a SingleLinkedList has the following functionality:

• Default constructor that creates an empty list;
  
• The GetSize method, which returns the number of items in the list;
  
• The IsEmpty method, which returns true if the list is empty, and false otherwise.
  
• PushFront - inserts an element at the beginning of a singly linked list, and the 'Clearoperation clears the list.<br> ThePushFront` method provides a strict exception safety guarantee: if an exception is thrown during the operation of the method, the state of the list should be the same as before the method was called.
  
• The Clear method clears the list and does not throw exceptions.
  
• When the list is destroyed, all its elements are deleted.
  
• The PopFront method. Deletes the first element of a non-empty list in time O(1). Does not throw exceptions.
  
• The InsertAfter method. During the time O(1) inserts a new value into the list following the element referenced by the iterator passed to insertAfter. The method provides a strict guarantee of exception safety.
  
• The EraseAfter method. During O(1) removes from the list the element following the element referenced by the iterator passed to insertAfter. Does not throw exceptions.
  
• Methods before_begin and cbefore_begin. Returns iterators referring to a dummy position before the first element of the list. Such an iterator is used as a parameter for the InsertAfter and EraseAfter methods when it is necessary to insert or delete an element at the beginning of the list. This iterator cannot be dereferenced.
  

Implemented support for iterating through the elements of the SingleLinkedList container.

The Basic Iterator class, on the basis of which the constant and non-constant iterator of the list are declared.
The list class implements a constant and non-constant version of the begin and end methods, which return iterators to the first element of the container and the position following the last element.
To make it convenient to get constant iterators, the cbegin and cend methods are implemented.

In the class of a singly linked list, the following functionality:

• Comparison operations ==, !=, <, >, <=, >=;< br>
• Exchange of the contents of two lists using the swap method and the template swap function;
  
• Construction of a singly linked list based on initializer_list. The sequence of elements of the created list and initializer_list is the same;
  
• Reliable copy constructor and assignment operation. The assignment operation provides a strict guarantee of exception safety. If an exception is thrown during the assignment process, the contents of the left argument of the assignment operation will remain unchanged.