C++

Forum

 
Infinite Loop in Doubly Linked List

JCSmith (5)
Like the title says I'm experiencing an infinite loop in my doubly linked list. Using gdb I've found the infinite loop to be in my size() function and walking through the main i've seen that the first time insert_after is called is when the loop begins.

I have been working on it for sometime but I can't seem to find out where the error lies in my insert_after function or why it would be causing the size function to loop infinitely.

Thanks for any help.

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
 
  #include <iostream>
#include <fstream>
#include "dlist.h"
#include "swatch.h"
#include "node_iterator.h"

using namespace std; 

int main() 
{	
	dlist<Swatch> swatches;
	dlist<Swatch>::iterator it; 
	ifstream fin; 
	fin.open("swatches.txt"); 
	if (fin.fail())
	{
		cout << "Could not open input file." << endl; 
		return 1; 
	}
	Swatch tmp; 
	while (fin >> tmp)
	{
		int red = tmp.get_red(); 
		int green = tmp.get_green(); 
		int blue = tmp.get_blue(); 
		
		if ( (red>=green) && (red>=blue) ) // red is dominant
		{
			swatches.front_insert(tmp); 
		}
		else if ( (green >= red) && (green >= blue) ) 
				// green is dominant
		{
			swatches.rear_insert(tmp); 
		}
		else // blue is dominant
		{
		   it = swatches.begin();
		   for(int i = 0;i < swatches.size()/2;i++)
			++it; // loop moves iterator to the middle
		   if(swatches.size()%2 == 1){
			if(swatches.size()>2){
			it++;
			}
			swatches.insert_before(it,tmp);
		   }
		   else{
			swatches.insert_after(it,tmp);
		   }
		}
	}
	fin.close(); 

	dlist<Swatch> copy(swatches); // make a copy
	
	// remove the front, back, and centermost swatch from the copy
	copy.front_remove(); 
	copy.rear_remove(); 
	it = copy.begin();
	for(int i =0; i < copy.size()/2; ++i)
		++it;
	if(copy.size()%2 ==1) ++it; // if list has a true middle
					// step up into it
	copy.remove(it);
	
	
	// output the original list frontwards
	for (dlist<Swatch>::iterator i=swatches.begin(); i != swatches.end(); ++i)
	{
		cout << *i << endl; 
	}
	
	cout << endl << endl; // some space
	
	// output the copy frontwards
	for (dlist<Swatch>::iterator i=copy.begin(); i != copy.end(); ++i)
	{
		cout << *i << endl; 
	}

	cout << endl << endl; // some space

	// output the original backwards
	for (dlist<Swatch>::iterator i=swatches.r_begin(); i != swatches.r_end(); --i)
	{
		cout << *i << endl; 
	}
	
	cout << endl << endl; // some space

	// destroy the original list by alternating between removal of first and 
	// last items.  Print each item as it is removed
	int counter=0; 
	while (swatches.size() > 1)//0
	{
		if (swatches.begin() != NULL)
			cout<<*swatches.begin()<<endl;
		swatches.front_remove();
	
		 if(swatches.r_begin() != NULL)//if(swatches.size() > 0){
		    cout<<*swatches.r_begin()<<endl;
		swatches.rear_remove();
	}

	cout << endl << endl; // some space

	// output the copy backwards
	for (dlist<Swatch>::iterator i=copy.r_begin(); i != copy.r_end(); --i)
	{
		cout << *i << endl; 
	}

	return 0; 
}


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
 
#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include "dnode.h"
#include "node_iterator.h"

template <class T>
class dlist {
        public:
            typedef node_iterator<T> iterator; //
            typedef node_iterator<T> const_iterator;//

            dlist(dnode<T> *h = NULL, dnode<T> *t = NULL) {head = h; tail = t;}
            ~dlist(); //

            dlist(const dlist& other);//
            dlist& operator =(const dlist& other);//

            void front_insert(const T& item);//
            void front_remove();//
            void rear_insert(const T& item);//
            void rear_remove();//
            void show();//

            iterator begin() {return iterator(head);}
            const_iterator begin() const{return const_iterator(head);}

            iterator end() {return iterator();}
            const_iterator end() const{return const_iterator();}

            iterator r_begin() {return iterator(tail);}
            const_iterator r_begin() const{return const_iterator(tail);}

            iterator r_end() {return iterator(head->prev());}
            const_iterator r_end() const {return const_iterator(head->prev());}

            void insert_before(iterator spot, T item);//
            void insert_after(iterator spot, T item);//
            void remove(iterator spot);//

            int size();

        private:
            dnode<T> *head;
            dnode<T> *tail;
};

#include "dlist.template"

#endif
JCSmith (5)
Here is the "dlist.template" file with my insert_after function.

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
 
template <class T>
dlist<T>::~dlist(){
        dnode<T> *cur;

        while(head != NULL){
                cur = head->next();
                delete head;
                head = cur;
        }
        tail = NULL;
}


