### C++ LL issue

The length of list is total num of nodes it contains. So am empty list has length 0. For example consider the below linked list.
Below linked list : has 4 nodes, I,J,K and L. Here node L is last node and its tail is terminator. The length of this list is 4.
I -> J -> K -> L ->

I am trying to write a function int solve(IntList * L) {
} given a non empty linked list L consisting of N nodes , returns its length.Here this function must return 4, assuming N ranges [1..5,000] and list L doesnt have a cycle (each non empty pointer points to different structure)/

Below is what i have tried so far.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131`` `````` //IntListNode.h file #ifndef INTLISTNODE_H #define INTLISTNODE_H #include using namespace std; struct IntListNode { int Value; IntListNode *next; IntListNode(int Value) : Value(Value), next(nullptr) { } }; class IntListNode { private: IntListNode *head; IntListNode *tail; public: IntListNode(); ~IntListNode(); void push_front(int); void pop_front(); bool empty() const; const int & front() const; const int & back() const; friend ostream & operator<<(ostream &, const IntListNode &); }; #endif INTLISTNODE_H //Solution.cpp #include using namespace std; #include "IntListNode.h" int main() { IntListNode listnode1; cout << "pushfront 10" << endl; listnode1.push_front(10); cout << "pushfront 20" << endl; listnode1.push_front(20); cout << "pushfront 30" << endl; listnode1.push_front(30); cout << "listnode1: " << listnode1 << endl; cout << "pop" << endl; listnode1.pop_front(); cout << "listnode1: " << listnode1 << endl; cout << "pop" << endl; listnode1.pop_front(); cout << "listnode1: " << listnode1 << endl; cout << "pop" << endl; listnode1.pop_front(); cout << "listnode1: " << listnode1 << endl; cout << "pushfront 100" << endl; listnode1.push_front(100); cout << "pushfront 200" << endl; listnode1.push_front(200); cout << "pushfront 300" << endl; listnode1.push_front(300); cout << "listnode1: " << listnode1 << endl; cout << endl; cout << "Calling listnode1 destructor..." << endl; } cout << "listnode1 destructor returned" << endl; // To test destructor on empty IntListNode { IntListNode listnode2; cout << "Calling listnode2 destructor..." << endl; } cout << "listnode2 destructor returned" << endl; return 0; }``````
Last edited on
> friend ostream & operator<<(ostream &, constIntListNode &);
The fact that this won't even compile, coupled with the lack of any indentation at all, suggests you just copy/pasted someone else's HTML page in the attempt to pass off something as your own work.

I have modified the code, please review it.
Perhaps something like this:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139`` ``````#include #include class IntList { private: struct IntListNode { int Value {}; IntListNode* next {}; IntListNode() {} IntListNode(int Value) : Value(Value) {} }; IntListNode* head {}; IntListNode* tail {}; size_t sze {}; public: IntList() {} ~IntList(); void push_front(int); void pop_front(); bool empty() const; const int& front() const; const int& back() const; size_t size() const; friend std::ostream& operator<<(std::ostream& os, const IntListNode& n) { return os << n.Value; } friend std::ostream& operator<<(std::ostream& os, const IntList& il) { for (auto cur {il.head}; cur; cur = cur->next) os << *cur << ' '; return os; } }; IntList::~IntList() { while (head) { auto cur {head}; head = cur->next; delete cur; } } void IntList::push_front(int i) { if (auto n {new IntListNode(i)}; !head) head = tail = n; else { n->next = head; head = n; } ++sze; } void IntList::pop_front() { if (head) { auto cur {head->next}; delete head; head = cur; if (!head) tail = head; --sze; } } bool IntList::empty() const { return sze == 0; } const int& IntList::front() const { if (!head) throw std::out_of_range("Empty"); return head->Value; } const int& IntList::back() const { if (!tail) throw std::out_of_range("Empty"); return tail->Value; } size_t IntList::size() const { return sze; } int main() { IntList listnode1; std::cout << "pushfront 10\n"; listnode1.push_front(10); std::cout << "pushfront 20\n"; listnode1.push_front(20); std::cout << "pushfront 30\n"; listnode1.push_front(30); std::cout << "listnode1: " << listnode1 << '\n'; std::cout << "Length is: " << listnode1.size() << '\n'; std::cout << "pop\n"; listnode1.pop_front(); std::cout << "listnode1: " << listnode1 << '\n'; std::cout << "Length is: " << listnode1.size() << '\n'; std::cout << "pop\n"; listnode1.pop_front(); std::cout << "listnode1: " << listnode1 << '\n'; std::cout << "Length is: " << listnode1.size() << '\n'; std::cout << "pop\n"; listnode1.pop_front(); std::cout << "listnode1: " << listnode1 << '\n'; std::cout << "Length is: " << listnode1.size() << '\n'; std::cout << "pushfront 100\n"; listnode1.push_front(100); std::cout << "pushfront 200\n"; listnode1.push_front(200); std::cout << "pushfront 300\n"; listnode1.push_front(300); std::cout << "listnode1: " << listnode1 << '\n'; std::cout << "Length is: " << listnode1.size() << '\n'; std::cout << "\bCalling listnode1 destructor...\n"; }``````

 ``` pushfront 10 pushfront 20 pushfront 30 listnode1: 30 20 10 Length is: 3 pop listnode1: 20 10 Length is: 2 pop listnode1: 10 Length is: 1 pop listnode1: Length is: 0 pushfront 100 pushfront 200 pushfront 300 listnode1: 300 200 100 Length is: 3 Calling listnode1 destructor... ```

