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

Характер информации о следующем элементе зависит от того, где конкретно хранится список. Например, если это оперативная память, то информация будет представлять собой адрес следующего элемента, если файл - позицию следующего элемента в файле. Мы с Вами будем рассматривать реализацию списка хранящегося в оперативной памяти, однако, при желании, вы сможете создать собственный код для хранения списка в файле. Итак, приступим:

Каждый элемент списка мы представим программно с помощью структуры, которая состоит из двух составляющих:

1.Одно или несколько полей, в которых будет содержаться основная информация, предназначенная для хранения.

2. Поле, содержащее указатель на следующий элемент списка.

Отдельные объекты подобной структуры мы далее будем называть узлами, связывая их между собой с помощью полей, содержащих указатели на следующий элемент.

    //узел списка	
    struct node
    {
	// Информационная часть узла 
	int value;

 	// Указатель на следующий узел списка 
      	node *next; 	
    };

После создания структуры, нам необходимо инкапсулировать её объекты в некий класс, что позволит управлять списком, как цельной конструкцией. В классе будет содержаться два указателя (на хвост, или начало списка и голову, или конец списка), а так же набор функции для работы со списком.

//голова
  	node *phead;

//хвост
node *ptail;

В целом, полученный список можно представить так:

Итак, основные моменты создания списка, мы рассмотрели, переходим непосредственно к его формированию.

Формирование списка. Отведем место для указателей в статической памяти.

  	node *phead;
node *ptail;

Зарезервируем место для динамического объекта.

phead=new node;

Присвоим значение переменной ptail, и поместим в информационное поле значение элемента.

ptail = phead;
  	ptail->value = "значение1";

Поместим в поле узла адрес еще одного - нового динамического объекта.

ptail->next = new node;

Переменная ptail должна содержать адрес последнего добавленного элемента, т. к. он добавлен в конец.

ptail = ptail->next;

Если требуется завершить построение списка, то в поле указателя последнего элемента нужно поместить NULL.

ptail->next = NULL;
  	ptail->value = "значение2";

В результате построен линейный односвязный список, содержащий два узла.

Вставка узла в определенное заданное место списка. Здесь и далее, мы не будем приводить фрагменты кода, так как они являются крупными. Позже мы с вами просто рассмотрим пример реализации односвязного списка целиком. А, сейчас, разберем операции над списком с помощью иллюстраций. Выделить память под новый узел. Записать в новый узел значение. Записать в указатель на следующий узел адрес узла, который должен располагаться после нового узла. Заменить в узле, который будет располагаться перед новым узлом, записанный адрес на адрес нового узла.

Удаление узла из списка. Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел в узле, предшествующем удаляемому. Удалить узел, предназначенный для удаления.

#include <iostream>
using namespace std;
 

struct Element
{
   // Данные
   char data;
   // Адрес следующего элемента списка
   Element * Next;
};

// Односвязный список
class List
{
   // Адрес головного элемента списка
   Element * Head;
   // Адрес головного элемента списка
   Element * Tail;
   // Количество элементов списка
   int Count;

public:
   // Конструктор
   List();
   // Деструктор
   ~List();
	
   // Добавление элемента в список
   // (Новый элемент становится последним)
   void Add(char data);
	
   // Удаление элемента списка
   // (Удаляется головной элемент)
   void Del();
   // Удаление всего списка
   void DelAll();
	
   // Распечатка содержимого списка
   // (Распечатка начинается с головного элемента)
   void Print();
	
   // Получение количества элементов, находящихся в списке
   int GetCount();
};

List::List()
{
   // Изначально список пуст
   Head = Tail = NULL;   
   Count = 0;
}

List::~List()
{
   // Вызов функции удаления
   DelAll();
}

int List::GetCount()
{
   // Возвращаем количество элементов
   return Count;
}

void List::Add(char data)
{
   // создание нового элемента
   Element * temp = new Element;

   // заполнение данными
   temp->data = data;
   // следующий элемент отсутствует
   temp->Next = NULL;
   // новый элемент становится последним элементом списка
   // если он не первый добавленный
   if(Head!=NULL){
		Tail->Next=temp;
		Tail = temp;
   }
   // новый элемент становится единственным
   // если он первый добавленный
   else{
	   Head=Tail=temp;
   }
}

void List::Del()
{
   // запоминаем адрес головного элемента
   Element * temp = Head;
   // перебрасываем голову на следующий элемент
   Head = Head->Next;
   // удаляем бывший головной элемент
   delete temp;
}

void List::DelAll()
{
   // Пока еще есть элементы
   while(Head != 0)
      // Удаляем элементы по одному
      Del();
}

void List::Print()
{
   // запоминаем адрес головного элемента
   Element * temp = Head;
   // Пока еще есть элементы
   while(temp != 0)
   {
      // Выводим данные
      cout << temp->data << " ";
      // Переходим на следующий элемент
      temp = temp->Next;
   }

   cout << "\n\n";
}

// Тестовый пример
void main()
{
   // Создаем объект класса List
   List lst;

   // Тестовая строка
   char s[] = "Hello, World !!!\n";
   // Выводим строку
   cout << s << "\n\n";
   // Определяем длину строки
   int len = strlen(s);
   // Загоняем строку в список
   for(int i = 0; i < len; i++)
      lst.Add(s[i]);
   // Распечатываем содержимое списка
   lst.Print();
   // Удаляем три элемента списка
   lst.Del();
   lst.Del();
   lst.Del();
   //Распечатываем содержимое списка
   lst.Print();
}