A linear doubly linked list. An example of a template class

This topic provides an example of developing a class that implements a linear doubly linked list. By processing and copying each of the points of this topic, you can get a workable, tested program code for a class that implements a doubly linked list. General information and features of linear singly linked lists can be found in the topic:

Linear doubly linked list. General concepts. Basic operations on the list

Search other resources:

1. General description of the components of the program

The developed program has a demonstration character. When creating the application, the Console Application type was used.

In the developed example, the following program elements are declared:

template structure Element<T>, describing one element of the list;
template class List<T> that implements a doubly linked list of structures of the Element<T> type.

The Element<T> structure contains the following fields:

data – field that is data;
next – pointer to the next element of the list;
prev is a pointer to the previous element of the list.

The List<T> template class implements the following elements:

internal fields begin and end of type Element<T>*. These are pointers to the first and last element of the list;
internal field count – the number of elements in the list;
internal hidden (private) method Move(int) – returns the list element at the given index;
internal hidden (private) method Copy(const List&) – makes a copy from the list;
internal hidden (private) method CorrectIndex(int) – determines whether the position (index) of the list element has the correct value;
constructor List();
copy constructor List(const List&);
copy operator operator=(const List&);
destructor List~();
method GetElement(int) – returns the element at the given index;
method SetElement(T, int) – sets the value of the element at the given index;
method AddEnd(T) – adds a new element to the end of the list;
method AddBegin(T) – adds a new element to the beginning of the list;
method Insert(T, int) – insertion of an element at a given position in the list;
method Del(int) – remove an element from a given position in the list;
mehtod Clear() – clearing the list;
method Reverse() – reversing the list;
method Print() – output of the list;
method Count() – return the number of elements in the list;
operator function operator+(const List&) – list concatenation;
operator function operator==(const List&) – comparison of lists for equality;
operator function operator!=(const List&) – comparison of lists for inequality;
operator function operator>=(const List&) – comparison of lists;
operator function operator<=(const List&) – comparison of lists;
operator function operator>(const List&) – comparison of lists;
operator function operator<(const List&) – comparison of lists.

⇑

2. General structure of the program (abbreviated code)

The abbreviated application code is as shown below. Each component of the program can be obtained by working through all the subsequent paragraphs of this topic.

#include <iostream>
using namespace std;

// A structure that describes one element (node)
template <class T>
struct Element
{
  // Components of Element<T> structure
  // ...
};

// A class that implements a doubly linked list
template <class T>
class List
{
  // Components of List<T> class
  // ...
};

// Implementation of List<T> class methods
// ...

void main()
{
  // Client code (testing)
  // ...
}

⇑

3. Components of the program (detailed overview)

3.1. Structure Element<T>

In a program, a structure declaration looks like this:

// Structure describing one element (node)
template <class T>
struct Element
{
  T data; // data
  Element<T>* next; // the address of the next element in the list
  Element<T>* prev; // the address of the previous element in the list
};

⇑

3.2. Class List<T>. Program code

In this implementation of the List<T> class, only the signatures (prototypes) of the methods that are implemented in it are defined. The implementations of the class methods themselves are described in the following paragraphs.

The class code is as follows.

// Class that implements a doubly linked list
template <class T>
class List
{
private:
  Element<T>* begin; // pointer to the first element of the list
  Element<T>* end; // pointer to the last element of the list
  int count; // number of elements in the list

  // A method that returns the element at the given position,
  // it is considered that the position is correct.
  Element<T>* Move(int index);

  // Method that copies the list
  void Copy(const List<T>& obj);

  // Method that checks the correctness of the position (index) in the list
  bool CorrectIndex(int index);

public:
  // Constructor
  List();

  // Copy constructor
  List(const List& obj);

  // Copy operator
  List<T>& operator=(const List& obj);

  // Destructor
  ~List();

  // ---------- Access methods for individual list elements --------
  // Get list element by index
  T GetElement(int index);

  // Change the value of an element at a given position
  void SetElement(T _data, int index);

  // ---------- Methods for resizing a list ------------
  // Add an element to the end of the list
  void AddEnd(T _data);

  // Add an element to the beginning of the list
  void AddBegin(T _data);

  // Inserting an element at a given position in a list
  void Insert(T _data, int index);

  // Delete the element at the given position, the position is numbered from 0
  void Del(int index);

  // Clear the list
  void Clear();

  // Reversing the List
  void Reverse();

  // Print the list
  void Print(string msg);

  // Get the number of list elements
  int Count();

  // ------------------------------------------
  // Overloading of operators
  // Operation + - list concatenation
  List<T>& operator+(const List<T>& obj);

  // The operation of comparing lists for equality
  bool operator==(const List& obj);

  // The operation of comparing lists for inequality
  bool operator!=(const List& obj);