NB Please don't modify previous posts (except for spelling etc) as that destroys the understanding of subsequent replies.
Last edited on
Hi Seeplus

I am trying to write a function int solve(IntListNode * L) {
}

given a non empty linked list L consisting of N nodes , returns its length.
Here this function must return 4, assuming N ranges [1..5,000] and list L does not have a cycle (each non empty pointer points to different structure)
Last edited on
 ``123456789101112131415161718192021222324252627282930313233343536`` ``````#include #include struct toy_list_node { int value ; toy_list_node* next = nullptr ; }; std::size_t size( const toy_list_node* n ) // return the length of the list { if( n == nullptr ) return 0 ; // empty list, size is zero else return 1 + size( n->next ) ; // otherwise size is one (for head) plus the size of what is there after head } void print( const toy_list_node* n ) { if( n == nullptr ) std::cout << "null\n" ; else { std::cout << n->value << " => " ; print( n->next ) ; } } int main() { // set up a linked list of nodes toy_list_node nodes[] { {1}, {2}, {3}, {4}, {5}, {6}, {7} } ; for( std::size_t i = 0 ; i < std::size(nodes)-1 ; ++i ) nodes[i].next = nodes+i+1 ; const toy_list_node* head = nodes ; print(head) ; // print the linked list std::cout << "size: " << size(head) << '\n' ; // compute and print its size }``````

http://coliru.stacked-crooked.com/a/bfd6b9aca0cf8735
@leo2008 - I just adapted your code to make it work. solve() is then simply:

 ``123`` ``````size_t solve(const IntList* pil) { return pil->size(); }``````

Your code looks more like a stack implementation based upon a list than a general list. Are you asking the question - given a stack which doesn't maintain a size element and which can't be iterated outside of the class definition - how do you determine the number of elements on the stack?
Last edited on
In this implementation logic, the linked list : has 4 nodes, I,J,K and L.
I -> J -> K -> L ->

Here node L is last node and its tail is terminator. The length of this list is 4.
The logic is more of stack based implementation, I am trying to write a function int solve(IntListNode * L) which must return 4.

Based on the structure declaration below, I am trying to write this function int solve(IntListNode * L). Here the pointer is called linked list if:
1) it is an empty pointer ( it is then called terminator or an empty list) or
2) it points to structure (called node or the head), that contains a value and linked list (called tail).

 ``123456789`` ``````//struct declaration struct IntListNode { int Value; IntListNode *next; }; ``````

Then possibly just simply:

 ``1234567891011121314151617181920`` ``````#include struct IntListNode { int Value {}; IntListNode* next {}; }; std::size_t solve(const IntListNode* n) { size_t sze {}; for (; n; ++sze, n = n->next); return sze; } int main() { IntListNode nodes[] {{'I', &nodes[1]}, {'J', &nodes[2]}, {'K', &nodes[3]}, {'L'}}; std::cout << "size: " << solve(nodes) << '\n'; }``````

 ``` size: 4 ```

Last edited on