Лінійний двозв’язний список. Приклад шаблонного класу

У даній темі наводиться приклад побудови класу, що реалізує лінійний двозв’язний список. Опрацювавши та скопіювавши кожен з пунктів даної теми можна отримати працездатний, протестований програмний код класу, що реалізує двозв’язний список.

Загальні відомості та особливості лінійних двозв’язних списків можна знайти у темі:

Лінійний двозв’язний список. Загальні відомості. Базові операції над списком

Зміст

Пошук на інших ресурсах:

1. Загальний опис складових програми

Розроблена програма носить демонстраційний характер. При створенні програми використовувався тип додатку Console Application.

У розробленому прикладі оголошуються наступні програмні елементи:

шаблонна структура Element<T>, яка описує один елемент списку;
шаблонний клас List<T>, який реалізує двозв’язний список структур типу Element<T>.

Структура Element<T> містить наступні поля:

data – поле, що є даними;
next – покажчик на наступний елемент списку;
prev – покажчик на попередній елемент списку.

У шаблонному класі List<T> реалізовано такі елементи:

внутрішні поля begin та end типу Element<T>*. Цеє покажчики на перший та останній елементи списку;
внутрішнє поле count – кількість елементів у списку;
внутрішній прихований (private) метод Move(int) – повертає елементу списку з заданим індексом;
внутрішній прихований (private) метод Copy(const List&) – здійснює копію зі списку;
внутрішній прихований (private) метод CorrectIndex(int) – визначає, чи позиція (індекс) для доступу до елементу списку має коректне значення;
конструктор List();
конструктор копіювання List(const List&);
оператор копіювання operator=(const List&);
деструктор List~();
метод GetElement(int) – повертає елемент за заданим індексом;
метод SetElement(T, int) – встановлює значення елементу за заданим індексом;
метод AddEnd(T) – додає новий елемент в кінець списку;
метод AddBegin(T) – додає новий елемент на початок списку;
метод Insert(T, int) – вставка елементу в задану позицію списку;
метод Del(int) – видалити елемент з заданої позиції списку;
метод Clear() – очищення списку;
метод Reverse() – реверсування списку;
метод Print() – вивід списку;
метод Count() – повернути кількість елементів у списку;
операторна функція operator+(const List&) – конкатенація списків;
операторна функція operator==(const List&) – порівняння списків на рівність;
операторна функція operator!=(const List&) – порівняння списків на нерівність;
операторна функція operator>=(const List&) – порівняння списків;
операторна функція operator<=(const List&) – порівняння списків;
операторна функція operator>(const List&) – порівняння списків;
операторна функція operator<(const List&) – порівняння списків.

⇑

2. Загальна структура програми (скорочений код)

Скорочений програмний код програми має вигляд показаний нижче. Кожну складову програми можна отримати опрацювавши всі наступні пункти даної теми.

#include <iostream>
using namespace std;

// Структура, яка описує один елемент (вузол)
template <class T>
struct Element
{
  // Складові структури Element<T>
};

// Клас, що реалізує двохзв'язний список
template <class T>
class List
{
  // Складові класу List<T>
};

// Реалізація методів класу List<T>
// ...

void main()
{
  // Клієнтський код (тестування)
}

⇑

3. Складові програми (детальний огляд)

3.1. Структура Element<T>

У програмі оголошення структури має вигляд:

// Структура, яка описує один елемент (вузол)
template <class T>
struct Element
{
  T data; // дані
  Element<T>* next; // адреса наступного елементу в списку
  Element<T>* prev; // адреса попереднього елементу в списку
};

⇑

3.2. Клас List<T>. Програмний код

У даній реалізації класу List<T> визначені тільки сигнатури (прототипи) методів, що в ньому реалізовані. Самі реалізації методів класу описуються в наступних пунктах.

Програмний код класу наступний.

// Клас, що реалізує двохзв'язний список
template <class T>
class List
{
private:
  Element<T>* begin; // покажчик на перший елемент списку
  Element<T>* end; // покажчик на останній елемент списку
  int count; // к-сть елементів у списку

  // Метод, що повертає елемент в заданій позиції,
  // вважається що позиція коректна.
  Element<T>* Move(int index);

  // Метод, що копіює список
  void Copy(const List<T>& obj);

