Doubly linked list

I have been asked to have a go at 'modifying' a linked list into a doubly linked list. I have had a go but seem to be struggling somewhat with my remove and insert functions.
Any help and advice is much appreciated.

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
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
 template<typename T>
class node
{
public:
    //the data stored in t the node
    T m_value;

    //pointer to the next node
    node<T>* m_next;
    
    //pointer to the previous node
    node<T>* m_previous;
    
    node(T value, node<T>* previous=nullptr, node<T>* next=nullptr)
            : m_value(value),m_previous(previous), m_next(next) {}
    
};

template<typename T>
class list
{
private:
    node<T>* head;
    node<T>* tail;
    int node_count{};
    
public:
    //constructor
    list(): head(nullptr), tail(nullptr) {}
    
    //destructor
    ~list()
    {
        while(head)
        {
            std::cout << "destructor" << std::endl;
            node<T>* temp = head;
            head = head->m_next;
            delete temp;
        }
    }
    
    int size()
    {
        return node_count;
    }
    
    void push_back(T value) {
        if(!head)
        {
            tail = new node<T>(value);
            head = tail;
            node_count++;
        }
        else{
            node<T>* newtail = new node<T>(value);
            tail->m_next = newtail;
            newtail->m_previous = tail->m_next;
            tail = newtail;
            node_count++;
        }
    }
    
    void push_front(T value){
        if(!tail)
        {
            head = new node<T>(value);
            tail = head;
            node_count++;
        }
        else
        {
            node<T>* newhead =  new node<T>(value);
            newhead->m_next = head;
            newhead->m_previous = head->m_next;
            head = newhead;
            node_count++;
        }
    }
    
    void insert(T value, int idx)
    {
        if(idx == 0)
        {
            push_front(value);
        }
        else
        {
            node<T>* previousnode{head};
            int node_count{};
            while(node_count < (idx - 1))
            {
                previousnode = previousnode->m_next;
                node_count++;
            }
            node<T>* nextnode{previousnode};
            while(node_count < idx)
            {
                nextnode = nextnode->m_next;
                node_count++;
            }
            node<T>* newnode =  new node<T>(value);
            previousnode->m_next = newnode;
            newnode->m_next = nextnode;
            node_count++;
        }
    }
    
    void remove(int idx)
    {
        if(idx == 0)
        {
            node<T>* temp{head};
            head = head->m_next;
            head->m_previous = nullptr;
            node_count--;
            delete temp;
        }
        else
        {
            node<T>* first{head};
            int count{};
            while(count < (idx - 1))
            {
                first = first->m_next;
                count++;
            }
            node<T>* second{first};
            while (count < (idx + 1))
            {
                second = second->m_next;
                count++;
            }
            if(idx == count - 1)//not sure why its always 1 above node_count?
            {
                node<T>* temp = second;
                first->m_next = nullptr;
                first = tail;
                node_count--;
                delete temp;
            }
            else
            {
                node<T>* temp = first->m_next;
                first->m_next = second;
                second->m_previous = first;
                delete temp;
                node_count--;
            }
        }
    }
    
    friend std::ostream& operator<<(std::ostream& out, const list &l)
    {
        const node<T>* temp = l.head;
        while(temp)
        {
            out << temp->m_value << " ";
            temp = temp->m_next;
        }
        
        return out;
        
    }
};


For a start, you need to modify node to have a forward and backward pointer.

Then you need to modify each method to maintain them.
Last edited on
I haven't tested this (since you provided no headers or main) but remove could go something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
    void remove(int idx)
    {
        node<T>* temp{head};
        for (int i = 0; temp && i < idx; ++i)
            temp = temp->next;
        if (temp) {
            if (temp->next) temp->next->prev = temp->prev;
            if (temp->prev) temp->prev->next = temp->next;
            if (temp == head) head = temp->next;
            if (temp == tail) tail = temp->prev;
            delete temp;
        }
    }

In push_back():
1
2
            tail->m_next = newtail;
            newtail->m_previous = tail->m_next;

is the same as
1
2
            tail->m_next = newtail;
            newtail->m_previous = newtail;


You have the same problem in other places.

If you put class Node inside class List, you don't have to make it a template:
1
2
3
4
5
6
7
8
template<typename T>
class list {
    class Node {
        T m_value;
        Node *prev, *next;
   };
   ...
};

