C++. An example of the implementation of a linear singly-linked list

An example of the implementation of a linear singly-linked (singly-directed) list for the generic type T. The list is presented in RAM

The example demonstrates the development of a template class designed to implement a singly linked list organized in RAM. The class is implemented in a console application. Using the clipboard, you can combine the codes of the following program elements and get the workable class code.

Before studying this topic, it is recommended that you familiarize yourself with the following topic:

Linear singly linked list. General information. Basic operations on the list

Search other resources:

1. Program components

The program includes two main components:

template structure Element<T>, describing one element (node) of the list;
template class List<T> that implements a list.

The following programming elements are declared in the List<T> class:

the begin pointer, pointing to the beginning of the list;
end pointer, pointing to the end of the list;
counter count – sets the number of elements in the list;
internal hidden (private) method Move() – returns the list element at the specified index;
internal hidden (private) method Copy() – makes a copy from the list;
constructor without parameters List() – creates an empty list;
~List() destructor – releases the memory allocated for the list elements;
copy constructor List(const List&) – called when copying lists at the time of declaration;
copy operator operator=(const List&) – called when copying lists;
method Add(T) – adds a new element to the end of the list;
Del(int) method – removes an element from the list at a given position;
Del() method – removes the first element from the list;
Clear() method – removes all elements from the list;
method Count() – returns the number of elements of the list;
operator function operator[](int) – implements access to the list element by index [ ];
method Insert(T, int) – inserts an element of the list at the specified position;
Print() method – display the current state (value) of the list.

⇑

2. Program code in C++

2.1. Basic node. The structure Element

To represent a single element of the list, the generic structure Element<T> is used, which takes the type T as a parameter. This structure contains the fields:

data – data of some generalized type T. Type T can be any class or structure or ordinary primitive type (int, double, char…);
next – a pointer to the next element.

// Base node - element
template <class T>
struct Element
{
  T data; // data
  Element* next; // next element
};

⇑

2.2. Class List<T>

After declaring the Element<T> structure, a List<T> class is created that will use this structure. Initial view of the class

// Class - singly linked list
template <class T>
class List
{

}

⇑

2.2.1. Adding internal fields

The List<T> class declares 3 fields:

begin – pointer to the beginning of the list;
end – pointer to the end of the list;
count – the current number of elements in the list.

Optionally, you can reduce the number of internal fields to one, leaving only the begin field or two begin and count fields. However, such changes will lead to the addition of additional code (jumping to the end of the list, determining the number of elements in the list, etc.) each time the list is processed. This will slow down the program.

After adding internal fields, the class view is as follows

// Class - singly linked list
template <class T>
class List
{
private:
  Element<T>* begin; // pointer to the beginning of the list
  Element<T>* end; // pointer to end of list
  int count; // number of elements in the list
}

⇑

2.2.2. Internal function Move(int)

The Move() internal function is used to find (get) an element at a given list position by other public class functions.

// Class - singly linked list
template <class T>
class List
{
private:

  ...

  // An internal function that rewinds to the specified position,
  // used in several methods
  Element<T>* Move(int index)
  {
    if (count > 0) // if there are elements in the list
    {
      // Rewind to index position
      Element<T>* t = begin;
      for (int i = 0; i < index; i++)
        t = t->next;
      return t;
    }
    return nullptr;
  }
}

⇑

2.2.3. Method Copy(const List&). Make a copy of the list

An important class method is the Copy() method, which makes a copy from a list. This method is called in the copy constructor, copy operator, and can be used in other class functions.

// Class - singly linked list
template <class T>
class List
{
private:

...

  // Method that makes a copy of a list
  void Copy(const List& obj)
  {
    // 1. Release the memory allocated for the previous list
    Clear();

    // 2. Copy list obj => this
    Element<T>* t = obj.begin;

    for (int i = 0; i < obj.count; i++)
    {
      // Add to end of list
      Add(t->data);
      t = t->next;
    }

    count = obj.count;
  }
}

⇑

2.2.4. Default constructor List()

The List<T> class declares only one constructor that creates an empty list. You can optionally declare additional constructors that are initialized to some initial value based on the input array or list.

public:

  // Constructor
  List()
  {
    // The list is empty at the beginning
    begin = end = nullptr;
    count = 0;
  }

⇑

