C++

Forum

 
Dealing with nodes

Semirxbih (18)
Currently working on a project and I would appreciate all the help that I can get.

Here is the first part of the assignment:

Instructions:
1
2
3
4
5
6
7
8
9
 
In this file, you declare a class named StringList.
– StringList is a modified version of NumberList class (Chapter 17), that is designed to store C++ strings
in a linked list.
– Therefore, each node must store a string, not a number.
– The node structure must be declared within class, and a private attribute head points to the starting node.
– The class provides a default constructor that creates an empty linked list, and a destructor that releases
all the nodes.
– The class also provides public member functions for inserting and deleting a node (see below for details).
– It also provides a public member function for displaying the list.


Here is what I have so far, this is the StringList.h file.. Everything seems to be coming back error free.
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
 
#ifndef STRINGLIST_H
#define STRINGLIST_H

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>

using namespace std;

class StringList
{
private:
  //Declare a structure for the list
  struct listNode
  {
    string name;
    string a;
    struct listNode *next;
  };

  //Points to the starting Node
  listNode *head;

public:
  //Constructor
  StringList()
  {
    head = NULL;
  }

  //Destructor
  ~StringList();

  //List Operations
  void insertNode(string a);
  void deleteNode(string a);
  void displayList() const;
  void deleteFront();
  void deleteBack();
  void clear();
};

#endif




Here is the second part of the assignment, this I'm extremely confused about.
1
2
3
4
5
6
7
8
9
10
 
In this file, you provide definitions for the default constructor and the destructor for StringList.
– Make sure the destructor visits every node in the list and deletes every one of them from the heap.
– Define insertFront function to insert a new node into the front of the list. Therefore, the new node will
be the new first node in the list. This function takes a string as a parameter.
– Define insertBack function to insert a new node into the back of the list. Therefore, the new node will be
the new last node in the list. This function takes a string as a parameter.
– Define deleteFront function to delete the first node from the list. This function takes no parameter.
– Define deleteBack function to delete the last node from the list. This function takes no parameter.
– Define display function that displays the current contents (strings) of the list (display strings in a single
line, separated by a space). This function takes no parameter.



Here is what I have so far, I would appreciate if someone can guide in the right direction and teaching me how to define those four functions. Here is my StringList.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
 
#include <iostream>
#include "StringList.h"

using namespace std;

//Constructor definition
StringList::StringList()
{
  head = nullptr;
}

//Destructor definition
StringList::~StringList()
{
  delete head;
  clear();
}

//deleteFront
StringList::deleteFront()
{
  if(head != NULL)
  {
    listNode *tmp = head -> next;
    delete head;
    head = tmp;
  }
}

StringList::displayList()
{
  listNode *nodePtr;

  if(!head)
  {
    cout << "List is empty";
    return;
  }
  nodePtr = head;
  cout << "Here is the list: \n\t";

  while (nodePtr)
  {
    cout << nodePtr -> a << " -> ";
  }
  nodePtr = nodePtr -> next;
}
Last edited on
AbstractionAnon (6954)
stringlist.h
Lines 17-18: Why do you have two strings? Your deisplayList() function references only a.

stringlist.cpp
Lines 15-16: You haven't implemented clear(), so I can only guess that the intent of clear() is to walk the list and delete each node. If that's the case, you want to do that BEFORE you delete the head node. i.e. these two lines are in the wrong order.

Lines 44-46: Line 46 is outside the loop. Therefore, nodePtr will never change inside the loop and you will have an infinite loop printing the first node. Move line 46 inside the loop.

this I'm extremely confused about

Please be specific regarding what you're confused about. Your implementation of deleteFront is spot on. Make an attempt on the other three functions. Hint: For insertBack() and deleteBack(), you will have to walk the list to find the last node.

Line 44: The instructions say "separated by a space", not " -> ".

closed account (48T7M4Gy)
https://www3.ntu.edu.sg/home/ehchua/programming/cpp/DataStructureAlgorithm.html#zz-3.1

