Как посчитать количество узлов в связанном списке, не пересекая его?

Question

Меня спросили в интервью, как подсчитать количество узлов в связанном списке, не просматривая список? Есть ли способ добиться этого?

Answer 1

Единственный способ, которым я могу придумать, - это добавить счетчик количества узлов, который увеличивается каждый раз, когда вызываются методы add или insert , и уменьшается, когда delete вызывается.Вы не можете делать предположения о занимаемой памяти, потому что, будучи связанным списком, вы не можете гарантировать, что все узлы будут в одном и том же блоке памяти (действительно, это крайне маловероятно).

Answer 2

Если вы делаете распределение динамически с чем-то вроде malloc, то нет другого способа, кроме обновления счетчика каждый раз, когда вы вставляете / удаляете. Если вы не делаете динамическое распределение, значит, вы, вероятно, не реализовали связанный список.

Answer 3

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

Answer 4

То, что говорят эти парни, совершенно верно. Как узнать, сколько предметов в чем-то есть, прежде чем посмотреть на них?

Вам нужно будет вести подсчет и увеличивать / уменьшать его при вставке / удалении. Это (самый | единственный) надежный способ.