2.2.5. Copy constructor List(const List&)

Since the class uses pointers, it is imperative to implement a copy constructor that is called when the list is declared and initialized at the same time.

public:

  ...

  // Copy constructor
  List(const List& obj)
  {
    // Here you need to make a copy from the list,
    // to avoid the disadvantages of bitwise copying
    Copy(obj);
  }

⇑

2.2.6. Copy operator operator=(const List&)

The copy operator is used to assign one list to another and has the same purpose as the copy constructor.

public:

  ...

  // Copy operator
  List<T>& operator=(const List& obj)
  {
    // Invoke the function Copy()
    Copy(obj);
    return *this;
  }

⇑

2.2.7. Method Add(T). Add a new element to the end of the list

The Add() method adds a new element to the end of the list. The method creates a new element of type Element<T>. This element is filled with data and added to the end of the list. When adding, two cases are considered:

adding an element to an empty list;
adding an element to a non-empty list.

public:

  ...

  // Add a new element to the end of the list
  void Add(T _data)
  {
    try {
      // 1. Create a new element and fill it with data
      Element<T>* elem = new Element<T>;
      elem->data = _data;
      elem->next = nullptr; // the last element in the list

    // 2. Add element
    // Determine if element is first
    if (begin == nullptr)
    {
      // if the element is first in the list
      begin = end = elem;
    }
    else
    {
      // if the element is not the first in the list,
      // then add it to the end of the list.
      end->next = elem;
      end = elem;
    }

    // 3. Increase the number of elements in the list
    count++;
  }
  catch (bad_alloc e)
  {
    // If it was not possible to allocate memory, then display a system message
    cout << e.what() << endl;
  }
}

⇑

2.2.8. Method Del(int). Delete the element from a list at a given position

The Del() method takes as input the position of the element to be removed from the list. The element is removed provided that the removal position is correct.

public:

  ...

  // Delete the element at index position,
  // position is numbered from 0
  void Del(int index)
  {
    // 1. Checking if the number of elements is equal to zero
    if (count == 0)
      return;

    // 2. Checking if index value is correct
    if ((index < 0) || (index >= count))
      return;

    // 3. Deleting element.
    // Checking if the first element is being removed
    if (index == 0)
    {
      // 3.1. If the first element is removed
      Element<T>* t = begin; // save the address of the first element
      begin = begin->next; // go to the next element
      delete t; // release the first element
    }
    else
    {
      // 3.2. If not the first element is removed.
      // 3.2.1. Go to element at position index-1
      Element<T>* t = Move(index - 1);

      // 3.2.2. Save the element to be removed
      Element<T>* t2 = t->next;

      // 3.2.3. Set next element for element at position index-1
      t->next = t2->next; // works correctly even for the last element

      // 3.2.4. Delete the element pointed to by t2
      delete t2;
    }

    // 4. Decrease the total number of elements
    count--;

    cout << "Del(int)" << endl;
  }

⇑

2.2.9. Method Del(). Delete the first element from list

A modification of the Del(int) method is the Del() method, which removes the first element from the list.

public:

  ...

  // Delete the first item from the list
  void Del()
  {
    // Call overloaded Del(int) method
    Del(0);
  }

⇑

2.2.10. Clearing the list. Method Clear()

Clearing the list is implemented in the Clear() method, which calls the Del() method until the beginning of the list becomes nullptr.

public:

  ...

  // Method that removes all elements
  void Clear()
  {
    while (begin != nullptr)
    Del();
  }

⇑

2.2.11. Method Count(). Return the number of elements of the list

If you need to get the number of elements in the list, you can call the Count() method, which returns the value of the internal variable count.

public:

  ...

  // Return the number of elements in the list
  int Count() { return count; }

⇑

2.2.12. Operator function operator[](int). Indexing list as array

A convenient way to refer to an element of a list is to refer to it with the indexing operator [ ] as in the case of the array. To implement this for the List<T> class, you need to overload the operator function operator[](int). For a function to be used on the left and right sides of a statement, it must return a T& reference.

public:

  ...

  // Operator to index list as array
  T& operator[](int index)
  {
    // Checking if the value of index is correct
    if ((index < 0) || (index > count - 1))
    {
      // If not correct, then throw an exception
      throw out_of_range("Incorrect index.");
    }

    // If the value of index is correct,
    // then find the desired element and return its value
    Element<T>* t = Move(index);

    return t->data;
  }