  // Метод, що перевіряє коректність позиції (індексу) в списку
  bool CorrectIndex(int index);

public:
  // Конструктор
  List();

  // Конструктор копіювання
  List(const List& obj);

  // Оператор копіювання
  List<T>& operator=(const List& obj);

  // Деструктор
  ~List();

  // ---------- Методи доступу до окремих елементів списку --------
  // Отримати елемент списку за індексом
  T GetElement(int index);

  // Змінити значення елементу в заданій позиції
  void SetElement(T _data, int index);

  // ---------- Методи зміни розміру списку ------------
  // Додати елемент в кінець списку
  void AddEnd(T _data);

  // Додати елемент на початок списку
  void AddBegin(T _data);

  // Вставка елементу в задану позицію списку
  void Insert(T _data, int index);

  // Видалити елемент в заданій позиції,
  // позиція нумерується з 0
  void Del(int index);

  // Очищення списку
  void Clear();

  // Реверсування списку
  void Reverse();

  // Вивід списку
  void Print(string msg);

  // Отримати кількість елементів списку
  int Count();

  // ------------------------------------------
  // Перевантаження операторів
  // Операція + - конкатенація списків
  List<T>& operator+(const List<T>& obj);

  // Операція порівняння списків на рівність
  bool operator==(const List& obj);

  // Операція порівняння списків на нерівність
  bool operator!=(const List& obj);

  // Операція >=
  bool operator>=(const List& obj);

  // Операція <=
  bool operator<=(const List& obj);

  // Операція >
  bool operator>(const List& obj);

  // Операція <
  bool operator<(const List& obj);
};

⇑

3.2.1. Внутрішні поля класу

У класі List<T> лінійний список представлений трьома внутрішніми полями:

begin – покажчик на початок списку;
end – покажчик на кінець списку;
count – кількість елементів списку.

// Клас, що реалізує двозв'язний список
template <class T>
class List
{
private:
  Element<T>* begin; // покажчик на перший елемент списку
  Element<T>* end; // покажчик на останній елемент списку
  int count; // к-сть елементів у списку

  ...

}

⇑

3.2.2. Додаткові внутрішні методи класу

У класі виділено ряд операцій (методів), які використовуються в різних методах. Ці методи оголошуються в розділі private.

3.2.2.1. Метод Move(int). Отримати елемент в заданій позиції

Метод Move(int) повертає покажчик на елемент списку за заданою позицією.

// Отримати елемент в заданій позиції
template <class T>
Element<T>* List<T>::Move(int index)
{
  // 1. Встановити покажчик на початок списку
  Element<T>* t = begin;

  // 2. Перемотати до позиції index
  for (int i = 0; i < index; i++)
    t = t->next;

  // 3. Повернути покажчик
  return t;
}

⇑

3.2.2.2. Метод Copy(const List<T>&). Зробити копію з списку

Для поточного екземпляру метод Copy() реалізує копію зі списку, що є вхідним параметром obj.

