C++

Forum

 
Linked Lists - Same Loop Mechanism, One loops indefinitely

mikel792 (8)
This is essentially a two in one question:

1. How can I view dynamically created memory? All elements of the linked list won't and do not show up in the 'watches' debugging window. (Code::blocks is my IDE)

2. When I run this program, printNumberInList works fine. For removeFromList, on the otherhand, it loops for infinity and never reaches the printNumberInList function - even though they both loop on the same principal.

Thanks in advance


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
 
 #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <time.h>

using namespace std;

struct myList
{
    int number = 0;
    myList * next_myList;
};

int incrementer = 0;
void printNumberInList (myList * firstList);

myList * addToList (myList * firstList)
{
    myList* another_entry = new myList;
    another_entry->number = incrementer++;
    another_entry->next_myList = firstList;
    return another_entry;
}

void removeFromList (myList* firstList, int n)
{
    n = n - 1;
    myList* before;
    myList* after;
    while (firstList != NULL)
    {
        if (firstList->number == n)
        {
            before = firstList;
        }
        if (firstList->number == n)
        {
            after = firstList->next_myList;
            before = after;
            delete firstList;
        }
        firstList = firstList->next_myList;
    }
}

void printNumberInList (myList * firstList)
{
    while (firstList != NULL)
    {
        cout << firstList->number << endl;
        firstList = firstList->next_myList;
    }
}

int main()
{
    //goal: create a linked list, have ability to add and remove elements
    myList * firstList = NULL;
    firstList = addToList(firstList);
    firstList = addToList(firstList);
    firstList = addToList(firstList);
    firstList = addToList(firstList);
    removeFromList(firstList, 1);
    printNumberInList(firstList);
}
AbstractionAnon (6954)
Consider lines 41 and 43. If you delete firstList at line 41, firstList no longer points to anything valid. Yet, at line 43, you try to reference firstList->next_myList.
mikel792 (8)
I see some of the problems in the existing code, and I forgot to include that neither of my if statementse are ever triggered. My question is why they act differently, in that case, when they are essentially the same loop?
Last edited on
andywestken (4094)
Also, the conditions on lines 33 and 37 are the same, so you set before to firstList and then change it to after (or firstList->next_myList) pretty much immediately afterwards.

The names make me think you're heading in the right direction.,,

But line 28, where you subtract 1 from the value you want to delete, does not make any sense to me. What happens if you've already deleted nodes and the numbers are no longer contiguous?

How does your function handle deleting the first node in the list?

How can you join the node before the one you're deleting up with the one after it?

Andy

PS Your struct myList is what would usually be called something like myListNode or just myNode.
Last edited on
dhayden (5798)
You don't need to previous_myList member because you don't use it.

Lines 33-38 could go above line 31. There's no reason for that logic to be inside the loop.

removeFromList() removes the n'th element of the list (where n is the second parameter). Is that what you really want, or should it remove the node whose value is n?

mikel792 (8)
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
 
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <time.h>

using namespace std;

struct myList
{
    int number;
    myList * next_myList;
    myList * previous_myList;
};

int incrementer = 1;
void printNumberInList (myList * firstList);

myList * addToList (myList * firstList)
{
    myList* another_entry = new myList;
    another_entry->number = incrementer++;
    another_entry->next_myList = firstList;
    another_entry->previous_myList = another_entry;
    return another_entry;
}

void removeFromList (myList* firstList, int steps)
{
    int tempStep = 1;
    steps -= 1;
    while (firstList != NULL)
    {
        if (steps == 0)
        {
            firstList = firstList->next_myList;
            delete firstList->previous_myList;
            return;
        }
        else if (tempStep == steps)
        {
            firstList->previous_myList = firstList->next_myList;
            firstList = firstList->next_myList;
            delete firstList->previous_myList;
            return;
        }
        tempStep++;
        firstList = firstList->next_myList;
    }
}

void printNumberInList (myList * firstList)
{
    while (firstList != NULL)
    {
        cout << firstList->number << endl;
        firstList = firstList->next_myList;
    }
}

void printNumberInListBackwards (myList * firstList)
{
    while (firstList != NULL)
    {
        cout << firstList->previous_myList->number << endl;
        firstList = firstList->next_myList;
    }
}

int main()
{
    myList * firstList = NULL;
    firstList = addToList(firstList);
    firstList = addToList(firstList);
    firstList = addToList(firstList);
    firstList = addToList(firstList);
    //firstList = removeFromList(firstList, 4);
    removeFromList(firstList, 1);
    printNumberInList(firstList);
    printNumberInListBackwards(firstList);
}


I've made some revisions, and I think I am on my way to solving this. Thanks for your help in advance. Can anyone explain to me why my delete statements in my removeFromList function are causing my list to break? My printNumberInList function loops indefinitely with random numbers of memory, but will print the numbers correctly up until a revision is made... this is the output of the above example with 1 as the steps argument:

4 (I thought I deleted 4?)
-random number
-random number
-random number (for infinity)

Lots of love to he whom lets me continue my progress and learning. Some things I need to understand:

1. Why isn't my memory linking up right? With COUT statements I can see that the pointers are pointing to their next node and previous node correctly... so theoretically why is this not working?

2. In my printNumberInList function, why does it work multiple times? I would expect that the second time through firstList would now = NULL, but for some reason I can declare and use that function multiple times!!!

-Mike
andywestken (4094)
This part repairs your first version removeFromList(), but it cannot handle the removal of the first link.

Andy

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
 
#include <iostream>
//#include <cstdlib> EDIT not used
//#include <cstdio>
//#include <string>
//#include <time.h>