template <class T>
dlist<T>::dlist(const dlist<T>& other){
        if(!other.head)
                head = tail = NULL;
        else{
                head = new dnode<T>(other.head->data());

                dnode<T> *dest = head;
                dnode<T> *source = other.head;

                while(source != NULL){
                        dest->set_next(new dnode<T>);
                        dest = dest->next();
                        dest->set_data(source->data());
                        source = source->next(); //
                }
                dest->set_next(NULL);
                tail = dest;
        }
        
        
}

template <class T>
dlist<T>& dlist<T>::operator =(const dlist<T>& other){
        if(this == &other)
                return *this;

        dnode<T> *rmptr;

        while(head != NULL){
                rmptr = head;
                head = head->next();
                delete rmptr;
        }

        tail = NULL;
        const dnode<T> *source = other.head;

        while(source != NULL){
                rear_insert(source->data());
                source = source->next();
        }
}

template <class T>
void dlist<T>::show()
{
	dnode<T> *new_head = head;
	dnode<T> *temp;
	
	while(new_head != NULL)
	{
		std::cout << new_head->next();
		new_head = new_head->next();
	}
}

template <class T>
void dlist<T>::front_insert(const T& item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                head = new dnode<T>(item);
                head->set_next(tail);
                tail->set_prev(head);
        }else{
                dnode<T> *old_head = head;
                head = new dnode<T>(item);
                head->set_next(old_head);
                old_head->set_prev(head);
        }
}

template <class T>
void dlist<T>::front_remove(){
        iterator rmspot = head;
        remove(rmspot);
}

template <class T>
void dlist<T>::rear_insert(const T& item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                tail = new dnode<T>(item);
                tail->set_prev(head);
                head->set_next(tail);
        }else{
                dnode<T> *old_tail = tail;
                tail = new dnode<T>(item);
                tail->set_prev(old_tail);
                old_tail->set_next(tail);
        }
}

template <class T>
void dlist<T>::rear_remove(){
        iterator rmspot = tail;
        remove(rmspot);
}

template <class T>
void dlist<T>::insert_before(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(spot == end())
				front_insert(item);
        else if(head == tail){
                head = new dnode<T>(item);
                tail->set_prev(head);
                head->set_next(tail);
        }else if(head == spot.current)
                front_insert(item);
        else if(spot.current != NULL){
                dnode<T> *s = spot.current;
                dnode<T> *new_node = new dnode<T>(item, s, s->prev());
                s->prev()->set_next(new_node);
                s->set_prev(new_node);
        }
    
}

template <class T>
void dlist<T>::insert_after(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(spot == end())
				rear_insert(item);
        else if(head == tail){
                tail = new dnode<T>(item);
                head->set_next(tail);
                tail->set_prev(head);
        }else if(spot.current == tail)
                rear_insert(item);
        else if(spot.current != NULL){
                dnode<T> *s = spot.current;
                dnode<T> *new_node = new dnode<T>(item, s, s->next());
                s->next()->set_prev(new_node);
                s->set_next(new_node);          
        }
}

template <class T>
void dlist<T>::remove(iterator spot){
        dnode<T> *rmptr = spot.current;

        if(rmptr){
                if(head == NULL)
                        std::cout << "Can't remove anything, list is empty.\n";
                else if(rmptr == head && rmptr == tail){
                        delete rmptr;
                        head = tail = NULL;
                }else if(rmptr == head){
                        dnode<T> *new_head = head;
                        head = head->next();
                        delete new_head;
                        head->set_prev(NULL);
                }else if(rmptr == tail){
                        dnode<T> *new_tail = tail;
                        tail = tail->prev();
                        tail->set_next(NULL);//set_prev
                        delete new_tail;
                        new_tail = NULL;
                }else{
                        rmptr->prev()->set_next(rmptr->next());
                        rmptr->next()->set_prev(rmptr->prev());
                        delete rmptr;
                        rmptr = NULL;
                }
        }
}

template <class T>
int dlist<T>::size(){
        int len = 0;
        dnode<T> *new_head = head;

        while(new_head != NULL)
		{
                len++;
                new_head = new_head->next();
        }

        return len;
}
TheIdeasMan (6817)
Hi,

I am probably out of my depth here, but who knows these ideas might be useful :+)

So it is Swatch::size() that causes the infinite loop, not dlist::size() ? If you are using the debugger, you should be able to see why it is not meeting the end condition?

Are the tail pointers always guaranteed to to be null? Should use C++11's nullptr instead of NULL

When doing an else if chain, always put an else with some kind of warning - maybe a static_assert or even a std::cout if that is feasible. So this will catch anything not matching the other else if's . Edit: The insert_before and insert_after functions don't have this

Are you allowed to use smart pointers? They are better than using new - which should probably be avoided like the plague :+)

Cheers :+)

Last edited on
Topic archived. No new replies allowed.