Как удалить элемент из списка?, программирование Опции Рейтинг

[ierton]

Весь форум не читал, прошу прощения если задача с бородой. Говорят, что спрашивали на собеседовании в гугле.

Нужно реализовать удаление элемента односвязного списка, имея только указатель на удаляемый элемент (известно, что он не является последним). Другими словами, нужно сделать так, чтобы предыдущий элемент стал связан с следующим за данным.

Короче говоря:

struct Item { void* data; struct Item * next; } ;

void delete_item(struct Item * item)
{
???
}

Список конечный, признак последнего элемента - p.next == 0. Язык - С.

[Troublemaker]

Весь форум не читал, прошу прощения если задача с бородой. Говорят, что спрашивали на собеседовании в гугле.

Нужно реализовать удаление элемента односвязного списка, имея только указатель на удаляемый элемент (известно, что он не является последним). Другими словами, нужно сделать так, чтобы предыдущий элемент стал связан с следующим за данным.

Короче говоря:

struct Item { void* data; struct Item * next; } ;

void delete_item(struct Item * item)
{
???
}

Список конечный, признак последнего элемента - p.next == 0. Язык - С.

Так, не понял, а где указатель на начало списка? Про него ничего не сказано...

P.S. Понял, в этом вся фишка вопроса. Но в таком случае ответ не чистый. Никакой уверенности в том, что на указанные элементы не ссылается кто-то извне, нет. Стало быть этот момент нужно уточнять.

[Powered by Java]

Так, не понял, а где указатель на начало списка? Про него ничего не сказано...

P.S. Понял, в этом вся фишка вопроса. Но в таком случае ответ не чистый. Никакой уверенности в том, что на указанные элементы не ссылается кто-то извне, нет. Стало быть этот момент нужно уточнять.

В идеале, есть public List, в нем куча методов для работы с данными и private структура/класс Item. Так что внешних ссылок быть не должно, а head хранится непосредственно в List, у которого и просят имплементировать удаление.
Кстати, проблему с последним элементом вполне возможно решить, но не средствами структуры, конечно.
PS: однонаправленные списки - ЗЛО!

[Troublemaker]

В идеале, есть public List, в нем куча методов для работы с данными и private структура/класс Item. Так что внешних ссылок быть не должно, а head хранится непосредственно в List, у которого и просят имплементировать удаление.
Кстати, проблему с последним элементом вполне возможно решить, но не средствами структуры, конечно.
PS: однонаправленные списки - ЗЛО!

Тогда предлагаю "многонаправленные":

Есть список со случайными связями. То есть он однонаправленный (есть поле .next), кроме того, есть поле .random, которое ссылается на некий элемент из этого же списка. Задача: клонировать данный список (с сохранением связей). Ограничение: памяти использовать не больше, чем нужно для изначального списка и для нового.