using namespace std;

struct myList
{
    int number = 0;
    myList * next = NULL; // was next_myList; now init like number
};

//int incrementer = 0; EDIT eliminate auto numbering
void printNumberInList (myList * firstList);

myList * addToList (myList * firstList, int number)
{
    myList* another_entry = new myList;
    another_entry->number = number; //incrementer++;
    another_entry->next   = firstList;
    return another_entry;
}

void removeFromList (myList* firstList, int n)
{
    //n = n - 1; EDIT makes no sense
    myList* before = NULL;
    //myList* after; EDIT not needed
    while (firstList != NULL)
    {
        if (firstList->number == n)
        {
            //before = firstList;
            break; // this is the one we want!
        }

        //if (firstList->number == n)
        //{
        //    after = firstList->next;
        //    before = after;
        //    delete firstList;
        //}

        before = firstList; // EDIT remember the last link

        firstList = firstList->next;
    }

    if (firstList != NULL) // we found the link to delete
    {
        if(before == NULL)
        {
            cout << "Problems! before == NULL" << endl;
        }
        else
        {
            before->next = firstList->next;

            delete firstList;
        }
    }
    else
    {
        cout << "No link with value " << n << endl;
    }
}

void printNumberInList (myList * firstList)
{
    while (firstList != NULL)
    {
        cout << firstList->number << endl;
        firstList = firstList->next;
    }
}

int main()
{
    //goal: create a linked list, have ability to add and remove elements
    myList * firstList = NULL;

    cout << "make list of 4 elems" << endl;
    firstList = addToList(firstList, 3);
    firstList = addToList(firstList, 5);
    firstList = addToList(firstList, 7);
    firstList = addToList(firstList, 11);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem 1" << endl;
    removeFromList(firstList, 1);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem 5" << endl;
    removeFromList(firstList, 5);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem 3" << endl;
    removeFromList(firstList, 3);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem 11" << endl;
    removeFromList(firstList, 11);

    printNumberInList(firstList);
    cout << endl;

    return 0;
}
Last edited on
andywestken (4094)
And later version...

Andy

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
 
#include <iostream>
//#include <cstdlib>
//#include <cstdio>
//#include <string>
//#include <time.h>

using namespace std;

struct myList
{
    int number;
    myList * next_myList;
    myList * previous_myList;
};

//int incrementer = 1;
void printNumberInList (myList * firstList);

myList * addToList (myList * firstList, int number)
{
    myList* another_entry = new myList;
    another_entry->number = number; // incrementer++;
    another_entry->next_myList = firstList;
    another_entry->previous_myList = NULL;
    //WAS
    //another_entry->previous_myList = another_entry;
    if(NULL != firstList)
        firstList->previous_myList = another_entry;
    return another_entry;
}

// step 0 = first link
void removeFromList (myList* firstList, int steps)
{
    //int tempStep = 1;
    int tempSteps = steps;
    //steps -= 1;

    while (firstList != NULL)
    {
        //if (steps == 0)
        if (tempSteps == 0)
        {
            break; // the link we want
        //    firstList = firstList->next_myList;
        //    delete firstList->previous_myList;
        //    return;
        //}
        //else if (tempStep == steps)
        //{
        //    firstList->previous_myList = firstList->next_myList;
        //    firstList = firstList->next_myList;
        //    delete firstList->previous_myList;
        //    return;
        }
        //tempStep++;
        --tempSteps;
        firstList = firstList->next_myList;
    }

    if(NULL != firstList)
    {
        if(firstList->previous_myList == NULL)
        {
            cout << "Problems! firstList->previous_myList == NULL" << endl;
        }
        else
        {
            firstList->previous_myList->next_myList = firstList->next_myList;
            firstList->next_myList->previous_myList = firstList->previous_myList;
            delete firstList;
        }
    }
    else
    {
        cout << "No link at step " << steps << endl;
    }
}

void printNumberInList (myList * firstList)
{
    // print forwards (using next)
    while (firstList != NULL)
    {
        cout << firstList->number << endl;
        firstList = firstList->next_myList;
    }
}

void printNumberInListBackwards (myList * firstList)
{
    // find end of list
    while (firstList->next_myList != NULL)
    {
        firstList = firstList->next_myList;
    }

    // print backwards (using prev)
    while (firstList != NULL)
    {
        cout << firstList->number << endl;
        firstList = firstList->previous_myList;
    }

    //WAS
    //while (firstList != NULL)
    //{
    //    cout << firstList->previous_myList->number << endl;
    //    firstList = firstList->next_myList;
    //}
}

int main()
{
    myList * firstList = NULL;

    cout << "make list of 4 elems" << endl;
    firstList = addToList(firstList, 3);
    firstList = addToList(firstList, 5);
    firstList = addToList(firstList, 7);
    firstList = addToList(firstList, 11);

    printNumberInList(firstList);
    cout << endl;

    printNumberInListBackwards(firstList);
    cout << endl;

    cout << "remove elem at step 10" << endl;
    removeFromList(firstList, 10);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem at step 2" << endl;
    removeFromList(firstList, 2);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem at step 1" << endl;
    removeFromList(firstList, 1);

    printNumberInList(firstList);
    cout << endl;

    cout << "remove elem at step 0" << endl;
    removeFromList(firstList, 0);

    printNumberInList(firstList);
    cout << endl;

    return 0;
}
dhayden (5798)
I recommend that you remove the previous_myList member. In other words make this a singly linked list instead of a doubly linked list. Doubly linked lists take extra work to maintain the pointers. You're probably better off getting the singly linked list working right first.
Topic archived. No new replies allowed.