Размер связанного списка в функции C++

Question

Может кто-нибудь рассказать, что такое код для проверки размера связанного списка (количество узлов). Это то, что мой код (вставка и удаление головы + информация о печати всех узлов)

struct node 
{ 
    int info; 
    node *nextptr; 
}; 

class list 
{ 
private: 
    node *L,*tail; 
    int count; 

public: 
    list() 
    { 
     L=tail=NULL; 
     count=0; 
    } 

    void InsertHead(int info); 
    int RemoveHead(); 
    void Print(); 
}; 

Answer 1

Ну, самый простой бы Бето добавить в функции InsertHead добавить ++ рассчитывать и в RemoveHead сделать --count

В противном случае вы можете использовать цикл, чтобы перейти в перечне

eg

node* p = L; 
while (p != NULL) 
{ 
    ++count; 
    p = p->nextptr; 
} 

Answer 2

Вам нужно создать счетчик, а затем через петлю в списке увеличения счетчика

псевдокод:

count = 0 
iterator = head 
while(iterator != 0) 
    count++ 
    iterator = iterator.next 

Answer 3

Попробуйте это:

int size() { return count; } 

Answer 4

Что-то вроде:

int Count() 
{ 
    return count; 
} 

Answer 5

Существует два способа управления размером связанного списка, оба имеют недостатки. Простейшим является управление переменной count, ваш класс имеет такую ​​переменную, и вы увеличиваете ее каждый раз, когда вы добавляете узел в список, и уменьшаете его каждый раз, когда вы удаляете узел.

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

Если вы хотите, чтобы сплайсинг был постоянным, вы не можете отслеживать размер списков. Поэтому в любое время, когда вы хотите получить размер списка, вы должны подсчитать, сколько узлов есть.