Добавление нового узла в список
Для добавления нового узла в голову списка нужно выполнить последоватеьность действий, указанных в табл.15.
Таблица 15.
Добавление нового узла в голову списка
| № | Действие | Иллюстрация | ||||||||||||
| 1. | Выделить память под новый узел списка: list* ptr = new list. |
 | ||||||||||||
| 2. | Заполнить информационную часть узла и обнулить указатели в нем | 
 
 | ||||||||||||
| 3. | Если список пуст, то этот узел сделать головой списка: head = ptr. |
   
 | ||||||||||||
| 4. | Если список не пуст, то | |||||||||||||
| 4.1. | Для нового узла следующий указатель установить на голову текущего списка: ptr -> next = head. |
   
| ||||||||||||
| 4.2. | Для головы списка предыдущий указатель установить на новый узел: head -> back = ptr. |
 
  | ||||||||||||
| 4.3. | Установить на новый узел указатель на голову списка: head = ptr. |
        
|
int val;
list head;
list* ptr = new list;
ptr->value = val;
ptr->next = NULL;
ptr->back = NULL;
if (head == Nil) head = ptr //список пустой?
else
{
Ptr->next = head;
Head->back = ptr;
Head = ptr;
}
Добавление в хвост списка и после текущего узла списка (или перед текущим) делается аналогично:
int s
list tail;
list* ptr = new list;
ptr->value = val;
ptr->next = NULL;
ptr->back = NULL;
if (tail == NULL) tail = ptr //список пустой?
else
{
tail->next = ptr;
prt->back = tail;
tail = ptr;
}
Удаление узла из списка
При удалении узла из списка нужно рассмотреть следующие ситуации:
1. Удаляемый узел является головой списка.
2. Удаляемый узел является хвостом списка.
3. Удаляемый узел единственный в списке.
4. Удаляемый узел не является ни головой, ни хвостом, ни единственным в списке.
В конце процедуры удаления обязательно необходимо освободить ранее выделенную динамическую память для удаляемого узла с помощью стандартной процедуры free(). Разберем подробно последний случай 4, когда удаляется узел не с краев, а внутри списка (табл.16).
Таблица 16.
Удаление узла внутри списка
| № | Действие | Иллюстрация | ||||||||||||||||||||||
| 1. | На текущий узел указывает предыдущий узел. Этот указатель нужно «перекинуть» на следующий за текущим узел: cur->back->next =cur->next; |
   
 | ||||||||||||||||||||||
| 2. |
cur->next->back = cur->back; |
    | ||||||||||||||||||||||
| 3. |
|
       | ||||||||||||||||||||||
| 4. |
cur = cur->next; |
 
     | ||||||||||||||||||||||
| 5. | Освобождаем память, выделенную динамически для удаляемого узла списка: free(tail); |
     |
//удаление узла в списке
list head,tail,cur, temp;
// проверяем является ли узел единственным в списке?
if ((cur->next == NULL) && (cur->back = NULL))
{
head = NULL;
tail = NULL; // делаем список пустым
free(cur);
cur = NULL; //освобождаем память
}
else
if (cur->next == NULL) // текущий узел является хвостом?
{
tail = tail->back; // Хвостом теперь станет предпоследний узел
tail->next = NULL;
free (cur);
cur = tail;
}
else
if (cur->back == NULL) // текущий узел является головой?
{
head = head->next; // головой становится второй узел списка
head->back = NULL;
free (cur);
cur = head;
}
else //узел ни голова, ни хвост, ни единственный в списке
{
cur->back->next = cur->next;
cur->next->back = cur->back;
temp = cur;
cur = cur->next;
free (temp);
};
}