  // Operation >=
  bool operator>=(const List& obj);

  // Operation <=
  bool operator<=(const List& obj);

  // Operation >
  bool operator>(const List& obj);

  // Operation <
  bool operator<(const List& obj);
};

⇑

3.2.1. Internal class fields

In the List<T> class, a linear list is represented by three internal fields:

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

// A class that implements a doubly linked list
template <class T>
class List
{
private:
  Element<T>* begin; // pointer to the first element of the list
  Element<T>* end; // pointer to the last element of the list
  int count; // number of elements in the list

  ...

}

⇑

3.2.2. Additional internal class methods

The class has a number of operations (methods) used in different methods. These methods are declared in the private section.

3.2.2.1. Method Move(int). Retrieve the element at the given position

The Move(int) method returns a pointer to the list element at the given position.

// Retrieve the element at the given position
template <class T>
Element<T>* List<T>::Move(int index)
{
  // 1. Set the pointer to the beginning of the list
  Element<T>* t = begin;

  // 2. Rewind to index position
  for (int i = 0; i < index; i++)
    t = t->next;

  // 3. Return the pointer
  return t;
}

⇑

3.2.2.2. Method Copy(const List<T>&). Make a copy of the list

For the current instance, the Copy() method implements a copy from the list that is the input parameter obj.

// Method that makes a copy from a list
template <class T>
void List<T>::Copy(const List<T>& obj)
{
  // 1. Clear the list (release the memory)
  Clear();

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

  while (t != nullptr)
  {
    AddEnd(t->data);
    t = t->next;
  }
}

⇑

3.2.2.3. Method CorrectIndex(int). Checking the correctness of the position (index) in the list

The CorrectIndex() method takes the index position as an input parameter and returns true if the position is correct, that is, it lies in the range [0..count-1]. Otherwise, the method returns false.

// A method that checks the correctness of the position (index) in the list
template <class T>
bool List<T>::CorrectIndex(int index)
{
  return (index >= 0) && (index < count);
}

⇑

3.2.3. Special class functions

3.2.3.1. Constructor List<T>(). Create an empty list

To create an empty list, a constructor without parameters is used, the program code of which is as follows.

// Constructor
template <class T>
List<T>::List()
{
  // Create the empty list
  begin = end = nullptr;
  count = 0;
}

⇑

3.2.3.2. Copy constructor List<T>(const List<T>& obj). Copying the list when assigning it with simultaneous initialization

When an object of class List<T> is declared and an instance of another object is assigned to it at the same time, the copy constructor is called.

// Copy constructor
template <class T>
List<T>::List(const List& obj)
{
  // Make a copy of the list
  Copy(obj);
}

⇑

3.2.3.3. Copy operator operator=(const List<T>& obj). Lists assignment

The copy operator is called when assigning class instances.

// Copy operator
template <class T>
List<T>& List<T>::operator=(const List& obj)
{
  Copy(obj);
  return *this;
}

⇑

3.2.3.4. Destructor ~List<T>(). Deleting (clearing) the list

In the destructor, the memory allocated for the list is released by calling the Clear() method.

// Destructor
template <class T>
List<T>::~List()
{
  Clear(); // clear the list
}

⇑

3.2.4. Mehtods GetElement(int) and SetElement(T, int). Access to individual list items

The GetElement() method returns the list element at the given index. Unlike the Move() method, the index value is checked for correctness here. If the value of index is invalid, then an exception of type out_of_range is thrown.

The SetElement() method changes the value of the list element at the given index.

// Get list element by index
template <class T>
T List<T>::GetElement(int index)
{
  // Checking if the index is correct,
  // if index is not correct, throw an exception
  if (!CorrectIndex(index))
    throw out_of_range("Incorrect index.");

  // If the index is correct, then return the element
  Element<T>* t = Move(index);
  return t->data;
}

// Change the value of the element at the specified position
template <class T>
void List<T>::SetElement(T _data, int index)
{
  // Checking if the position is correct
  if (!CorrectIndex(index))
    return;

  // Get an element by position and change its value
  Element<T>* t = Move(index);
  t->data = _data;
}

⇑

3.2.5. Methods that modify the list as a whole

3.2.5.1. Method AddEnd(T). Add an element to the end of the list

The AddEnd() method adds a new element to the end of the list.

// Add element to the end of the list
template <class T>
void List<T>::AddEnd(T _data)
{
  try
  {
    // 1. Create a new element with _data data
    Element<T>* t = new Element<T>;
    t->next = nullptr; // next element is missing
    t->prev = end; // set the previous item
    t->data = _data; // write data

    // 2. Fill in the next field of the last element so far
    if (end != nullptr)
      end->next = t;

    // 3. Checking if there are elements in the list
    if (count == 0)
    {
      // if there are no elements, then this is both the beginning and end of the list
      begin = end = t;
    }
    else
    {
      // if there are elements in the list, then this is the end of the list
      end = t;
    }

    // 3. Increase the total number of elements
    count++;
  }
  catch (bad_alloc e)
  {
    // If memory is not allocated, then display a system message
    cout << e.what() << endl;
  }
}

