Пример реализации линейного односвязного (однонаправленного) списка для обобщенного типа T. Список представлен в оперативной памяти

В примере демонстрируется разработка шаблонного класса, предназначенного для реализации односвязного списка, организуемого в оперативной памяти. Класс реализован в консольном приложении. Используя буфер обмена можно объединить коды нижеследующих программных элементов и получить работоспособный код класса.

Перед изучением данной темы рекомендуется ознакомиться со следующей темой:

• Линейный односвязный список. Общие сведения. Базовые операции со списком

---

Содержание

• 1. Программные составляющие
• 2. Программный код на языке C++
  • 2.1. Базовый узел. Структура Element
  • 2.2. Класс List<T>
    • 2.2.1. Добавление внутренних полей
    • 2.2.2. Внутренняя функция Move(int)
    • 2.2.3. Метод Copy(const List&). Сделать копию из списка
    • 2.2.4. Конструктор по умолчанию List()
    • 2.2.5. Конструктор копирования List(const List&)
    • 2.2.6. Оператор копирования operator=(const List&)
    • 2.2.7. Метод Add(T). Добавить новый элемент в конец списка
    • 2.2.8. Метод Del(int). Удалить элемент из списка в заданной позиции
    • 2.2.9. Метод Del(). Удалить первый элемент из списка
    • 2.2.10. Очистка списка. Метод Clear()
    • 2.2.11. Метод Count(). Вернуть количество элементов списка
    • 2.2.12. Операторная функция operator[](int). Индексирование списка как массива
    • 2.2.13. Метод Insert(T, int). Вставка элемента в заданную позицию
    • 2.2.14. Деструктор ~List()
    • 2.2.15. Метод Print(). Виведення списку
• 3. Функция main(). Клиентский код
• 4. Результат выполнения программы
• Связанные темы

---

Поиск на других ресурсах:

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. Проверка, равно ли количество элементов нулю
    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

  ⇑

---

Связанные темы

• Линейный односвязный список. Общие сведения. Базовые операции со списком
• Линейный двухсвязный список. Общие сведения. Базовые операции со списком
• Линейный двухсвязный список. Пример шаблонного класса
• Разработка шаблонного класса, реализующего стек в виде односвязного списка

  ⇑

---