C++

Forum

 
implementing a doubly linked list using templates

unregistered (199)
I tried implementing a doubly linked list using templates but I got this error, any ideas?

node.h
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
 
#include <iostream>

using namespace std;

#ifndef NODE_H
#define NODE_H

template< typename Data >
class Node
{
        public:
                // Constructor
                Node();
                Node( Data );
                // Destructor
                ~Node();

                // Data Members
                Data data;
                Node< Data > *next,
                             *prev;

};

#endif



node.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include "node.h"

// Default Constructor
template< typename Data >
Node< Data >::Node() : prev( NULL ), next( NULL )
{
        return;
}

// Constructor
template< typename Data >
Node< Data >::Node( Data initialData ) : prev( NULL ), next( NULL )
{
        data = initialData;
        return;
}

// Destructor
template< typename Data >
Node< Data >::~Node()
{
        return;
}


The error I got:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
/tmp/ccG1S7Ka.o: In function `main':
driver.cpp:(.text+0x13): undefined reference to `DoublyLinkedList<int>::DoublyLinkedList()'
driver.cpp:(.text+0x47): undefined reference to `DoublyLinkedList<int>::outputList()'
driver.cpp:(.text+0x69): undefined reference to `DoublyLinkedList<int>::insertAtHead(int)'
driver.cpp:(.text+0x8b): undefined reference to `DoublyLinkedList<int>::insertAtTail(int)'
driver.cpp:(.text+0x9c): undefined reference to `DoublyLinkedList<int>::deleteAtHead()'
driver.cpp:(.text+0xad): undefined reference to `DoublyLinkedList<int>::deleteAtTail()'
driver.cpp:(.text+0xbe): undefined reference to `DoublyLinkedList<int>::deleteAllNodes()'
driver.cpp:(.text+0xcc): undefined reference to `DoublyLinkedList<int>::isEmpty() const'
driver.cpp:(.text+0x10a): undefined reference to `DoublyLinkedList<int>::getNoOfNodes() const'
driver.cpp:(.text+0x15d): undefined reference to `DoublyLinkedList<int>::~DoublyLinkedList()'
driver.cpp:(.text+0x178): undefined reference to `DoublyLinkedList<int>::~DoublyLinkedList()'
collect2: ld returned 1 exit status
unregistered (199)
doublylinkedlist.h
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
 
#include <iostream>
#include "node.h"

using namespace std;

#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H

template< typename Data >
class DoublyLinkedList
{
        public:
                // Constructor
                DoublyLinkedList();
                // Destructor
                ~DoublyLinkedList();

                // Get Methods
                int getNoOfNodes() const;

                // Insert Methods
                bool insertAtHead( Data );
                bool insertAtTail( Data );

                // Delete Methods
                bool deleteAtHead();
                bool deleteAtTail();
                void deleteAllNodes();

                // Predicate Methods
                bool isEmpty() const;

                // Print List
                void outputList();

        private:
                 // Set Methods
                 bool setNoOfNodes( int );

                 // Utility Methods
                 Node< Data > * createNode( Data );
                 bool insertAtHead( Node< Data > * );
                 bool insertAtTail( Node< Data > * );
                 bool insertBefore( Node< Data > *, Node< Data > *);
                 bool insertAfter( Node< Data > *, Node< Data > * );
                 bool deleteNode( Node< Data > * );

                 // Data Members
                 int noOfNodes;
                 Node< Data > *head,
                              *tail;

};

#endif


doublylinkedlist.cpp
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
 
#include "doublylinkedlist.h"

// Default Constructor

template< typename Data >
DoublyLinkedList< Data >::DoublyLinkedList() : noOfNodes( 0 ), head( NULL ), tail( NULL )
{
        return;
}

// Destructor

template< typename Data >
DoublyLinkedList< Data >::~DoublyLinkedList()
{
        deleteAllNodes();

        return;
}

// Get Methods

template< typename Data >
int DoublyLinkedList< Data >::getNoOfNodes() const
{
        return noOfNodes;
}

// Set Methods

