C++

Forum

 
C++ LL issue

leo2008 (147)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 

//IntListNode.h file

#ifndef INTLISTNODE_H
#define INTLISTNODE_H

#include <iostream>

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 <iostream>

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
salem c (3700)
> 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.

leo2008 (147)
I have modified the code, please review it.
seeplus (6591)
Perhaps something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <iostream>
#include <exception>

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
leo2008 (147)
Hi Seeplus

Thanks for your detailed reply.
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
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <iterator>

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
seeplus (6591)
@leo2008 - I just adapted your code to make it work. solve() is then simply:

1
2
3
 
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
leo2008 (147)
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).

1
2
3
4
5
6
7
8
9
 
//struct declaration 

struct IntListNode {

int Value;

IntListNode *next;
};

seeplus (6591)
Then possibly just simply:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>

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
Topic archived. No new replies allowed.