Добавление нового узла в список

Для добавления нового узла в голову списка нужно выполнить последоватеьность действий, указанных в табл.15.

Таблица 15.

Добавление нового узла в голову списка

 

№	Действие	Иллюстрация
1.	Выделить память под новый узел списка: list* ptr = new list.	ptr
2.	Заполнить информационную часть узла и обнулить указатели в нем	данные ptr
3.	Если список пуст, то этот узел сделать головой списка: head = ptr.	head данные
4.	Если список не пуст, то
4.1.	Для нового узла следующий указатель установить на голову текущего списка: ptr -> next = head.	ptr
4.2.	Для головы списка предыдущий указатель установить на новый узел: head -> back = ptr.	ptr
4.3.	Установить на новый узел указатель на голову списка: head = ptr.	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;	cur->back->next                 Cur->back         cur->next->back   Cur->next
2.	cur->back->next   Следующий узел за текущим после удаления текущего узла должен будет указывать на предыдущий от текущего узла. Заменяем этот указатель: cur->next->back = cur->back;	cur   Cur->next
3.	cur->back->next   Запомним указатель на текущий элемент во временном указателе tail: tail = cur;	Cur->back         cur->next->back     Cur->next
4.	cur->back->next   Текущим элементом списка будет теперь следующий за ним узел: cur = cur->next;	Cur->back         cur->next->back     Cur->next
5.	Освобождаем память, выделенную динамически для удаляемого узла списка: free(tail);	cur

 

//удаление узла в списке

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);

};

}