Data structures: Linked list

Совсем краткое описание. 

Связный список - структура данных, имеющая набор своих данных и содержащая ссылку на следующий элемент  (или две ссылки: одна на следующий, одна на предыдущие). В случае, если  

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

Однонаправленный список: 

Код построения связного списка:

#ifndef LINKED_LIST
#define LINKED_LIST

template <typename ItemType>

struct linked_list
{
  ItemType Item;
  linked_list *Next;

  linked_list(ItemType item)
  {
    Item=item;
    Next=NULL;
  };
};

Код добавления нового элемента в список:

template <typename ItemType>

void add_item(linked_list *list, ItemType Item) 

{ 

   list=(list->Next=new linked_list(Item)); 

}
Удалить элемент из списка можно достаточно просто, если элемент находится вначале или в конце списка. Если элемент находится где то посередине списка:

Алгоритм следующий:

1. Идем по списку начиная с перового элемента X и находим элемент Y, который нужно удалить (случай когда требуемый элемент в списке не найден здесь не рассматривается).

while (X->Next->Item!=required_item )   
{
     X=X->Next; 
};

Y=X->Next;

2. После того как элемент найден, удаляем его следующим образом:

X->Next=Y->Next;

Итого код удаления элемента из списка:

template <typename ItemType> 

void remove_item(linked_list *list, ItemType required_item)
{ 
  while (X->Next->Item!=required_item)   
  {
      X=X->Next; 
  };

  Y=X->Next;
  X->Next=Y->Next;
};