⇑

3.2.5.2. Method AddBegin(T). Add element to the beginning of the list

// Add an element to the beginning of the list
template <class T>
void List<T>::AddBegin(T _data)
{
  try
  {
    // 1. Create a new element (new memory location)
    //    and fill it with data
    Element<T>* t = new Element<T>;
    t->data = _data; // data
    t->prev = nullptr; // there is no previous element.

    // the next element points to the previous first
    t->next = begin;

    // 2. Are there elements in the list?
    if (count > 0)
    {
      // if there is, then redirect to the previous beginning of the list
      begin->prev = t;
      begin = t;
    }
    else
    {
      // if there are no elements, then the beginning and end are the same element
      begin = end = t;
    }

    // 3. Increase the total number of elements
    count++;
  }
  catch (bad_alloc e)
  {
    // if memory is not allocated, then handle the error
    cout << e.what() << endl;
  }
}

⇑

3.2.5.3. Method Insert(T, int). Inserting an element at a given position in a list

// Inserting an element at a given position in a list
template <class T>
void List<T>::Insert(T _data, int index)
{
  // 1. Checking if the position is correct
  if (!CorrectIndex(index))
    return;

  // 2. Checking if the insertion is at the end of the list (by the end pointer)
  if (index == count)
  {
    // Add data at pointer end
    AddEnd(_data);
    return;
  }

  // 3. Checking if the insertion is at the beginning of the list (before begin)
  if (index == 0)
  {
    AddBegin(_data);
    return;
  }

  try
  {
    // 4. Get the element before the insert position
    Element<T>* itemPrev = Move(index - 1);

    // 5. Get element at insertion position
    Element<T>* item = Move(index);

    // 6. Create a new element and insert it into the list
    Element<T>* t = new Element<T>;
    t->data = _data;
    t->next = item;
    t->prev = itemPrev;
    itemPrev->next = t;
    item->prev = t;

    // 7. Increase the number of elements
    count++;
  }
  catch (bad_alloc e)
  {
    // If memory is not allocated, then display a system message
    cout << e.what() << endl;
  }
}

⇑

3.2.5.4. Method Del(int). Remove element at given position

// Delete the element at the given position, the position is numbered from 0
template <class T>
void List<T>::Del(int index)
{
  // 1. Checking if elements are in the list
  if (count == 0) return;

  // 2. Ignore if position is incorrect
  if (!CorrectIndex(index))
    return;

  // 3. Go to element to be removed
  Element<T>* item = Move(index);

  // 4. Get previous element
  Element<T>* itemPrev = item->prev;

  // 5. Get next element
  Element<T>* itemNext = item->next;

  // 6. Checking if not the first element of the list is being removed
  if ((count > 1) && (itemPrev != nullptr))
    itemPrev->next = itemNext; // bypass the element

  // 7. Checking if not the last element of the list is being removed
  if ((itemNext != nullptr) && (count > 1))
    itemNext->prev = itemPrev;

  // 8. If the first element is removed
  if (index == 0)
    begin = itemNext;

  // 9. If the last element is removed
  if (index == count - 1)
    end = itemPrev;

  // 10. Delete item
  delete item;

  // 11. Decrease the total number of elements
  count--;
}

⇑

3.2.5.5. Method Clear(). Clearing the list

// Clearing the List
template <class T>
void List<T>::Clear()
{
  // Need to remove the first element of the list count times
  int n = count; // make a copy of count - important!
  for (int i = 0; i < n; i++)
    Del(0);
}

⇑

3.2.5.6. Method Reverse(). Reversing a list

// Reversing a list
template <class T>
void List<T>::Reverse()
{
  List<T> L;
  Element<T>* t = begin;

  // list generation cycle,
  // element is added to the beginning of the list
  while (t != nullptr)
  {
    L.AddBegin(t->data);
    t = t->next;
  }
  *this = L;
}

⇑

3.2.6. Method Print(string). Display the list

In order to determine the current state of the list, the Print() method is implemented in the class. The method outputs the list in human-readable form.

// Print the list
template <class T>
void List<T>::Print(string msg)
{
  cout << msg << " => ";

  Element<T>* t = begin;
  for (int i = 0; i < count; i++)
  {
    cout << t->data << " ";
    t = t->next;
  }
  cout << endl;
}

⇑

3.2.7. Method Count(). Get the number of elements in a list

// Get the number of elements in a list
template <class T>
int List<T>::Count()
{
  return count;
}

