Удаление узла из однонаправленого списка

Как правильно удалить узел из однонапрвленого списка: элементами которого есть структура struct Node { Object* element; Node* next; }. Задание очень общее--удалить элемент из середины--чтобы список остался связным в одном направление. Я так понимаю эти узлы надо как то пронумеровать (присвоить имена), в том числе тому который удаляется. Или использовать функцию размера списка: Будет ли правильным такой подход. While (Node(i)->next!=NULL) {if (Node(i)->next==Node(k)) Node(i)->next=Node(k+1)} или использование (int i=0; i<List<Node> l.size(); i++) в начале предыдущего кода?...

Из середины-то удалить легко: Node->next = Node->next->next;. Вот для удаления из начала
нужен будет указатель на указатель.

Posted via ActualForum NNTP Server 1.5

Dimitry Sibiryakov,
да проверил -- есть такое представление указателя -- node->next->next -- хотя єто лиш упрощенная форма того что Я написал. Ну а delete node.element -- не надо применять? И какой там указатель надо удаление из начала списка--если список направленный из начала в конец указателями?

Dimitry Sibiryakov
Из середины-то удалить легко: Node->next = Node->next->next;. Вот для удаления из начала нужен будет указатель на указатель.

А освобождение памяти для удалённого элемента?

Вероятно удаление может быть сделано более изящно (надо полагать появятся другие варианты, когда Сообщество проснётся), но вы можете потестировать пока мой. Я его не проверял.

struct Node
{
	int data;
	struct Node* next;
}* head;


void removeNode(struct Node* el)
{
	struct Node* t;
	if (el == head){
		t = head;
		head = head->next;
		free(t);
	}
	else{
		for (struct Node* prev = head; prev->next; prev = prev->next){
			if (prev->next == el){
				t = prev->next;
				prev->next = prev->next->next;
				free(t);
				break;
			}
		}
	}
}

SashaMercury,

не удалит последний элемент из списка.

Mozok
SashaMercury, не удалит последний элемент из списка.

Нет, код Саши правилен.

Может быть кто-нибудь предложит более изящный/красивый вариант на Си ? Алгоритм, надо полагать, будет аналогичный (при известных head и указателе на удаляемый элемент), однако, мне кажется, что реализация может быть красивее

SashaMercury
Может быть кто-нибудь предложит более изящный/красивый вариант на Си ? Алгоритм, надо полагать, будет аналогичный (при известных head и указателе на удаляемый элемент), однако, мне кажется, что реализация может быть красивее

Предлагаю не делать различий между головой и другими элементами.
Это красивше

void removeNode(struct Node* el)
{
    for (struct Node** prev_next = &head; *prev_next; prev_next = &(*prev_next)->next) {
        if (*prev_next == el){
            *prev_next = el->next;
            free(el);
            break;
        }
    }
}

Анатолий, спасибо за пример :)