⇑

2.2.13. Method Insert(T, int). Inserting an element at a given position

To ensure the convenience of working with the list, the Insert() method is additionally implemented, which is designed to insert the element at a given position.

public:

  ...

  // Inserting an item element at the given index position.
  // The index position is numbered from 0.
  void Insert(T item, int index)
  {
    // 1. Checking if the value of index is correct,
    // only for the case if the elements are in the list
    if ((count != 0) && ((index < 0) || (index >= count)))
      return;

    // 2. Trying to jump to the element at position index
    Element<T>* t = Move(index);

    // 3. Checking if the list exists
    if (t == nullptr)
    {
      // 3.1. If the list does not exist, then add the element to the end of the list
      Add(item);
    }
    else
    {
      // 3.2. If the list exists, then implement the insert
      try {
        // Attempt to allocate memory for a new cell
        Element<T>* t2 = new Element<T>;
        t2->data = item;

        if (index == 0) // If insertion in first element
        {
          // Set start of list to new cell
          t2->next = begin;
          begin = t2;
        }
        else
        {
          // If insertion into second, third, etc. element,
          // go to element index-1
          t = Move(index - 1);

          // Insertion into second, third, etc. element
          t2->next = t->next;
          t->next = t2;
        }

        // Increase the number of elements by 1
        count++;
      }
      catch (bad_alloc e)
      {
        // If the memory could not be allocated, then handle the exception
        cout << e.what() << endl;
      }
    }
  }

⇑

2.2.14. Destructor ~List()

In the destructor, the Clear() function is called, which frees the memory allocated for the list element by element.

public:

...

// Destructor
~List()
{
  // Clear the list
  Clear();
}

⇑

2.2.15. Method Print(). Display the list

The Print() function prints the list that is present in the current instance of the class.

// List output - testing
void Print(string msg)
{
  cout << msg << endl;

  if (count == 0) // if list is empty
  {
    cout << "List is empty." << endl;
    return;
  }

  // List traversal
  Element<T>* t = begin;

  while (t != nullptr)
  {
    cout << t->data << " ";
    t = t->next;
  }
  cout << endl;
}

⇑

3. Function main(). Client code

The main() function creates and tests the base methods of the list.

void main()
{
  List<double> L; // Create empty list
  L.Print("L: ");

  // Empty list
  L.Del();

  // Add items to list
  L.Add(2.5);
  L.Add(3.8);
  L.Add(4.1);
  L.Add(3.3);
  L.Print("L+4: ");

  // Delete one element  
  L.Del(2);
  L.Print("L-1: ");

  // Change the element in the list
  L[0] = 77.8;
  L.Print("L[0] = 77.8: ");

  // List elements - access by index
  cout << "L[1] = " << L[1] << endl;
  double z = L[2];
  cout << "z = " << z << endl;

  cout << "count = " << L.Count() << endl;

  List<double> L2 = L; // Copy constructor
  L2.Print("L2 = L: ");

  List<double> L3;
  L3.Print("L3: ");

  L2.Add(11.55);
  L2.Print("L2 + 11.55: ");

  L3 = L2;
  L3.Print("L3 + L2 + 11.55: ");

  L3.Clear();
  L3.Print("L3.Clear: ");

  L3.Insert(225.8, 0);
  L3.Print("L3 + 225.8: ");

  L3.Insert(10.15, 0);
  L3.Print("L3 + 10.0: ");

  L3.Insert(77.77, 1);
  L3.Print("L3 + [77.77]: ");
}

⇑

4. The result of the program

L:
List is empty.
L+4:
2.5 3.8 4.1 3.3
L-1:
2.5 3.8 3.3
L[0] = 77.8:
77.8 3.8 3.3
L[1] = 3.8
z = 3.3
count = 3
L2 = L:
77.8 3.8 3.3
L3:
List is empty.
L2 + 11.55:
77.8 3.8 3.3 11.55
L3 + L2 + 11.55:
77.8 3.8 3.3 11.55
L3.Clear:
List is empty.
L3 + 225.8:
225.8
L3 + 10.0:
10.15 225.8
L3 + [77.77]:
10.15 77.77 225.8

BestProg

Programming: theory and practice