template< typename Data >
bool DoublyLinkedList< Data >::setNoOfNodes( int no )
{
        bool exitStatus = false;

        if ( no >= 0 )
        {
                noOfNodes = no;
                exitStatus = true;
        }
        return exitStatus;
}

// Insert Methods

template< typename Data >
bool DoublyLinkedList< Data >::insertAtHead( Data data )
{
        return insertAtHead( createNode( data ) );
}

template< typename Data >
bool DoublyLinkedList< Data >::insertAtTail( Data data )
{
        return insertAtTail( createNode( data ) );
}

// Delete Methods

template< typename Data >
bool DoublyLinkedList< Data >::deleteAtHead()
{
        return deleteNode( head );
}

template< typename Data >
bool DoublyLinkedList< Data >::deleteAtTail()
{
        return deleteNode( tail );
}

template< typename Data >
void DoublyLinkedList< Data >::deleteAllNodes()
{
        while ( head )
                deleteAtHead();
        return;
}

// Predicate Methods

template< typename Data >
bool DoublyLinkedList< Data >::isEmpty() const
{
        return ( getNoOfNodes() == 0 );
}


// Utility Methods

template< typename Data >
Node< Data > * DoublyLinkedList< Data >::createNode( Data data )
{
        Node< Data > *pNew = new Node< Data >( data );
        pNew -> prev = NULL;
        pNew -> next = NULL;

        return pNew;
}

template< typename Data >
bool DoublyLinkedList< Data >::insertAtHead( Node< Data > *newNode )
{
        bool exitStatus = false;

        if ( newNode )
        {
                if ( head )
                        exitStatus = insertBefore( head, newNode );
                else
                {
                        head = newNode;
                        tail = newNode;
                        newNode -> pre = NULL;
                        newNode -> next = NULL;
                        exitStatus = setNoOfNodes( getNoOfNodes() + 1 );
                }
        }

        return exitStatus;
}

template< typename Data >
bool DoublyLinkedList< Data >::insertAtTail( Node< Data > *newNode )
{
        bool exitStatus = false;

        if ( newNode )
        {
                if ( tail )
                        exitStatus = insertAfter( tail, newNode );
                else
                        exitStatus = insertAtHead( newNode );

        }

        return exitStatus;
}

template< typename Data >
bool DoublyLinkedList< Data >::insertBefore( Node< Data > *node, Node< Data > *newNode )
{
        bool exitStatus = false;

        if ( node && newNode )
        {
                newNode -> prev = node -> prev;
                newNode -> next = node;

                if ( node -> prev )
                        node -> prev -> next = newNode;
                else
                        head = newNode;

                node -> prev = newNode;

                exitStatus = setNoOfNodes( getNoOfNodes() + 1 );
        }

        return exitStatus;
}


template< typename Data >
bool DoublyLinkedList< Data >::insertAfter( Node< Data > *node, Node< Data > *newNode )
{
        bool exitStatus = false;

        if ( node && newNode )
        {

                newNode -> prev = node;
                newNode -> next = node -> next;

                if ( node -> next )
                        node -> next -> prev = newNode;
                else
                        tail = newNode;

                node -> next = newNode;

                exitStatus = setNoOfNodes( getNoOfNodes() + 1 );
        }

        return exitStatus;
}


template< typename Data >
bool DoublyLinkedList< Data >::deleteNode( Node< Data > *node )
{
        bool exitStatus = false;

        if ( node )
        {
                if ( node -> prev )
                        node -> prev -> next = node -> next;
                else
                        head = node -> next;

                if ( node -> next )
                        node -> next -> prev = node -> prev;
                else
                        tail = node -> prev;

                delete node;

                exitStatus = setNoOfNodes( getNoOfNodes() - 1 );
        }

        return exitStatus;
}


// Test Methods

template< typename Data >
void DoublyLinkedList< Data >::outputList()
{
        Node< Data > *pCur = head;

        while ( pCur )
        {
                cout << pCur -> data << endl;
                pCur = pCur -> next;
        }
        return;
}
jsmith (5804)
You can't put template class implementations in .cpp files easily; you have to move the implementations into the header files where the template classes are declared.
Topic archived. No new replies allowed.