C++. Приклад реалізації лінійного однозв’язного списку

Приклад реалізації лінійного однозв’язного списку для узагальненого типу T. Список представлений в оперативній пам’яті

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

Перед вивченням даної теми рекомендується ознайомитись з наступною темою:

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

Зміст

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

1. Складові програми

У програмі реалізовані дві основні складові

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

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

покажчик begin, що вказує на початок списку;
покажчик end, що вказує на кінець списку;
лічильник count – задає кількість елементів у списку;
внутрішній прихований (private) метод Move() – повертає елемент списку за заданим індексом;
внутрішній прихований (private) метод Copy() – робить копію зі списку;
конструктор без параметрів List() – створює пустий список;
деструктор ~List() – виконує звільнення пам’яті, виділеної під елементи списку;
конструктор копіювання List(const List&) – викликається при копіюванні списків в момент оголошення;
оператор копіювання operator=(const List&) – викликається при копіюванні списків;
метод Add(T) – додає новий елемент в кінець списку;
метод Del(int) – видаляє елемент зі списку в заданій позиції;
метод Del() – видалє перший елемент зі списку;
метод Clear() – видаляє всі елементи зі списку;
метод Count() – повертає кількість елементів списку;
операторна функція operator[](int) – реалізує доступ до елементу списку за індексом [ ];
метод Insert(T, int) – вставляє елемент списку в задану позицію;
метод Print() – вивести поточний стан (значення) списку.

⇑

2. Програмний код на мові C++

2.1. Базовий вузол. Структура Element

Для представлення окремого елементу списку використовується узагальнена структура Element<T> яка отримує тип T в якості параметру. Ця структура містить поля:

data – дані деякого узагальненого типу T. Типом T може бути будь-який клас чи структура або звичайний примітивний тип (int, double, char, …);
next – покажчик на наступний елемент.

// Базовий вузол - елемент
template <class T>
struct Element
{
  T data; // дані
  Element* next; // наступний елемент
};

⇑

2.2. Клас List<T>

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

// Клас - однозв'язний список
template <class T>
class List
{

}

⇑

2.2.1. Додавання внутрішніх полів

У класі List<T> оголошуються 3 поля:

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

За бажанням, можна зменшити кількість внутрішніх полів до одного, залишивши тільки поле begin або два поля begin і count. Однак, такі зміни призведуть до додавання додаткового програмного коду (перехід на кінець списку, визначення кількості елементів у списку тощо) при кожній обробці списку. Це уповільнить роботу програми.

Після додавання внутрішніх полів вигляд класу наступний

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

⇑

2.2.2. Внутрішня функція Move(int)

Внутрішня функція Move() використовується для пошуку (отримання) елементу в заданій позиції списку в інших загальнодоступних функціях класу.

// Клас - однозв'язний список
template <class T>
class List
{
private:

  ...

  // Внутрішня функція, яка перемотує на задану позицію,
  // використовується у декількох методах
  Element<T>* Move(int index)
  {
    if (count > 0) // якщо є елементи в списку
    {
      // Перемотати на позицію index
      Element<T>* t = begin;
      for (int i = 0; i < index; i++)
        t = t->next;
      return t;
    }
    return nullptr;
  }
}

⇑

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

Важливим методом класу є метод Copy(), який здійснює копію зі списку. Цей метод викликається у конструкторі копіювання, операторі копіювання та може використовуватись в інших власно-розроблених функціях класу.

// Клас - однозв'язний список
template <class T>
class List
{
private:

  ...

  // Метод, який робить копію зі списку
  void Copy(const List& obj)
  {
    // 1. Звільнити пам'ять, виділену під попередній список
    Clear();

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

    for (int i = 0; i < obj.count; i++)
    {
      // Додати в кінець списку
      Add(t->data);
      t = t->next;
    }

    count = obj.count;
  }
}

⇑

2.2.4. Конструктор за замовчуванням List()

У класі List<T> оголошується тільки один конструктор, який створює пустий список. За бажанням можна оголосити додаткові конструктори, які ініціалізуються деяким початковим значенням на основі вхідного масиву чи списку.

public:

  // Конструктор
  List()
  {
    // На початку список пустий
    begin = end = nullptr;
    count = 0;
  }

⇑

2.2.5. Конструктор копіювання List(const List&)

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

public:

...

  // Конструктор копіювання
  List(const List& obj)
  {
    // Тут потрібно робити копію зі списку,
    // щоб уникнути недоліків побітового копіювання
    Copy(obj);
  }

⇑

2.2.6. Оператор копіювання operator=(const List&)

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

public:

...

// Оператор копіювання
List<T>& operator=(const List& obj)
{
  // Викликати внутрішню функцію Copy()
  Copy(obj);
  return *this;
}

⇑

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

Метод Add() додає новий елемент в кінець списку. В методі створюється нова комірка типу Element<T>. Ця комірка заповнюється даними та додається в кінець списку. При додаванні розглядається два випадки:

додавання елементу до пустого списку;
додавання елементу до непустого списку.

public:

...

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

    // 2. Додати елемент
    // Визначити, чи елемент перший
    if (begin == nullptr)
    {
      // якщо елемент перший у списку
      begin = end = elem;
    }
    else
    {
      // якщо елемент не перший у списку,
      // то додати його в кінець списку.
      end->next = elem;
      end = elem;
    }

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

⇑

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

Метод Del() отримує вхідним параметром позицію елементу, який потрібно видалити зі списку. Елемент видаляється при умові, що позиція видалення є коректною.

