C++

Forum

 
Linked LIsts

awhetton90 (1)
I was to create a linkedlist template class to be able to learn the basic functions of the linked list. I have gone through everything, but in the test driver provided, for some reason my code is not running. It seems to be going through an infinite loop when it runs the size() function in the T at function. Can somebody please help me know what is wrong with my code? The insertHead function is to insert a node at the head. The insertTail function is to insert a node at the tail. The insertAfter is to insert after a specific node, with the insertNode parameter listing which node to place the new one after. Remove is to remove a specific node. Clear is to clear all. T at is to return the value at the specified index, and if out of bounds an out of bounds exception, and the size is to count the number of nodes. Please help. Thank you

#include "LinkedListInterface.h"
#include <iostream>
#include <stdexcept>//to be able to throw exceptions

template<class T>
class LinkedList : public LinkedListInterface<T>
{
private:
struct node
{
T data;
node* next;
node(T data_item)
{
data = data_item;
next = NULL;
}


};
node* head;
node* tail;
node* temp;
node* node_it;
int num_node;


//IF YOU CREATE A NEW NODE, BE SURE TO DELETE IT! BE SURE IT != NULL!!!
public:
LinkedList()
{
head = NULL;
tail = NULL;
temp = NULL;
node_it = NULL;
num_node = 0;
}
~LinkedList(){}
void insertHead(T value)
{
node* n = new node(value);
if (head == NULL)
{
head = n;
tail = n;
}
else
{
n->next = head;
head = n;
}

n = NULL;

}
void insertTail(T value)
{
node* t = new node(value);
if (head == NULL)
{
head = t;
tail = t;
}
else
{
tail->next = t;
tail = t;
}
t = NULL;

}
void insertAfter(T value, T insertionNode)
{
node* n = new node(value);
node_it = head;

while (node_it->data != insertionNode)
{
node_it = node_it->next;


}
if(node_it->data == insertionNode)
{
n->next = node_it->next;
node_it->next = n;
}
n = NULL;
}
void remove(T value)
{
node* pre = head;
node* i_value = head->next->next;
node_it = head;
if(node_it->data != value)
{
while(node_it->next->data != value)
{
i_value = i_value->next;
pre = pre->next;
node_it = node_it->next;
}
}

if(node_it->data == value)
{
pre = pre->next;
node_it ->next= i_value;
delete pre;
}
//iterate through until you find the value
//while finding value, keep track of the one behind it
//node_pre->next = node_value->next;
//delete node_value;
}
void clear()
{

while(head != NULL)
{
temp = head;
head = head->next;
remove(temp->data);
}
}
T at(int index)//if out of bounds throw an exception
{
node_it = head;
int i = 0;
if(index >= size())
{
throw new out_of_range("That is out of range");
}
else
{
while(node_it!= NULL)
{
if(i == index)
{
return node_it->data;
}
node_it = node_it->next;
i++;
}
}

}
int size()
{
node_it = head;
while (node_it != NULL)
{
num_node ++;
node_it = node_it->next;
}

return num_node;
}


};
dhayden (5795)
It seems to be going through an infinite loop when it runs the size() function

What is the value of num_node when you enter size()?

There are several other problems with your code. When posting code, please use code tags so we can refer to it by line. Also it's very helpful to indent the code to reflect the block structure. Here is your 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
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
 
#include "LinkedListInterface.h"
#include <iostream>
#include <stdexcept>            // to be able to throw exceptions

template < class T > class LinkedList:public LinkedListInterface < T > {
  private:
    struct node
    {
        T   data;
        node *next;
            node(T data_item)
        {
            data = data_item;
            next = NULL;
        }


    };
    node *head;
    node *tail;
    node *temp;
    node *node_it;
    int num_node;


//IF YOU CREATE A NEW NODE, BE SURE TO DELETE IT! BE SURE IT != NULL!!!
  public:
    LinkedList() {
        head = NULL;
        tail = NULL;
        temp = NULL;
        node_it = NULL;
        num_node = 0;
    }
    ~LinkedList() {
    }
    void insertHead(T value)
    {
        node *n = new node(value);
        if (head == NULL) {
            head = n;
            tail = n;
        } else {
            n->next = head;
            head = n;
        }

        n = NULL;

    }
    void insertTail(T value)
    {
        node *t = new node(value);
        if (head == NULL) {
            head = t;
            tail = t;
        } else {
            tail->next = t;
            tail = t;
        }
        t = NULL;

    }
    void insertAfter(T value, T insertionNode)
    {
        node *n = new node(value);
        node_it = head;

        while (node_it->data != insertionNode) {
            node_it = node_it->next;


        }
        if (node_it->data == insertionNode) {
            n->next = node_it->next;
            node_it->next = n;
        }
        n = NULL;
    }
    void remove(T value)
    {
        node *pre = head;
        node *i_value = head->next->next;
        node_it = head;
        if (node_it->data != value) {
            while (node_it->next->data != value) {
                i_value = i_value->next;
                pre = pre->next;
                node_it = node_it->next;
            }
        }

        if (node_it->data == value) {
            pre = pre->next;
            node_it->next = i_value;
            delete pre;
        }
//iterate through until you find the value
//while finding value, keep track of the one behind it
//node_pre->next = node_value->next;
//delete node_value;
    }
    void clear()
    {

        while (head != NULL) {
            temp = head;
            head = head->next;
            remove(temp->data);
        }
    }
    T   at(int index)           // if out of bounds throw an exception
    {
        node_it = head;
        int i = 0;
        if (index >= size()) {
            throw new out_of_range("That is out of range");
        } else {
            while (node_it != NULL) {
                if (i == index) {
                    return node_it->data;
                }
                node_it = node_it->next;
                i++;
            }
        }

    }
    int size()
    {
        node_it = head;
        while (node_it != NULL) {
            num_node++;
            node_it = node_it->next;
        }

        return num_node;
    }


};

Line 21-23: These should be local variables in the methods that need them.
Lines 35-36: See the comment at line 26
Line 69: what if head is null?
Line 70: what if node_it becomes NULL?
Lines 74-77: If you're inserting at the beginning or end of the list then you need to adjust head and/or tail.
Lines 108-109: By changing head, you basically remove temp's node from the list, so the call to remove() will probably fail because it won't find the value. You should just delete temp directly here.
Line 109: You never adjust the tail pointer.
Line 112: This code is inefficient because it will traverse the list twice: once to count the nodes and again to find the i'th node. Do all the work here, traversing the list and counting as you go.

Topic archived. No new replies allowed.