This reference has a useful single linked list
Semirxbih (18)
So this is what I have so far in StringList.h

1
2
3
4
5
6
7
8
9
 
– In this file, you declare a class named StringList.
– StringList is a modified version of NumberList class (Chapter 17), that is designed to store C++ strings
in a linked list.
– Therefore, each node must store a string, not a number.
– The node structure must be declared within the class, and a private attribute head points to the starting node.
– The class provides a default constructor that creates an empty linked list, and a destructor that releases
all the nodes.
– The class also provides public member functions for inserting and deleting a node (see below for details).
– It also provides a public member function for displaying the list.


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
 
#ifndef STRINGLIST_H
#define STRINGLIST_H

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>

using namespace std;

class StringList
{
private:
  //Declare a structure for the list
  struct listNode
  {
    string a;
    listNode *next;
  };

  //Points to the Node
  listNode *head;
  listNode *back;

public:
  //Constructor
  StringList();

  //Destructor
  ~StringList();

  //List Operations
  void displayList();
  void deleteFront();
  void deleteBack();
  void insertFront(string a);
  void insertBack(string a);
};

#endif


NO ERRORS
_________________________________________________


This is my second part:

1
2
3
4
5
6
7
8
9
10
 
– In this file, you provide definitions for the default constructor and the destructor for StringList.
– Make sure the destructor visits every node in the list and deletes every one of them from the heap.
– Define insertFront function to insert a new node into the front of the list. Therefore, the new node will
be the new first node in the list. This function takes a string as a parameter.
– Define insertBack function to insert a new node into the back of the list. Therefore, the new node will be
the new last node in the list. This function takes a string as a parameter.
– Define deleteFront function to delete the first node from the list. This function takes no parameter.
– Define deleteBack function to delete the last node from the list. This function takes no parameter.
– Define display function that displays the current contents (strings) of the list (display strings in a single
line, separated by a space). This function takes no parameter.


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

using namespace std;

//Constructor definition
StringList::StringList()
{
  head = nullptr;
}

//Destructor definition
StringList::~StringList()
{
  delete head;
  delete back;
}

//Inserting Front
void StringList::insertFront(string a)
{
  listNode *temp = new listNode;
  temp -> a;
  temp -> next = head;
  head = temp;
}

//Inserting Back
void StringList::insertBack(string a)
{
  listNode *temp = new listNode;
  temp -> a;
  temp -> next = back;
  head = temp;
}

//deleteFront
void StringList::deleteFront()
{
  if(head != NULL)
  {
    listNode *tmp = head -> next;
    delete head;
    head = tmp;
  }
}

void StringList::deleteBack()
{
  if(head != NULL)
  {
    listNode *tmp = back -> next;
    delete back;
    back = tmp;
  }
}

void StringList::displayList()
{
  listNode *nodePtr;

  if(!head)
  {
    cout << "List is empty" << endl;
    return;
  }
  for (auto nodePtr = head; nodePtr; nodePtr = nodePtr -> next)
    cout << nodePtr -> a << " " << endl;
}


NO ERRORS:

_________________________________________________________________

This is my third and final page:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
– In this file, you define main function that tests StringList class.
– You must first create a StringList object.
1
– Then start inserting new nodes, one at a time. Alternate between inserting into the front and into the
back. Make sure to add at least 6 nodes.
– Then start deleting nodes, one at a time. Alternate between deleting from the front and from the back.
– Make sure all the nodes are deleted before terminating the program.
– After each insertion or deletion, call display member function to display the updated list.
– Make sure all the member functions are tested and shown to work properly, without missing any of them.
– Note that the display function must be called pretty much every time a node is inserted or deleted.
Otherwise the respective functionality will not be properly demonstrated and could lead to loss of points.
– Also note that each member function should properly work regardless of the current list configuration
(empty list, one-node list, or multiple-node list).


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
 
#include <iostream>
#include <string>
#include <iomanip>
#include "StringList.h"
#include "StringList.cpp"

using namespace std;