⇑

3.2.8. Implementation of basic operations in lists

3.2.8.1. Operator function operator+(const List<T>& obj). Overloading the + operator. List concatenation

To implement convenient concatenation (addition) of lists, the operator + is overloaded in the class using the operator+() function.

// Operation + - list concatenation
template <class T>
List<T>& List<T>::operator+(const List<T>& obj)
{
  // 1. Get access to the obj
  Element<T>* t = obj.begin;

  // 2. Add elements t to temporary list
  while (t != nullptr)
  {
    AddEnd(t->data);
    t = t->next;
  }

  // 3. Return concatenated list
  return *this;
}

⇑

3.2.8.2. Operator function operator==(const List<T>& obj). Operator overloading ==. Comparison of lists for equality

Comparison operations are useful when working with lists. One of them is the operation of comparing lists for equality, implemented in the operator function operator==().

// The operation of comparing lists for equality
template <class T>
bool List<T>::operator==(const List<T>& obj)
{
  // 1. First compare the sizes of the lists
  if (count != obj.count)
    return false;

  // 2. If the sizes are the same, then compare element by element
  Element<T>* t1 = begin;
  Element<T>* t2 = obj.begin;

  while (t1 != nullptr)
  {
    // As soon as at least one mismatch is found, then exit with the code false
    if (t1->data != t2->data)
      return false;

    t1 = t1->next;
    t2 = t2->next;
  }

  return true;
}

⇑

3.2.8.3. Operator function operator!=(const List<T>& obj). Operator overload !=. Comparing lists for inequality

Comparison of lists for inequality is implemented in the operator function operator!=(), which overloads the operator !=.

// The operation of comparing lists for inequality
template <class T>
bool List<T>::operator!=(const List<T>& obj)
{
  // Use comparison operator ==
  return !(*this == obj);
}

// Operation >=
template <class T>
bool List<T>::operator>=(const List<T>& obj)
{
  // 1. Compare number of elements
  if (count > obj.count)
    return true;

  // 2. Compare by content
  if (*this == obj)
    return true;

  return false;
}

⇑

3.2.8.4. Operator function operator>=(const List<T>& obj). Operator overload >=

// Operation >=
template <class T>
bool List<T>::operator>=(const List<T>& obj)
{
  // 1. Comparison by number of elements
  if (count > obj.count)
    return true;

  // 2. Comparison by content
  if (*this == obj)
    return true;

  return false;
}

⇑

3.2.8.5. Operator function operator<=(const List<T>& obj). Operator overload <=

// Operation <=
template <class T>
bool List<T>::operator<=(const List<T>& obj)
{
  // 1. Comparison by the number of elements in the list
  if (count < obj.count)
    return true;

  // 2. Comparison by content
  if (*this == obj)
    return true;

  return false;
}

⇑

3.2.8.6. Operator function operator>(const List<T>& obj). Overload operator >

// Operation >
template <class T>
bool List<T>::operator>(const List<T>& obj)
{
  if (count > obj.count)
    return true;
  return false;
}

⇑

3.2.8.7. Operator function operator<(const List<T>& obj). Overload operator <

// Operation <
template <class T>
bool List<T>::operator<(const List<T>& obj)
{
  if (count < obj.count)
    return true;
  return false;
}

⇑

3.2.9. Function main(). Client code

Testing the operation of the List<T> class is carried out in the main() function. Here, an instance of the class is declared on which the base methods are called.

void main()
{
  // Test
  List<double> L1; // Create a list

  // Add elements to the list
  L1.AddBegin(2.0);
  L1.AddBegin(1.0);
  L1.AddEnd(3.0);
  L1.AddEnd(4.0);
  L1.Print("L1: ");

  // Insert an element at a given position
  L1.Insert(-2.5, 2);
  L1.Print("L1.Insert: ");

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

  // Copy operator
  List<double> L3;
  L3 = L2;
  L3.Print("L3: ");

  // Get element
  double x = L1.GetElement(3);
  cout << "x = " << x << endl;

  // Set a new element
  L3.SetElement(100.55, 0);
  L3.Print("L3: ");

  // Compare two lists
  if (L1 == L3)
    cout << "L1==L2" << endl;
  else
    cout << "L1!=L2" << endl;

  // Reversing a list
  L1.Reverse();
  L1.Reverse();
  L1.Print("L1: ");
}

⇑

4. Run the program. Results

After running the program, it will give the following result

L1: => 1 2 3 4
L1.Insert: => 1 2 -2.5 3 4
L2: => 1 2 -2.5 3 4
L3: => 1 2 -2.5 3 4
x = 3
L3: => 100.55 2 -2.5 3 4
L1!=L2
L1: => 1 2 -2.5 3 4
L6: =>

BestProg

Programming: theory and practice