Thanks! I have had a rethink and amended. Now it seems to work as I want but when I step through the destructor I get the following, I have tried to find the problem but can't :( below is my code.
doubly linked list(94838,0x1000d8dc0) malloc: *** error for object 0x1004bf880: pointer being freed was not allocated
doubly linked list(94838,0x1000d8dc0) malloc: *** set a breakpoint in malloc_error_break to debug


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

#ifndef list_hpp
#define list_hpp
#include <iostream>
#include <memory>
#include "node.hpp"

template<typename T>
class list
{
private:
    node<T>* head;
    node<T>* tail;
    int node_count{};
    
public:
    //constructor
    list(): head(nullptr), tail(nullptr) {}
    
    //destructor
    ~list()
    {
        while(head)
        {
            std::cout << "destructor" << std::endl;
            node<T>* temp = head;
            head = head->m_next;
            delete temp;
            std::cout << "node count:-> " << node_count << std::endl;
            node_count--;
        }
    }
    
    int size()
    {
        return node_count;
    }
    
    void push_back(T value) {
        if(!head)//check for empty list
        {
            std::cout << "empty 1st creating 1st node" << std::endl;
            tail = new node<T>(value);
            head = tail;
            node_count++;
        }
        else{
            node<T>* newtail = new node<T>(value);
            tail->m_next = newtail;
            newtail->m_previous = tail;
            tail = newtail;
            node_count++;
        }
    }
    
    void push_front(T value){
        if(!tail)//check for empty list
        {
            std::cout << "empty list creatin 1st node" << std::endl;
            head = new node<T>(value);
            tail = head;
            node_count++;
        }
        else
        {
            node<T>* newhead =  new node<T>(value);
            newhead->m_next = head;
            head->m_previous = newhead;
            head = newhead;
            node_count++;
        }
    }
    
    void insert(T value, int idx)
    {
        if(idx == 0)
        {
            push_front(value);
        }
        else if(idx == node_count)
        {
            push_back(value);
        }
        else
        {
            node<T>* previousnode{head};
            int node_count{};
            while(node_count < (idx - 1))
            {
                previousnode = previousnode->m_next;
                node_count++;
            }
            node<T>* nextnode{previousnode};
            while(node_count < idx)
            {
                nextnode = nextnode->m_next;
                node_count++;
            }
            node<T>* newnode =  new node<T>(value);
            newnode->m_previous = previousnode;
            newnode->m_next = nextnode;
            //previousnode->m_next = newnode;
            //nextnode->m_previous = newnode;
            node_count++;
        }
    }
    
    void remove(int idx)
    {
        if(idx == 0)
        {
            node<T>* temp{head};
            head = head->m_next;
            head->m_previous = nullptr;
            node_count--;
            delete temp;
        }
        else if(idx == node_count)
        {
            node<T>* temp{tail};
            tail = tail->m_previous;
            tail->m_next = nullptr;
            delete temp;
            node_count--;
        }
        else if(idx == (node_count - 1))
        {
            node<T>* previousnode{head};
            int count{};
            while(count < (idx - 2))
            {
                previousnode = previousnode->m_next;
                count++;
            }
            node<T>* temp{previousnode};
            while(count < idx)
            {
                temp = temp->m_next;
                count++;
            }
            previousnode->m_next = tail;
            tail->m_previous = previousnode;
            delete temp;
            node_count--;
        }
        else
        {
            node<T>* previousnode{head};
            int count{};
            while(count < (idx - 1))
            {
                previousnode = previousnode->m_next;
                count++;
            }
            node<T>* temp{previousnode};
            while(count < idx)
            {
                temp = temp->m_next;
                count++;
            }
            node<T>* nextnode{temp};
            while(count < idx + 1)
            {
                nextnode = nextnode->m_next;
                count++;
            }
            previousnode->m_next = nextnode;
            nextnode->m_previous = previousnode;
            delete temp;
            node_count--;
        }
        
    }
    
    friend std::ostream& operator<<(std::ostream& out, const list &l)
    {
        const node<T>* temp = l.head;
        while(temp)
        {
            out << temp->m_value << " ";
            temp = temp->m_next;
        }
        
        return out;
        
    }
};



#endif /* list_hpp */


attached main and node class

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
#ifndef node_hpp
#define node_hpp
#include "list.hpp"


template<typename T>
class node
{
public:
    //the data stored in t the node
    T m_value;

    //pointer to the next node
    node<T>* m_next;
    
    //pointer to the previous node
    node<T>* m_previous;
    