int main() {

//Then start inserting new nodes, one at a time. Alternate between inserting into the front and into the
//back. Make sure to add at least 6 nodes.
  StringList::StringList myList()
  {
    for(i = 0, i < 6, i++)
    {
      a++;
//After each insertion or deletion, call display member function to display the updated list.
      myList.displayList();
    }
//Then start deleting nodes, one at a time. Alternate between deleting from the front and from the back.
    for(i = 0, i < 6, i++)
    {
      a--;
    }
  }

  return 0;
}


1
2
3
 
This one I had the most trouble with:
1. How to insert up to 6 nodes & then deleting them.
2. Making sure that their all being displayed using displayList.


Please help guide me in the right direction, and tell me where I'm making the biggest mistakes. I'm a total newbie when it comes to lists.
Last edited on
Semirxbih (18)
The First and the Second page are error free! Need help with the final page still.
JLBorges (13770)
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
 
#include <string>
#include <cassert>
#include <iostream>
#include <iomanip>

struct str_list
{
    // default constructor that creates an empty linked list
    // the explicitly defaulted default constructor would creates an empty list
    // note: head and tail have default member initialiser that initialise them to null
    str_list() = default ;

    // destructor that releases all the nodes.
    ~str_list()
    {
        assert( is_valid() ) ; // sanity check: the list is in a valid state
        while( !empty() ) pop_back() ;
    };

    // disable copy and move for now (you may ignore this nicety for now)
    str_list( const str_list& ) = delete ;
    str_list( str_list&& ) = delete ;
    str_list& operator= ( str_list ) = delete ;

    bool empty() const
    {
        assert( is_valid() ) ; // sanity check: the list is in a valid state
        return head == nullptr ;
    }

    // member functions for inserting and erasing at the front and back
    void push_front( std::string str )
    {
        assert( is_valid() ) ; // sanity check: the list is originally in a valid state

        head = new node { str, head } ;
        if( tail == nullptr ) tail = head ; // edgecase: insert into empty list

        assert( is_valid() ) ; // sanity check: the modified list is in a valid state
    }

    void push_back( std::string str )
    {
        assert( is_valid() ) ; // sanity check: the list is originally in a valid state

        if( empty() ) push_front(str) ; // insert into empty list
        else
        {
            tail->next = new node {str} ; // add a node after the current tail
            tail = tail->next ; // and make it the new tail
        }

        assert( is_valid() ) ; // sanity check: the modified list is in a valid state
    }

    void pop_front()
    {
        assert( is_valid() ) ; // sanity check: the list is in a valid state

        if( !empty() )
        {
            auto temp = head ;
            head = head->next ;
            delete temp ;
            if( head == nullptr ) tail = nullptr ; // edge case: erased the only element
        }

        assert( is_valid() ) ; // sanity check: the modified list is in a valid state
    }

    void pop_back()
    {
        assert( is_valid() ) ; // sanity check: the list is in a valid state

        if( head == tail ) pop_front() ; // erase the only element or empty list

        else
        {
            // get to the node just before the tail
            node* just_before_tail = head ;
            while( just_before_tail->next != tail )
                just_before_tail = just_before_tail->next ;

            delete tail ; // delete the old tail
            tail = just_before_tail ; // and make this the new tail
            tail->next = nullptr ;
        }

        assert( is_valid() ) ; // sanity check: the modified list is in a valid state
    }

    // display function that displays the current contents
    std::ostream& display( std::ostream& stm = std::cout ) const
    {
        assert( is_valid() ) ; // sanity check: the list is in a valid state

        stm << "[ " ;
        for( node* n = head ; n != nullptr ; n = n->next )
            std::cout << std::quoted(n->value) << ' ' ;
        return stm << ']' ;
    }

    private:

        struct node
        {
            explicit node( std::string v, node* n = nullptr ) : value(v), next(n) {}
            std::string value ;
            node* next = nullptr ; // default member initialiser
        };

        node* head = nullptr ; // default member initialiser
        node* tail = nullptr ; // default member initialiser

