C++

Forum

 
 
Linked List adding node issue

Pages: 12
JRManx (603)
I've been working on a little project that requires linked lists, and it's been a long time since I did them...and things have gotten a bit rusty.

So, I wrote a practice program, and for some reason, it's not working.

Here's my code:
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
 
#include <iostream>

// List class
class List
{
private:
	
	// List node structure
	struct Node
	{
		double value;
		Node* next;
		
		// constructor to initialize a node
		Node (double valNode, Node* nextNode = nullptr)
		{
			value = valNode;
			next = nextNode;
		}
	};
	
	Node* head;
	
public:
	List ()
		{ head = nullptr; }
	
	void add (double x);
	void display ();
};

void List::add (double x)
{
	if (head == nullptr)
	{
		head = new Node (x);
	}
	else
	{
		Node* ptr = head;
		
		while (ptr -> next != nullptr)
		{
			ptr = ptr -> next;
			ptr -> next = new Node (x);
		}
	}
}

void List::display ()
{
	Node* ptr = head;
	
	while (ptr != nullptr)
	{
		std::cout << ptr -> value << std::endl;
		ptr = ptr -> next;
	}
}

int main ()
{
	List list1;
	
	list1.add (2.5);
	list1.add (103);
	list1.add (85.021);
	
	std::cout << "Displaying values: \n";
	
	list1.display ();
	
	return 0;
}