public:

...

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

  // 2. Перевірка, чи коректне значення index
  if ((index < 0) || (index >= count))
    return;

  // 3. Видалення елементу.
  // Перевірка, чи видаляється перший елемент
  if (index == 0)
  {
    // 3.1. Якщо видаляється перший елемент
    Element<T>* t = begin; // запам'ятати адресу першого елементу
    begin = begin->next; // перейти на наступний елемент
    delete t; // звільнити перший елемент
  }
  else
  {
    // 3.2. Якщо видаляється не перший елемент.

    // 3.2.1. Перейти на елемент в позиції index-1
    Element<T>* t = Move(index - 1);

    // 3.2.2. Запам'ятати елемент який видаляється
    Element<T>* t2 = t->next;

    // 3.2.3. Встановити наступний елемент для елементу в позиції index-1
    t->next = t2->next; // працює коректно навіть для останнього елементу

    // 3.2.4. Видалити елемент на який вказує t2
    delete t2;
  }

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

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

⇑

2.2.9. Метод Del(). Видалити перший елемент зі списку

Модифікацією методу Del(int) є метод Del(), який видаляє перший елемент зі списку.

public:

...

// Видалити перший елемент зі списку
void Del()
{
  // Викликати перевантажений метод Del(int)
  Del(0);
}

⇑

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

Очищення списку реалізоване в методі Clear(), який звертається до методу Del() до тих пір, поки початок списку begin не стане рівним nullptr.

public:

...

// Метод, що видаляє всі елементи
void Clear()
{
  while (begin != nullptr)
  Del();
}

⇑

2.2.11. Метод Count(). Повернути кількість елементів списку

При необхідності отримати кількість елементів у списку, можна викликати метод Count(), який повертає значення внутрішньої змінної count.

public:

...

// Повернути к-сть елементів у списку
int Count() { return count; }

⇑

2.2.12. Операторна функція operator[](int). Індексування списку як масиву

Зручним способом звертання до елементу списку є звертання з допомогою операції індексування [ ] як у випадку з масивом. Щоб реалізувати це для класу List<T> потрібно перевантажити операторну функцію operator[](int). Щоб функція використовувалась у лівій та правій частині оператора присвоєння потрібно, щоб вона повертала посилання T&.

public:

...

// Оператор індексування списку як масиву
T& operator[](int index)
{
  // Перевірка, чи коректне значення index
  if ((index < 0) || (index > count - 1))
  {
    // Якщо не коректне, то викинути виключення
    throw out_of_range("Incorrect index.");
  }

  // Якщо значення index коректне,
  // то знайти потрібний елемент і повернути його значення
  Element<T>* t = Move(index);

  return t->data;
}

⇑

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

Для забезпечення зручності роботи зі списком додатково реалізовано метод Insert(), який вставляє елемент в задану позицію.

public:

...

// Вставка елементу item в задану позицію index.
// Позиція index нумерується з 0.
void Insert(T item, int index)
{
  // 1. Перевірка, чи коректне значення index,
  // тільки для випадку, якщо елементи є в списку
  if ((count != 0) && ((index < 0) || (index >= count)))
    return; // не робити ніякої вставки

  // 2. Спроба переходу до елементу в позиції index
  Element<T>* t = Move(index);

  // 3. Перевірка, чи існує список
  if (t == nullptr)
  {
    // 3.1. Якщо списку не існує, то додати елемент в кінець списку
    Add(item);
  }
  else
  {
    // 3.2. Якщо список існує, то реалізувати вставку
    try {
      // Спроба виділення пам'яті під нову комірку
      Element<T>* t2 = new Element<T>;
      t2->data = item;

      if (index == 0) // Якщо вставка в перший елемент
      {
        // Встановити початок списку на нову комірку
        t2->next = begin;
        begin = t2;
      }
      else
      {
        // Якщо вставка в другий, третій і т.д. елемент
        // Перейти до елементу index-1
        t = Move(index - 1);

        // Вставка в другий, третій і т.д. елемент
        t2->next = t->next;
        t->next = t2;
      }

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

⇑

2.2.14. Деструктор ~List()

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

public:

...

// Деструктор
~List()
{
  // Очистити список
  Clear();
}

⇑

2.2.15. Метод Print(). Виведення списку

Функція Print() виводить список, що представлений в поточному екземплярі класу.

// Виведення списку - тестування
void Print(string msg)
{
  cout << msg << endl;

  if (count == 0) // якщо пустий список
  {
    cout << "List is empty." << endl;
    return;
  }

  // Обхід списку
  Element<T>* t = begin;

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

⇑

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

У функції main() здійснюється створення списку та тестування базових методів списку.

void main()
{
  List<double> L; // Створити пустий список
  L.Print("L: ");

  // Пустий список
  L.Del();

  // Додати до списку елементи
  L.Add(2.5);
  L.Add(3.8);
  L.Add(4.1);
  L.Add(3.3);
  L.Print("L+4: ");

  // Видалити один елемент
  L.Del(2);
  L.Print("L-1: ");

  // Змінити елемент у списку
  L[0] = 77.8;
  L.Print("L[0] = 77.8: ");

  // Вивести елементи - доступ за індексом
  cout << "L[1] = " << L[1] << endl;
  double z = L[2];
  cout << "z = " << z << endl;

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

  List<double> L2 = L; // Конструктор копіювання
  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. Результат виконання програми

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