        // class invariant: (if our code is correct, this must always be true)
        // this should be the first function that we write when we implement a class
        bool is_valid() const
        {
            // sanity check: either both head and tail are non-null
            //               or both head and tail are null
            if( ( head && !tail ) || ( !head && tail ) ) return false ;

            // there must be nothing after the tail; it must be the last node
            if( tail && tail->next != nullptr ) return false ;

            // if we start from head, we must be able to reach the tail
            for( node* n = head ; n != tail ; n = n->next )
                if( n == nullptr ) return false ; // we won't be able to reach the tail

            return true ; // things seem to be fine
        }

   // provide an overloaded stream insertion operator (you may ignore this nicety for now)
   friend std::ostream& operator<< ( std::ostream& stm, const str_list& lst )
   { return lst.display(stm) ; }
};

int main()
{
    str_list lst ; // create a StringList object.
    lst.display() << '\n' ;

    const std::string test_strings[] = { "1.One,", "2.two,", "3.Buckle", "4.my", "5.shoe;",
                                         "6.Three,", "7.four", "8.Knock", "9.at", "10.the", "11.door." } ;

    // start inserting new nodes, one at a time.
    bool at_front = true ;
    for( std::string str : test_strings )
    {
        // Alternate between inserting at the front and back.
        if(at_front) lst.push_front(str) ; else lst.push_back(str) ;
        at_front = !at_front ; // toggle

        // call display member function to display the updated list.
        lst.display() << '\n' ;
    }

    std::cout << '\n' ;

    // start erasing nodes, one at a time.
    at_front = true ;
    for( std::string str : test_strings )
    {
        // Alternate between erasing at the front and back.
        if(at_front) lst.pop_front() ; else lst.pop_back() ;
        at_front = !at_front ; // toggle

        // call display member function to display the updated list.
        // for variety, use the overloaded operator
        std::cout << lst << '\n' ;
    }
}

http://rextester.com/LPIH38171
closed account (48T7M4Gy)
This is a partial start to getting it to work. You can still keep separate files, this way just makes things easier.

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
 
#include <iostream>
#include <string>

using namespace std;

class StringList
{
private:
    //Declare a structure for the list
    struct listNode
    {
        string str; // <--
        listNode *next;
    };
    
    //Points to the Node
    listNode *head;
    listNode *back;
    
public:
    
    //Constructor definition
    StringList()
    {
        head = nullptr;
        back = nullptr; // <--
    }
    
    //Destructor definition
    ~StringList()
    {
        delete head;
        delete back;
    }
    
    //Inserting Front
    void insertFront(string aStr)
    {
        listNode *temp = new listNode;
        temp -> next = head;
        temp -> str = aStr; // <--
        head = temp;
    }
    
    //Inserting Back
    void insertBack(string aStr)
    {
        listNode *temp = new listNode;
        temp -> str = aStr; // <--
        temp -> next = back;
        head = temp;
    }
    
    //deleteFront
    void deleteFront()
    {
        if(head != NULL)
        {
            listNode *tmp = head -> next;
            delete head;
            head = tmp;
        }
    }
    
    void deleteBack()
    {
        if(head != NULL)
        {
            listNode *tmp = back -> next;
            delete back;
            back = tmp;
        }
    }
    
    void displayList()
    {
        listNode *nodePtr;
        
        if(!head)
        {
            cout << "List is empty" << endl;
            return;
        }
        for (auto nodePtr = head; nodePtr; nodePtr = nodePtr -> next)
            cout << nodePtr -> str << " " << endl;
    }
    
};

int main()
{
    string test = "Testing";
    StringList myList; // <--
    
    for(int i = 0; i < 6; i++) // <--
    {
        myList.insertBack(test + '-' + to_string(i)); // <--
        myList.displayList();
    }
    
    return 0;
}
Semirxbih (18)
Wow thank you so much guys! kemort your version helped even more! I'm almost there.
closed account (48T7M4Gy)
@Semirxbih
My pleasure. Keep plugging away at it though because there are still a few quirky bits/challenges.
Topic archived. No new replies allowed.