I tried debugging it, and it appears that nothing is actually getting stored in the succeeding nodes after the head. I don't know why...I did everything the book said.
(lldb) run
Process 62607 launched: '/home/Stored Documents/Programs/C++/Experiment  programs/linked_list' (x86_64)
Process 62607 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x0000000100000f93 linked_list`main(argc=1, argv=0x00007ffeefbffab0) at linked_list.cc:27
   24  		
   25  		list1.add (2.5);
   26  		
-> 27  		list1.add (103);
   28  		
   29  		list1.add (85.021);
   30  		
Target 0: (linked_list) stopped.
(lldb) print list1.head -> value
(double) $0 = 2.5
(lldb) print list1.head -> next
(List::Node *) $1 = 0x0000000000000000


Any input anyone has would be really helpful! It's probably one of those dumb mistakes where I overlooked something tiny but vital...but the debugger didn't catch it, so I don't know.

Thanks!
max
mbozzi (3912)
Transpose lines 45 and 46.
JRManx (603)
............................................________
....................................,.-‘”...................``~.,
.............................,.-”...................................“-.,
.........................,/...............................................”:,
.....................,?......................................................\,
.................../...........................................................,}
................./......................................................,:`^`..}
.............../...................................................,:”........./
..............?.....__.........................................:`.........../
............./__.(.....“~-,_..............................,:`........../
.........../(_....”~,_........“~,_....................,:`........_/
..........{.._$;_......”=,_.......“-,_.......,.-~-,},.~”;/....}
...........((.....*~_.......”=-._......“;,,./`..../”............../
...,,,___.\`~,......“~.,....................`.....}............../
............(....`=-,,.......`........................(......;_,,-”
............/.`~,......`-...............................\....../\
.............\`~.*-,.....................................|,./.....\,__
,,_..........}.>-._\...................................|..............`=~-,
.....`=~-,_\_......`\,.................................\
...................`=~-,,.\,...............................\
................................`:,,...........................`\..............__
.....................................`=-,...................,%`>--==``
........................................_\..........._,-%.......`\
...................................,<`.._|_,-&``................`\


I can't believe it...I spent an hour–literally–trying to figure out what in tarnation I did wrong. And you're just like "Switch these two lines." And it's like magic!

Looks like I misread the book, whoever wrote it made it look like line 45 was inside the loop.
1
2
3
4
5
6
 
ListNode *nodePtr = head;
while (nodePtr->next != nullptr)
	nodePtr = nodePtr->next;

// then they had some comments here
nodePtr->next = new listNode(number);


I hate it when people do that...it looks so confusing. It's easier to visually debug if people add curly brackets.

But thanks, @mbozzi! You saved me further hours of staring at it and wondering "what in the heck did I do"!
max

Also, I've been wanting to use that facepalm thing for a while now... ;)
Last edited on
mbozzi (3912)
Sometimes you just need a second set of eyes.

I hate it when people do that...it looks so confusing. It's easier to visually debug if people add curly brackets.

I've been convinced for a while now that lines normally devoted to braces would be better used for notation of more importance.

YMMV, of course. Actually doing this -- styling your code such that braces never have their own line -- is probably too weird for most C and C++ programmers to abide.
Last edited on
seeplus (6463)
@agentmax - Sorry, but I'm with the book. I hate extra braces...

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

class List {
public:
	List() {}

	void add(double x);
	void display() const;

private:
	struct Node {
		double value {};
		Node* next {};

		Node(double valNode, Node* nextNode = nullptr) : value(valNode), next(nextNode) {}
	};

	Node* head {};
};

void List::add(double x)
{
	if (head == nullptr)
		head = new Node(x);
	else {
		auto ptr {head};

		for (; ptr->next != nullptr; ptr = ptr->next);
		ptr->next = new Node(x);
	}
}

void List::display() const
{
	for (auto ptr {head}; ptr != nullptr; ptr = ptr->next)
		std::cout << ptr->value << '\n';
}

int main()
{
	List list1;

	list1.add(2.5);
	list1.add(103);
	list1.add(85.021);

	std::cout << "Displaying values: \n";

	list1.display();
}

Last edited on
JRManx (603)
@mbozzi,
Well, I find it much easier to read code if it's something like 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <iostream>
int main ()
{
    int num = 2;
    
    if (num == 2)
    {
    	std::cout << "Num equals two \n";
    }
    else
    {
    	std::cout << "Num does not equal two \n";
    }
    
    return 0;
}


rather than

1
2
3
4
5
6
7
8
9
10
11
 
#include <iostream>
int main(){
    int num = 2;
    
    if (num == 2)
    	std::cout << "Num equals two \n";
    else
    	std::cout << "Num does not equal two \n";
    
    return 0;
}


@seeplus,
Just a matter of preference, really. Personally, I can't understand why people put the brace right after the statement:
1
2
3
 
if (x == 0){
/*stuff*/
}


It makes it harder to read, as opposed to:
1
2
3
4
 
if (x == 0)
{
    /*stuff*/
}


I don't know about it being weird...it's how I was taught to write programs, to make them as easy to read as possible. Maybe that's not how it's generally done anymore?
George P (5604)
I can't understand why people put the brace right after the statement

It's the 1TBS, which is almost as old as the C language.
https://en.wikipedia.org/wiki/Indent_style#Variant:_1TBS_(OTBS)

What, you don't like "Egyptian braces"? Neither do I.

Those who worship at the altar of 1TBS believe the style is easier to read, really. *shrug*
Last edited on
JRManx (603)
Wow...I did not know there were that many ways of doing that, or that it was that controversial!

I think it really depends on what you're used to, or what you're taught...I was taught the "Allman Style," so that's what I'm used to.
JRManx (603)
Ok, I have added a destructor and a copy constructor to my linked list program, and I keep getting an "Abort trap: 6" message. It's probably a ridiculously simple fix like the last one, but I don't know...I had to write them from scratch because my book didn't have any examples.

Here are the destructor and the copy constructor:
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
 
// Copy constructor:
List::List (const List &list)
{
	if (list.head == nullptr)
	{
		head = new Node (0, nullptr);
	}
	else
	{
		head = new Node (list.head -> value, list.head -> next);
		
		Node* ptr = head;
		
		while (ptr -> next != nullptr)
		{
			ptr = new Node (ptr -> value, ptr -> next);
			ptr = ptr -> next;
		}
	}
}

// Destructor:
List::~List ()
{
	Node* ptr = head;

	while (ptr -> next != nullptr)
	{
		Node* trash = ptr;
		ptr = ptr -> next;
		delete trash;
	}
}


Here's the abort trap stuff, and the output:
103 is a member! 
13.6 is not a member. 

Displaying List1: 
2.5
103
85.24
12.001

Displaying List2: 
2.5
103
85.24
12.001
linked_list(85597,0x7fff9d3f9380) malloc: *** error for object 0x7fdb14400030: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6


I'm about 99% sure it has something to do with the destructor, because if I delete the destructor, it runs fine– no abort trap 6.

Something weird...When I compile it and run it in the debugger (lldb), it doesn't show the abort trap message, and then if I recompile it and run it in lldb, it shows the abort trap message! And so it alternates, I compile and run (in the debugger), and no abort trap; I compile and run again, and it gives me the abort trap!! This is only in my debugger, if I run it with Terminal, it still gives me the abort trap.

I have absolutely no clue what is going on here, other than that I think it is doing weird things with my computer memory.
Last edited on
seeplus (6463)
Try:

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

class List {
public:
	List() {}
	~List();

	List(const List&);

	void add(double x);
	void display() const;

private:
	struct Node {
		double value {};
		Node* next {};

		Node(double valNode, Node* nextNode = nullptr) : value(valNode), next(nextNode) {}
	};

	Node* head {};
};

void List::add(double x)
{
	if (head == nullptr)
		head = new Node(x);
	else {
		auto ptr {head};

		for (; ptr->next != nullptr; ptr = ptr->next);
		ptr->next = new Node(x);
	}
}

void List::display() const
{
	for (auto ptr {head}; ptr != nullptr; ptr = ptr->next)
		std::cout << ptr->value << '\n';
}

List::List(const List& list)
{
	for (auto ptr {list.head}; ptr != nullptr; ptr = ptr->next)
		add(ptr->value);
}

// Destructor:
List::~List()
{
	while (head != nullptr) {
		const auto trash {head->next};

		delete head;
		head = trash;
	}
}

int main()
{
	List list1;

	list1.add(2.5);
	list1.add(103);
	list1.add(85.021);

	std::cout << "Displaying values l1: \n";
	list1.display();

	const List list2(list1);

	std::cout << "Displaying values l2: \n";
	list2.display();
}



Displaying values l1:
2.5
103
85.021
Displaying values l2:
2.5
103
85.021

mbozzi (3912)
The list you've written has a dynamically allocated head node, which actually stores the first element. Therefore an empty list should always have a null pointer for head.

On lines 4 through 6 the copy constructor creates a head node for the new list even if the source of the copy has a null head - so it fails to properly copy an empty list.

Lines 16, 17 obtain a pointer to a new node and then immediately throw away the results; the newly-allocated node is never linked into the copy.

This explains the current problem, because the copied list shares structure with the old (nonempty) list as follows
         +---+   +---+   +---+
original |   +--->   +--->   +---> null
         +---+   +-^-+   +---+
                   |
         +---+     |
    copy |   +-----+
         +---+

Where the top left box is the head of the original list and the bottom left box is the head of the copy.

The copy is destroyed first, because the compiler calls destructors for objects in reverse order of their construction. This deletes the structure of the original list - the top row of boxes. When the original list's destructor runs, it attempts to delete copy.head->next which has already been deleted. This is a double free error.

The destructor is wrong because it accesses head->next even if head is a null pointer. This probably shares a root cause with the problem on lines 4-6.
mbozzi (3912)
Here's some code to chew on. Not directly related to your issue.

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
 
// Linked list sample code.

// This is a reasonable sketch of a real implementation of std::list, except
// that it is incomplete and untested: 
//   - no allocator support;
//   - no copy or move support;
//   - no node-based interface;

#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>

////////////////////////////////////////////////////////////////////////
struct list_node_base 
{
  list_node_base* next_;
  list_node_base* prev_;    
};

template <typename T>
  struct list_node: public list_node_base
  {
    template <typename... Args>
      explicit list_node(Args&&... args)
        : value_(std::forward<Args>(args)...) 
      {}
      
    T value_;  
  };
  
////////////////////////////////////////////////////////////////////////
template <typename T> class list;

template <typename T>
  class list_iterator
  {
    list_node_base* node_ = nullptr;
    
  public:
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using pointer = value_type*;
    using reference = value_type&;

    list_iterator() = default;
    explicit list_iterator(list_node_base* node)
      : node_{node}
    {}

    reference      operator*()     const noexcept;
    pointer        operator->()    const noexcept;
    list_iterator& operator++()    noexcept;
    list_iterator  operator++(int) noexcept;
    list_iterator& operator--()    noexcept;
    list_iterator  operator--(int) noexcept;

    bool operator==(list_iterator const&) const noexcept;
    bool operator!=(list_iterator const&) const noexcept;

    friend class list<T>;
    
  private:
    list_node<T>* value_node() const;
  };

// TODO(mbozzi): address exception safety requirements within list<T>
template <typename T>
  class list
  {
  public:
    using value_type       = T;
    using allocator_type   = std::allocator<T>;
    using pointer          = T*;
    using const_pointer    = T const*;
    using reference        = value_type&;
    using const_reference  = value_type const&;
    using size_type        = std::size_t;
    
    using iterator         = list_iterator<T>;
    using reverse_iterator = std::reverse_iterator<iterator>;

  private:
    // The last element in the list links to root_.  List iterators are defined
    // in terms of a pointer-to-node.  By definition, begin() refers to
    // root_.next_ and end() refers to root_.
    // 
    // Therefore when the list is empty, begin() == end().  If the list is
    // nonempty, the tail node is *root_.prev_.

    // NOTE(mbozzi): The end of the list, root_, is stored internally with the
    // list object.  This means that move construction would necessarily
    // invalidate ranges involving the end iterator.  
    // 
    // The workaround for this issue is to allocate the sentinel node
    // externally.  The downside is that this approach makes an non-throwing
    // move constructor impossible to write.  Both internal and external
    // sentinels are permitted by the standard, but these concerns are a general
    // limitation of all node-based containers.  The internal-sentinel
    // representation is slightly simpler to code.  S.A.: n4055 at
    // https://wg21.link/n4055.
    
    list_node_base root_;
    size_type      size_ = 0;
    
  public:
    ~list();
    
    list();

    // TODO(mbozzi): add copy and move support within list<T>
    list(list const& other) = delete;
    list& operator=(list const& rhs) = delete;

    iterator begin() noexcept;
    iterator end() noexcept;
    
    reverse_iterator rbegin() noexcept;
    reverse_iterator rend() noexcept;
    
    [[nodiscard]] bool empty() const noexcept;
    size_type size() const noexcept;
    
    reference front();
    reference back();

    template <typename... Args>
      reference emplace(iterator pos, Args&&...);

    void push_front(T const& x);
    void push_back (T const& x);

    iterator erase(iterator pos);
    
    void pop_front();
    void pop_back();

    void clear(); 
  };

////////////////////////////////////////////////////////////////////////
template <typename T>
  typename list_iterator<T>::reference list_iterator<T>::operator*() const noexcept
  {
    return value_node()->value_;
  }

template <typename T>
  typename list_iterator<T>::pointer list_iterator<T>::operator->() const noexcept
  {
    return value_node()->ptr_value();
  }

template <typename T>
  list_iterator<T>& list_iterator<T>::operator++() noexcept
  {
    node_ = node_->next_;
    return *this;
  }

template <typename T>
  list_iterator<T> list_iterator<T>::operator++(int) noexcept
  {
    return list_iterator{std::exchange(node_, node_->next_)};
  }

template <typename T>
  list_iterator<T>& list_iterator<T>::operator--() noexcept
  {
    node_ = node_->prev_;
    return *this;
  }

template <typename T>
  list_iterator<T> list_iterator<T>::operator--(int) noexcept
  {
    return list_iterator{std::exchange(node_, node_->prev_)};
  }

template <typename T>
  bool list_iterator<T>::operator==(
    list_iterator<T> const& other) const noexcept
  {
    return node_ == other.node_;
  }

template <typename T>
  bool list_iterator<T>::operator!=(
    list_iterator<T> const& other) const noexcept
  {
    return !(*this == other);
  }

template <typename T>
  list_node<T>* list_iterator<T>::value_node() const
  {
    return static_cast<list_node<T>*>(node_);
  }

////////////////////////////////////////////////////////////////////////
template <typename T>
  list<T>::~list()
  {
    clear();
  }

template <typename T>
  list<T>::list()
    : root_()
  {
    root_.next_ = &root_;
    root_.prev_ = &root_;
  }

template <typename T>
  typename list<T>::iterator list<T>::begin() noexcept
  {
    return list_iterator<T>(root_.next_);
  }

template <typename T>
  typename list<T>::iterator list<T>::end() noexcept
  {
    return list_iterator<T>(&root_);
  }

template <typename T>
  typename list<T>::reverse_iterator list<T>::rbegin() noexcept
  {
    return std::make_reverse_iterator(end());
  }

template <typename T>
  typename list<T>::reverse_iterator list<T>::rend() noexcept
  {
    return std::make_reverse_iterator(begin());
  }

template <typename T>
  bool list<T>::empty() const noexcept
  {
    return static_cast<bool>(size());
  }

template <typename T>
  typename list<T>::size_type list<T>::size() const noexcept
  {
    return size_;
  }

template <typename T>
  typename list<T>::reference list<T>::front()
  {
    return *begin();
  }

template <typename T>
  typename list<T>::reference list<T>::back()
  {
    return *--end();
  }

template <typename T>
template <typename... Args>
  typename list<T>::reference 
  list<T>::emplace(list_iterator<T> pos, Args&&... args)
  {
    list_node<T>*   new_node = new list_node<T>(std::forward<Args>(args)...);
    list_node_base* old_node = pos.node_->prev_;
    
    ++size_;
    
    new_node->next_ = old_node->next_;
    new_node->prev_ = old_node;
    
    old_node->next_->prev_ = new_node;
    old_node->next_        = new_node;

    return new_node->value_;
  }

template <typename T>
  void list<T>::push_front(T const& x)
  {
    emplace(begin(), x);
  }

template <typename T>
  void list<T>::push_back(T const& x)
  {
    emplace(end(), x);
  }

template <typename T>
  typename list<T>::iterator list<T>::erase(list<T>::iterator pos)
  {
    list_node<T>* n = static_cast<list_node<T>*>(pos.node_);
    
    list_node_base* after  = n->next_;
    list_node_base* before = n->prev_;

    after->prev_  = before;
    before->next_ = after;

    delete n;
    
    --size_;
    
    return list_iterator<T>(after);
  }

template <typename T>
  void list<T>::pop_front()
  {
    erase(begin());
  }

template <typename T>
  void list<T>::pop_back()
  {
    erase(--end());
  }

template <typename T>
  void list<T>::clear()
  {
    while (size()) pop_front();
  }


Live demo:
https://godbolt.org/z/chzbs6
Last edited on
JRManx (603)
@seeplus,
OH!!!!! Of course!!! I should have used the add() function inside the copy constructor!!! I'm dumb...

@mbozzi,
Ah...so it's trying to deallocate memory that has already been deallocated.

And it is...linking the old list to the new head???? What...?

Oh, I think I see. Wow...I should have seen that!

Thanks, guys! You have solved my problems once again!
max

P.S.
mbozzi,
What's that code, exactly? It looks for all the world like the C++ standard header files I found in my /include/c++/v1/ directory.
mbozzi (3912)
What's that code, exactly? It looks for all the world like the C++ standard header files

I wrote it for a guy who was trying to implement std::list. It follows std::list very closely. I chose to implement a subset of the interface from http://eel.is/c++draft/list#overview-2

The most interesting part about the list is that the pointers are linked in a circle.
The node that sits one-past-the-end of the list is also immediately before the first node in the list. This has the effect of eliminating most of the if-statements inside the list, makes it easier to write and understand.
Last edited on
dhayden (5795)
It's a bad idea to add to a linked list by walking through it to the end. Either add to the beginning of the list or keep a tail pointer. Warning: keeping a tail pointer can be tricky to implement.

This becomes clear when you consider:
Of course!!! I should have used the add() function inside the copy constructor!!!

No, you definitely should NOT. Using your add() function makes the copy constructor run in O(n2) time.

Regarding the use and placement of braces:

If I'm dealing with one statement and it fits on the same line, I won't use braces:
if (cond) statement;
but if the statement is long, I'll use the braces:
1
2
3
 
if (cond) {
  long statement;
}

The reason is simple. Two years from now, you'll find that you need to modify the code. Without braces, it's way to easy to change this:
1
2
 
if (cont)
    statement;

into this:
1
2
3
 
if (cond)
   statement;
   anotherStatement;

If course anotherStatement isn't actually inside the if condition.

I cuddle the braces whenever it makes sense. Consider an earlier example from this thread:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int main ()
{
    int num = 2;
    
    if (num == 2)
    {
    	std::cout << "Num equals two \n";
    }
    else
    {
    	std::cout << "Num does not equal two \n";
    }
    
    return 0;
}

That

code

is

quite

literally

double

spaced.

I think of braces as a syntactic necessity to be tolerated, not celebrated. If the compiler could read your mind about the block structure, you'd never write:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
int main ()

    int num = 2;
    
    if (num == 2)
    
    	std::cout << "Num equals two \n";
    
    else
    
    	std::cout << "Num does not equal two \n"; 
    
    return 0;

Instead, you'd write something like
1
2
3
4
5
6
7
8
9
 
int main ()
    int num = 2;
    
    if (num == 2)
    	std::cout << "Num equals two \n";
    else
    	std::cout << "Num does not equal two \n"; 
    
    return 0;

Or maybe you'd have even fewer blank lines. So why let braces push you around?
1
2
3
4
5
6
7
8
9
10
 
int main () {
    int num = 2;
    
    if (num == 2) {
    	std::cout << "Num equals two \n";
    } else { 
    	std::cout << "Num does not equal two \n"; 
    }
    return 0;
}
JRManx (603)
dhayden,
I don't really like "Egyptian braces," I think they don't flow as well as the style I use. But it's really a matter of opinion, and a lot of it probably has to do with what you learned; I learned the Allman style
1
2
3
4
 
if (thing)
{
    // other thing
}

but I see a lot of people (like you) using others. Nothing wrong with it, it's just a different style ;)

dhayden wrote:
So why let braces push you around?

I don't. I use them to separate sections of code, such as if/switch statements, loop bodies, etc.

And personally, I think 
1
2
3
4
 
if (thing)
{
    // other thing
}

flows better than 
1
2
3
 
if (thing) {
    // other thing
}

or 
1
2
 
if (thing)
    // other thing

Although I occasionally use the last one if I only need one line of code, because you can't fit more than one line of code inside it.

As for
dhayden wrote:
That

code

is

quite

literally

double

spaced.

En mi opiñon, it reads more easily that way. Takes up more space, true. But that's not a big deal for me, I have plenty of room on my monitor.

Have a good day!
max

mbozzi,
Wow, that's cool! I remember circular linked lists. Need to brush up on them so I can try writing my own again sometime...

Edit: I accidentally used Ganado's name in here...I meant to say mbozzi, sorry if I confused anyone.
Last edited on
Ganado (6785)

Ganado,
Wow, that's cool! I remember circular linked lists. Need to brush up on them so I can try writing my own again sometime...
??? I'm not even a part of this thread lol.
seeplus (6463)
Of course!!! I should have used the add() function inside the copy constructor!!!

No, you definitely should NOT. Using your add() function makes the copy constructor run in O(n2) time.


Quite right! In my defence I plead caffeine deficiency. Without using a tail pointer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
List::List(const List& list)
{
	Node* last {};

	for (auto ptr {list.head}; ptr != nullptr; ptr = ptr->next) {
		const auto newnode {new Node(ptr->value)};

		if (head == nullptr)
			head = newnode;

		if (last != nullptr)
			last->next = newnode;

		last = newnode;
	}
}



Why does add() need to add to tail of list and not to head of list (which is much easier)?
Last edited on
dhayden (5795)
The copy constructor can be done easier with a Node ** to the head, or the last Node's next pointer. It other words, it points to where the next node will be linked in.

When copying data, I find that using the names src and dst helps avoid confusion:
1
2
3
4
5
6
7
8
 
List::List(const List &rhs)
{
    Node **dst, *src;
    for (src = rhs.head, dst = &head; src; src = src->next, dst = &(*dst)->next) {
        *dst = new Node(src->value);
    }
    *dst = nullptr;
}

The for loop looks complicated but it really just walks src and dst down two lists at the same time. src points to the current node in the source list. dst points to the pointer where it will be linked in.
JRManx (603)
Ganado,
Oops, sorry! I was talking to mbozzi, and I guess I got mixed up– no offense taken, I hope? I will edit that ASAP.

seeplus,
Why auto? My book said to initialize nodes of a list as Node*, and that's what I remember learning. Also, why would I need a tail pointer? I know if I was making a circular linked list, I would need one, but I'm not.

dhayden wrote:
Using your add() function makes the copy constructor run in O(n2) time.


Why would calling the add() function inside the copy constructor cause it to run "O(n2) times"? What does that even mean, exactly? I've never heard it before.
Pages: 12