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

[ierton]

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

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

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

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

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

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

[Alexandroppolus]

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

[De_Bill]

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

[Powered by Java]

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

Так и надо Главное не забыть оригинальный следующий обнулить, что бы память не текла.

[Alexandroppolus]

Блин, точно! Ведь знал же когда-то (совсем недавно)...

[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, которое ссылается на некий элемент из этого же списка. Задача: клонировать данный список (с сохранением связей). Ограничение: памяти использовать не больше, чем нужно для изначального списка и для нового.

[De_Bill]

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

поиск в глубину надо провернуть

[Powered by Java]

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

поиск в глубину надо провернуть

А поподробнее?

[De_Bill]

Ну там какой-то странный вариант дфса конечно получается ну да ладно. хотя да, это вообще будет не дфс

идем по некстам до конца первого списка, создаем элементы второго, пока что только с полями некст
дальше берем i-тый элемент первого списка(Аi), и соответствующий ему эл-т второго списка (Bi)
пишем
Item1=A1
Item2=A2
while (Item1!=Ai.random){
Item1=Item1.next
Item2=Item2.next
}
Bi.random=Item2;

Ну и прокручиваем это для каждого i

Конечно тут две лишних переменных, но, думаю, это ничего

[Powered by Java]

Ну там какой-то странный вариант дфса конечно получается ну да ладно. хотя да, это вообще будет не дфс

идем по некстам до конца первого списка, создаем элементы второго, пока что только с полями некст
дальше берем i-тый элемент первого списка(Аi), и соответствующий ему эл-т второго списка (Bi)
пишем
Item1=A1
Item2=A2
while (Item1!=Ai.random){
Item1=Item1.next
Item2=Item2.next
}
Bi.random=Item2;

Ну и прокручиваем это для каждого i

Конечно тут две лишних переменных, но, думаю, это ничего

т.е. рандом элементы искать для каждого элемента нового списка? Слишком уж долго... О(n^2)...

[De_Bill]

Все зависит от того насколько сильно ограничение по памяти. Понятно что с булевским массивом или еще чем любой дуралей за О(n) решит

[Powered by Java]

Все зависит от того насколько сильно ограничение по памяти. Понятно что с булевским массивом или еще чем любой дуралей за О(n) решит

А надо за О(n) и без памяти лишней
PS: предлагаю финальное решение этой задачи через личку обсуждать. Пусть остальные тоже голову поломают

[Alexandroppolus]

А надо за О(n) и без памяти лишней
PS: предлагаю финальное решение этой задачи через личку обсуждать. Пусть остальные тоже голову поломают

Есть вариант ответа, кому скинуть в личку - Вам или Troublemaker?

[Powered by Java]

Есть вариант ответа, кому скинуть в личку - Вам или Troublemaker?

Полагаю, Troublemaker ответ знает, раз написал тут задачу...
Я знаю алгоритм. Могу проверить ваш

[Alexandroppolus]

Полагаю, Troublemaker ответ знает, раз написал тут задачу...
Я знаю алгоритм. Могу проверить ваш

Отправил в личку (та, которая форумная)

[Alexandroppolus]

Для всех интересующихся уточню: на этот раз структура элемента
Item { Item * next; Item * random};

т.е. только 2 указателя для маневров.
Рандомная ссылка, как я понял, может указывать вперед и назад.

В таком виде пока не решил. (
upd: решил, интересная задачка)

[ierton]

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

Нет, здесь идея именно в том, что указатель на начало списка неизвестен.

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

Да, это и есть решение

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

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

Верно, гарантии нет. Но условие и не требует от решения каких-либо гарантий, лишь бы итоговый список оказался правильным. Боюсь, что если уточнять, то совсем очевидно станет.

[Troublemaker]

Полагаю, Troublemaker ответ знает, раз написал тут задачу...
Я знаю алгоритм. Могу проверить ваш

А не в той ли компании Вы работаете, где эту задачку давали на собеседовании?

P.S. Ответ знаю