    node(T value, node<T>* previous=nullptr, node<T>* next=nullptr)
    : m_value(value),m_previous(previous), m_next(next) { std::cout << "node cons" << std::endl;}
    
};


#include <iostream>
#include <string>
#include "list.hpp"

int main(int argc, const char * argv[]) {
    
    list<int> numbers;
    std::cout << numbers.size() << std::endl;
    numbers.push_back(5);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_front(10);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_front(20);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.insert(100, numbers.size());
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_back(200);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.remove(numbers.size() - 2);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_back(15);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_back(25);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.remove(numbers.size());
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    std::cout << "remove entry at-> " << numbers.size() - 1 <<  std::endl;
    numbers.remove(numbers.size() - 1);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    
    
    numbers.push_front(30);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_front(35);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_front(40);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.push_front(45);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.insert(200, numbers.size());
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    std::cout << "remove entry at-> " << numbers.size() - 1 <<  std::endl;
    numbers.remove(numbers.size() - 1);
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.remove(numbers.size());
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.insert(300, numbers.size());
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    numbers.insert(400, numbers.size());
    std::cout << numbers << std::endl;
    std::cout << numbers.size() << std::endl;
    
    
    
    /*list<std::string> words;
    
    words.push_front("hello");
    words.push_back("world");
    words.push_back("!");
    words.insert("new", 1);
    std::cout << words << std::endl;
    std::cout << words.size() << std::endl;*/
    
    return 0;
}


In the list code:
lines 100-101: you need to adjust previousnode->next and nextnode->prev
Lines 112-116: You assume the list isn't empty. You also assume there isn't exactly one item, in which case you need to update tail.
Lines 120-124: Same as above

I'm not sure if you're handling all the cases in remove(). I'd structure this as:
- set previousnode to the node before the insertion point. Nullptr means insert at head.
- if (previousnode == nullptr) push_front()
else if (previousnode == tail) push_back()
else you know that there's a node after previousnode. Insert the new node between them.

Thanks I will have a look tomorrow!! If you look at code snippet below, I have commented out a delete. Now it runs with out an error 😂
Haven't got clue why though...


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

else if(idx == (node_count - 1))
        {
            node<T>* previousnode{head};
            int count{};
            while(count < (idx - 2))
            {
                previousnode = previousnode->m_next;
                count++;
            }
            node<T>* temp{head};
            count = 0;
            while(count < idx)
            {
                temp = temp->m_next;
                count++;
            }
            previousnode->m_next = tail;
            tail->m_previous = previousnode;
            //delete temp;
            node_count--;
        }

Wait a sec. If idx==0, you remove the first node. If idx == node_count then idx is out of bounds. If idx == node_count-1 then you're removing the tail.
dhayden I have looked at what you said and you are onto something!!
This is going to sound really strange...
When I initialise int node_count{} it is zero. When my fist node is created the node_count is incremented to 1,code runs and reproduces the error.
Now if I init node_count{-1} and increment to zero when first node is created everything is good 🧐, code runs without error.
So where am I going wrong??
its my remove function that is the issue :( it needs rewriting from top to bottom.
What I have tried isn't any good, where to start through?
I'd start with my advice from yesterday :)
I'm not sure if you're handling all the cases in remove(). I'd structure this as:
- set previousnode to the node before the insertion point. Nullptr means insert at head.
- if (previousnode == nullptr) push_front()
else if (previousnode == tail) push_back()
else you know that there's a node after previousnode. Insert the new node between them.
Thanks for all the help. I finally realised that I disappeared down a rabbit hole and was mistaking numbers.size() for the 'indexes' of the nodes. Thanks to dhayden for pointing this out!

I have re-written remove() with the above knowledge in mind.
I have made similar changes to insert().

Thanks everyone for the help!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void remove(int idx)
    {
        if(node_count == 0) return;
        else
        {
            node<T>* node_to_remove{head};
            for(int i{}; i < idx; i++, node_to_remove = node_to_remove->m_next);
            if(node_to_remove->m_previous) node_to_remove->m_previous->m_next = node_to_remove->m_next;
            if(node_to_remove->m_next) node_to_remove->m_next->m_previous = node_to_remove->m_previous;
            if(head == node_to_remove) head = node_to_remove->m_next;
            if(tail == node_to_remove) tail = node_to_remove->m_previous;
            node_count--;
            delete node_to_remove;
        }
    }

Topic archived. No new replies allowed.