// Метод, що робить копію зі списку
template <class T>
void List<T>::Copy(const List<T>& obj)
{
  // 1. Очистити список (звільнити пам'ять)
  Clear();

  // 2. Цикл копіювання this <= obj
  Element<T>* t = obj.begin;

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

⇑

3.2.2.3. Метод CorrectIndex(int). Перевірка коректності позиції (індексу) в списку

Метод CorrectIndex() отримує вхідним параметром позицію index і повертає true, якщо позиція коректна, тобто лежить в діапазоні [0..count-1]. В противному випадку метод повертає false.

// Метод, що перевіряє коректність позиції (індексу) в списку
template <class T>
bool List<T>::CorrectIndex(int index)
{
  return (index >= 0) && (index < count);
}

⇑

3.2.3. Спеціальні функції класу

3.2.3.1. Конструктор List<T>(). Створення пустого списку

Для створення пустого списку використовується конструктор без параметрів, програмний код якого має наступний вигляд

// Конструктор
template <class T>
List<T>::List()
{
  // Створити пустий список
  begin = end = nullptr;
  count = 0;
}

⇑

3.2.3.2. Конструктор копіювання List<T>(const List<T>& obj). Копіювання списку при його присвоєнні з одночасною ініціалізацією

При оголошенні об’кту класу List<T> та одночасному присвоєнні йому екземпляру іншого об’єкту викликається конструктор копіювання.

// Конструктор копіювання
template <class T>
List<T>::List(const List& obj)
{
  // Зробити копію зі списку
  Copy(obj);
}

⇑

3.2.3.3. Оператор копіювання operator=(const List<T>& obj). Присвоєння списків

Оператор копіювання викликається у випадку присвоєння екземплярів класу.

// Оператор копіювання
template <class T>
List<T>& List<T>::operator=(const List& obj)
{
  Copy(obj);
  return *this;
}

⇑

3.2.3.4. Деструктор ~List<T>(). Знищення списку

У деструкторі відбувається звільнення пам’яті, виділеної під список шляхом виклику методу Clear().

// Деструктор
template <class T>
List<T>::~List()
{
  Clear(); // очистити список
}

⇑

3.2.4. Методи GetElement(int) та SetElement(T, int). Доступ до окремих елементів списку

Метод GetElement() повертає елемент списку за заданим індексом. На відміну від методу Move() тут здійснюється перевірка значення index на коректність. Якщо значення index некоректне, то генерується виключна ситуація типу out_of_range.
Метод SetElement() змінює значення елементу списку за заданим індексом.

// Отримати елемент списку за індексом
template <class T>
T List<T>::GetElement(int index)
{
  // Перевірка, чи коректний індекс,
  // якщо індекс не коректний, згенерувати виключення
  if (!CorrectIndex(index))
    throw out_of_range("Incorrect index.");

  // Якщо індекс коректний, то повернути елемент
  Element<T>* t = Move(index);
  return t->data;
}

// Змінити значення елементу в заданій позиції
template <class T>
void List<T>::SetElement(T _data, int index)
{
  // Перевірка, чи коректна позиція
  if (!CorrectIndex(index))
    return;

  // Отримати елемент за позицією та змінити його значення
  Element<T>* t = Move(index);
  t->data = _data;
}

⇑

3.2.5. Методи, що змінюють список в цілому

3.2.5.1. Метод AddEnd(T). Додати елемент в кінець списку

Метод AddEnd() додає новий елемент в кінець списку.

// Додати елемент в кінець списку
template <class T>
void List<T>::AddEnd(T _data)
{
  try
  {
    // 1. Створити новий елемент з даними _data
    Element<T>* t = new Element<T>;
    t->next = nullptr; // наступного елементу немає
    t->prev = end; // встановити попередній елемент
    t->data = _data; // записати дані

    // 2. Заповнити поле next поки що останнього елементу
    if (end != nullptr)
      end->next = t;

    // 3. Перевірка, чи є в списку елементи
    if (count == 0)
    {
      // якщо елементів немає,
      // то це є одночасно і початок і кінець списку
      begin = end = t;
    }
    else
    {
      // якщо елементи є в списку, то це є кінець списку
      end = t;
    }

    // 3. Збільшити загальну кількість елементів
    count++;
  }
  catch (bad_alloc e)
  {
    // Якщо пам'ять не виділена, то вивести системне повідомлення
    cout << e.what() << endl;
  }
}

⇑

3.2.5.2. Метод AddBegin(T). Додати елемент на початок списку

// Додати елемент на початок списку
template <class T>
void List<T>::AddBegin(T _data)
{
  try
  {
    // 1. Створити новий елемент (нову комірку пам'яті)
    // та заповнити його даними
    Element<T>* t = new Element<T>;
    t->data = _data; // дані
    t->prev = nullptr; // попереднього елементу немає

    // наступний елемент вказує на колишній перший
    t->next = begin;

    // 2. Чи є елементи в списку?
    if (count > 0)
    {
      // якщо є, то перенаправити колишній початок списку
      begin->prev = t;
      begin = t;
    }
    else
    {
      // якщо елементів немає, то початок і кінець
      // є тим самим елементом
      begin = end = t;
    }

    // 3. Збільшити загальну к-сть елементів
    count++;
  }
  catch (bad_alloc e)
  {
    // якщо пам'ять не виділилась, то обробити помилку
    cout << e.what() << endl;
  }
}

⇑

3.2.5.3. Метод Insert(T, int). Вставка елементу в задану позицію списку

// Вставка елементу в задану позицію списку
template <class T>
void List<T>::Insert(T _data, int index)
{
  // 1. Перевірка, чи коректна позиція
  if (!CorrectIndex(index))
    return;

  // 2. Перевірка, чи вставка в кінець списку (за покажчиком end)
  if (index == count)
  {
    // Додати дані за покажчиком end
    AddEnd(_data);
    return;
  }

  // 3. Перевірка, чи вставка на початок списку (перед begin)
  if (index == 0)
  {
    AddBegin(_data);
    return;
  }

  try
  {
    // 4. Отримати елемент перед позицією вставки
    Element<T>* itemPrev = Move(index - 1);

    // 5. Отримати елемент в позиції вставки
    Element<T>* item = Move(index);

    // 6. Створити новий елемент та вставити його в список
    Element<T>* t = new Element<T>;
    t->data = _data;
    t->next = item;
    t->prev = itemPrev;
    itemPrev->next = t;
    item->prev = t;

    // 7. Збільшити кількість елементів
    count++;
  }
  catch (bad_alloc e)
  {
    // якщо пам'ять не виділена, то вивести системне повідомлення
    cout << e.what() << endl;
  }
}

⇑

3.2.5.4. Метод Del(int). Видалити елемент в заданій позиції

// Видалити елемент в заданій позиції,
// позиція нумерується з 0
template <class T>
void List<T>::Del(int index)
{
  // 1. Перевірка, чи взагалі є елементи в списку
  if (count == 0) return;

  // 2. Ігнор, якщо позиція вказана неправильно
  if (!CorrectIndex(index))
    return;

  // 3. Перейти до елементу, який видаляється
  Element<T>* item = Move(index);

  // 4. Отримати попередній елемент
  Element<T>* itemPrev = item->prev;

  // 5. Отримати наступний елемент
  Element<T>* itemNext = item->next;

  // 6. Перевірка, чи видаляється не перший елемент списку
  if ((count > 1) && (itemPrev != nullptr))
    itemPrev->next = itemNext; // обійти елемент item

  // 7. Перевірка, чи видаляється не останній елемент списку
  if ((itemNext != nullptr) && (count > 1))
    itemNext->prev = itemPrev;

  // 8. Якщо видаляється перший елемент
  if (index == 0)
    begin = itemNext;

  // 9. Якщо видаляється останній елемент
  if (index == count - 1)
    end = itemPrev;

  // 10. Видалити елемент item
  delete item;

  // 11. Зменшити загальну к-сть елементів
  count--;
}

⇑

3.2.5.5. Метод Clear(). Очищення списку

// Очищення списку
template <class T>
void List<T>::Clear()
{
  // Потрібно count разів видалити перший елемент списку
  int n = count; // зробити копію з count - важливо!
  for (int i = 0; i < n; i++)
    Del(0);
}

⇑

3.2.5.6. Метод Reverse(). Реверсування списку

// Реверсування списку
template <class T>
void List<T>::Reverse()
{
  List<T> L;
  Element<T>* t = begin;

  // цикл формування списку,
  // елемент додається до початку списку
  while (t != nullptr)
  {
    L.AddBegin(t->data);
    t = t->next;
  }
  *this = L;
}

⇑

3.2.6. Метод Print(string). Вивід списку

З метою визначення поточного стану спику в класі реалізовано метод Print(). Метод виводить список у зручній формі.

// Вивід списку
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. Метод Count(). Отримати кількість елементів у списку

// Отримати кількість елементів списку
template <class T>
int List<T>::Count()
{
  return count;
}

⇑

3.2.8. Реалізація базових операцій в списках

3.2.8.1. Операторна функція operator+(const List<T>& obj). Перевантаження оператора +. Конкатенація списків

Для реалізації зручної конкатенації (додавання) списків у класі перевантажено оператор + з допомогою функції operator+().

// Операція + - конкатенація списків
template <class T>
List<T>& List<T>::operator+(const List<T>& obj)
{
  // 1. Отримати доступ до списку obj
  Element<T>* t = obj.begin;

  // 2. Додати до тимчасового списку елементи t
  while (t != nullptr)
  {
    AddEnd(t->data);
    t = t->next;
  }

  // 3. Повернути об'єднаний список
  return *this;
}

⇑

3.2.8.2. Операторна функція operator==(const List<T>& obj). Перевантаження оператора ==. Порівняння списків на рівність

Корисними при роботі зі списками будуть операції порівняння. Однією з них є операція порівняння списків на рівність, яка реалізована в операторній функції operator==().

// Операція порівняння списків на рівність
template <class T>
bool List<T>::operator==(const List<T>& obj)
{
  // 1. Спочатку порівняти розміри списків
  if (count != obj.count)
    return false;

  // 2. Якщо розміри однакові, то порівняти поелементно
  Element<T>* t1 = begin;
  Element<T>* t2 = obj.begin;

  while (t1 != nullptr)
  {
    // Як тільки знайдено хоча б одне неспівпадіння,
    // то вихід з кодом false
    if (t1->data != t2->data)
      return false;

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

  return true;
}

⇑

3.2.8.3. Операторна функція operator!=(const List<T>& obj). Перевантаження оператора !=. Порівняння списків на нерівність

Порівняння списків на нерівність реалізовано в операторній функції operator!=(), яка перевантажує оператор !=.

// Операція порівняння списків на нерівність
template <class T>
bool List<T>::operator!=(const List<T>& obj)
{
  // Використати оператор порівняння ==
  return !(*this == obj);
}

// Операція >=
template <class T>
bool List<T>::operator>=(const List<T>& obj)
{
  // 1. Порівняння кількостей
  if (count > obj.count)
    return true;

  // 2. Порівняння за вмістом
  if (*this == obj)
    return true;

  return false;
}

⇑

3.2.8.4. Операторна функція operator>=(const List<T>& obj). Перевантаження оператора >=

// Операція >=
template <class T>
bool List<T>::operator>=(const List<T>& obj)
{
  // 1. Порівняння кількостей
  if (count > obj.count)
    return true;

  // 2. Порівняння за вмістом
  if (*this == obj)
    return true;

  return false;
}

⇑

3.2.8.5. Операторна функція operator<=(const List<T>& obj). Перевантаження оператора <=

// Операція <=
template <class T>
bool List<T>::operator<=(const List<T>& obj)
{
  // 1. Порівняння за кількістю ел-в у списку
  if (count < obj.count)
    return true;

  // 2. Порівняння за вмістом
  if (*this == obj)
    return true;

  return false;
}

⇑

3.2.8.6. Операторна функція operator>(const List<T>& obj). Перевантаження оператора >

// Операція >
template <class T>
bool List<T>::operator>(const List<T>& obj)
{
  if (count > obj.count)
    return true;
  return false;
}

⇑

3.2.8.7. Операторна функція operator<(const List<T>& obj). Перевантаження оператора <

// Операція <
template <class T>
bool List<T>::operator<(const List<T>& obj)
{
  if (count < obj.count)
    return true;
  return false;
}

⇑

3.2.9. Функція main(). Клієнтський код

Тестування роботи класу List<T> здійснюється у функції main(). Тут оголошується екземпляр класу для якого викликаються базові методи.

void main()
{
  // Тест
  List<double> L1; // Створити список

  // Додати елементи до списку
  L1.AddBegin(2.0);
  L1.AddBegin(1.0);
  L1.AddEnd(3.0);
  L1.AddEnd(4.0);
  L1.Print("L1: ");

  // Вставити елемент в задану позицію
  L1.Insert(-2.5, 2);
  L1.Print("L1.Insert: ");

  // Конструктор копіювання
  List<double> L2 = L1;
  L2.Print("L2: ");

  // Оператор копіювання
  List<double> L3;
  L3 = L2;
  L3.Print("L3: ");

  // Отримати елемент
  double x = L1.GetElement(3);
  cout << "x = " << x << endl;

  // Встановити новий елемент
  L3.SetElement(100.55, 0);
  L3.Print("L3: ");

  // Порівняти два списки
  if (L1 == L3)
    cout << "L1==L2" << endl;
  else
    cout << "L1!=L2" << endl;

  // Реверсування списку
  L1.Reverse();
  L1.Reverse();
  L1.Print("L1: ");
}

⇑

4. Запуск програми. Результати

Після запуску на виконання програма видасть наступний результат

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: =>