C++

Forum

 
 
Pushing to the front of a singly linked list

PiggiesGoSqueal (167)
Okay, for those of you who saw my previous question, this is different and now I'm following my professor's notes:
https://github.com/rambasnet/cs2notebooks/blob/master/LinkedLists.ipynb

Please Note:
1. This is a homework assignment, however, it was due ~3 weeks ago so I'm only doing it for the learning aspect.
2. The homework assignment has me start with some of my professor's code (also found in same link above) then I am supposed to add to it to get the desired effect.

I'm trying to add a new node to the beginning of a singly linked list. And it appears to work, but also adds a 0 too (after the newly added node).

Console Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
LinkedList has 0 nodes.
[ ]

Now pushing 10, 20, 30...

New Linked List Contents:
[ 10 20 30 ]

Pushing '3000' to front of linked list...

New Linked List Contents:
[ 0 10 20 30 ]
Note: My professor's code ignore's the first element
when printing out whole thing. If I change that, it
shows: [3000 0 10 20 30]

Get First Element:
3000

LinkedList has 4 nodes.



Main.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
 
#include <iostream>
#include <sstream> // stringstream
#include <cassert>
#include "SinglyLinkedList_v2.h"

int main() {
    // test IntLinkedList with some data
    IntLinkedList ilist;

    std::cout << "LinkedList has " << ilist.size() << " nodes.\n";
    std::cout << ilist.toString() << '\n';

    std::cout << "\nNow pushing 10, 20, 30...\n";
    ilist.push_back(10); // remember: We made the push_back() ourselves. It's not a default function C++ offers for this
    ilist.push_back(20);
    ilist.push_back(30);
    std::cout << "\nNew Linked List Contents:\n";
    std::cout << ilist.toString() << '\n';

    std::cout << "\nPushing '3000' to front of linked list...\n";
    ilist.push_front(3000); // does work but for some reason there's a zero added that it's showing instead.

    std::cout << "\nNew Linked List Contents:\n";
    std::cout << ilist.toString() << '\n';
    std::cout << "Note: My professor's code ignore's the first element\n"
              << "when printing out whole thing. If I change that, it\n"
              << "shows: [3000 0 10 20 30]\n";
    
    std::cout << "\nGet First Element:\n";
    std::cout << ilist.getFirstElem() << '\n';

    std::cout << "\nLinkedList has " << ilist.size() << " nodes.\n";
    /*
    std::cout << "Removing 20 from linked list...\n";
    ilist.remove(20);

    std::cout << "\nNew Linked List Contents:\n";
    std::cout << ilist.toString() << '\n';

    std::cout << "\nNew Linked List Contents:\n";
    std::cout << ilist.toString() << '\n';
    */
    return 0;
}



SinglyLinkedList_v2.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
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
 
// SinglyLinkedList_v2.h
// v1 was based on an online guide with a lot of memory leaks.
// v2 is based on professor's github notes and I started over completely.

// Guard
#ifndef SINGLYLINKEDLIST_V2
#define SINGLYLINKEDLIST_V2

#include <iostream>
#include <sstream>
#include <cassert>

struct Int_Node {
    int data; // int data
    Int_Node *next; // address of the next node
};

class IntLinkedList {
    private:
        Int_Node *head; // pointer to the header node
        Int_Node *tail; // pointer to the trailer node
        size_t nodeCount; // keep track of number of nodes
        
    public:
        IntLinkedList() {
            this->nodeCount = 0;
            Int_Node *temp = new Int_Node;
            temp->data = 0;
            temp->next = nullptr;
            this->head = temp;
            temp = new Int_Node;
            temp->data = 0;
            temp->next = nullptr;
            this->tail = temp;
            
            // link head with tail
            this->head->next = this->tail;
        }
    
        bool empty() const {
            return this->nodeCount == 0;
        }
    
        // adds an element to the end (insert end)
        void push_back(int data) {
            Int_Node *node = new Int_Node;
            node->data = 0;
            node->next = NULL;
            
            this->tail->data = data; // update trailer node's data
            this->tail->next = node; // link new node at the end
            this->tail = node; // make new node the trailer node
            
            this->nodeCount++;
        }
    
        // inserts an element to the beginning
        void push_front(int data) {
            // FIXME
            Int_Node *temp = new Int_Node; // creates a new node for info data that will be inserted.
            temp->data = data; // Stores data value in temp node.
            temp->next = this->head; // Stores the address of the head node into 'next' for temp node.
            //std::cout << "Debug: temp->data = " << temp->data << '\n';
            //std::cout << "Debug: temp->next = " << temp->next << '\n';
            //std::cout << "Debug: head = " << head << '\n';
            this->head = temp;

            this->nodeCount++;
        }
        
        // return the size of the list
        size_t size() {
            return this->nodeCount;
        }
    
        // access the first element
        // FIXME - implement method to access the data in first node
        // #FIXED#
        int getFirstElem() {
            return head->data;
        }

        // return string representation of linked list
        std::string toString() {
            std::stringstream ss;
            ss << "[";
            Int_Node *curr = head->next; // ignore head and stop before tail
            while (curr != tail) {
                ss << " " << curr->data;
                curr = curr->next;
            }
            ss << " ]";
            return ss.str();
        }
        
    
        // remove node with given key
        void remove(int key) {
            assert(!empty());
            Int_Node *curr = head; //start from header noded
            bool found = false;
            while (curr->next != tail) {
                if (curr->next->data == key) {
                    found = true;
                    break;
                }
                curr = curr->next;
            }
            if (found) {
                // node found delete it
                Int_Node *node = curr->next; //copy curr->next to properly delete it
                // point around unneeded node
                curr->next = curr->next->next;
                delete curr->next;
                this->nodeCount--;
            }
        }
        
    
        // insert a node with a given data after the node with the after_key value
        // if the element with after_key not found, insert data at the end
        void insert_after(int after_key, int data) {
            // FIXME
        }
};

#endif



Help would be greatly appreciated, thanks!
Last edited on
dhayden (5795)
In your prof's implementation, the list always has at least two nodes: a dummy head node and a dummy tail node. This means that the first node with real data is head->next (as long as head->next != tail, in which case the list is empty).

So here are the two fixes needed:
1
2
3
 
        int getFirstElem() {
            return head->next->data;
        }


and
1
2
3
4
5
6
7
8
9
10
 
        // inserts an element to the beginning
        void push_front(int data) {
            // FIXME
            Int_Node *temp = new Int_Node; // creates a new node for info data \
that will be inserted.
            temp->data = data; // Stores data value in temp node.
            temp->next = head->next; // now link it after head
            head->next = temp;
            this->nodeCount++;
        }

PiggiesGoSqueal (167)
dhayden wrote:
In your prof's implementation, the list always has at least two nodes: a dummy head node and a dummy tail node. This means that the first node with real data is head->next (as long as head->next != tail, in which case the list is empty).

So here are the two fixes needed:
1
2
3
 
        int getFirstElem() {
            return head->next->data;
        }

and
1
2
3
4
5
6
7
8
9
10
 
        // inserts an element to the beginning
        void push_front(int data) {
            // FIXME
            Int_Node *temp = new Int_Node; // creates a new node for info data \
that will be inserted.
            temp->data = data; // Stores data value in temp node.
            temp->next = head->next; // now link it after head
            head->next = temp;
            this->nodeCount++;
        }

Thank you for your reply!

Your explanation makes sense. But for the first block of code I tried changing the line to what you suggested and the issue still persists. It has the same output as when the line was return head->data;.

New Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
LinkedList has 0 nodes.
[ ]

Now pushing 10, 20, 30...

New Linked List Contents:
[ 10 20 30 ]

Pushing '3000' to front of linked list...

New Linked List Contents:
[ 3000 10 20 30 ]
Note: My professor's code ignore's the first element
when printing out whole thing. If I change that, it
shows: [3000 0 10 20 30]

Get First Element:
3000

LinkedList has 4 nodes.



New SinglyLinkedList_v2.h 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
 
// SinglyLinkedList_v2.h
// v1 was based on an online guide with a lot of memory leaks.
// v2 is based on professor's github notes and I started over completely.

// Guard
#ifndef SINGLYLINKEDLIST_V2
#define SINGLYLINKEDLIST_V2

#include <iostream>
#include <sstream>
#include <cassert>

struct Int_Node {
    int data; // int data
    Int_Node *next; // address of the next node
};

class IntLinkedList {
    private:
        Int_Node *head; // pointer to the header node
        Int_Node *tail; // pointer to the trailer node
        size_t nodeCount; // keep track of number of nodes
        
    public:
        IntLinkedList() {
            this->nodeCount = 0;
            Int_Node *temp = new Int_Node;
            temp->data = 0;
            temp->next = nullptr;
            this->head = temp;
            temp = new Int_Node;
            temp->data = 0;
            temp->next = nullptr;
            this->tail = temp;
            
            // link head with tail
            this->head->next = this->tail;
        }
    
        bool empty() const {
            return this->nodeCount == 0;
        }
    
        // adds an element to the end (insert end)
        void push_back(int data) {
            Int_Node *node = new Int_Node;
            node->data = 0;
            node->next = NULL;
            
            this->tail->data = data; // update trailer node's data
            this->tail->next = node; // link new node at the end
            this->tail = node; // make new node the trailer node
            
            this->nodeCount++;
        }
    
        // inserts an element to the beginning
        void push_front(int data) {
            // FIXME
            Int_Node *temp = new Int_Node; // creates a new node for info data that will be inserted.
            temp->data = data; // Stores data value in temp node.
            temp->next = head->next; // links temp to point to the (soon to be previous) head
            head->next = temp; // sets head->next (where the first actual info is stored in linked list) to temp.

            this->nodeCount++;
        }
        
        // return the size of the list
        size_t size() {
            return this->nodeCount;
        }
    
        // access the first element
        // FIXME - implement method to access the data in first node
        // #FIXED#
        int getFirstElem() {
            return head->next->data;
        }

        // return string representation of linked list
        std::string toString() {
            std::stringstream ss;
            ss << "[";
            Int_Node *curr = head->next; // ignore head and stop before tail
            while (curr != tail) {
                ss << " " << curr->data;
                curr = curr->next;
            }
            ss << " ]";
            return ss.str();
        }
        
    
        // remove node with given key
        void remove(int key) {
            assert(!empty());
            Int_Node *curr = head; //start from header noded
            bool found = false;
            while (curr->next != tail) {
                if (curr->next->data == key) {
                    found = true;
                    break;
                }
                curr = curr->next;
            }
            if (found) {
                // node found delete it
                Int_Node *node = curr->next; //copy curr->next to properly delete it
                // point around unneeded node
                curr->next = curr->next->next;
                delete curr->next;
                this->nodeCount--;
            }
        }
        
    
        // insert a node with a given data after the node with the after_key value
        // if the element with after_key not found, insert data at the end
        void insert_after(int after_key, int data) {
            // FIXME
        }
};

#endif
Last edited on
mbozzi (3911)
Eliminate special cases. Place the head node before the first element of the list. If you do that, each single-element insertion can then be specified in terms of insert_after.

N.B.: The insert_after function should take an unambiguous reference to a node - no searching required. Something like:

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

namespace my {
  struct node {
    node() = default;
    explicit node(int value, node *next = nullptr) : data_(value), next_(next) {}
  
    int data_;
    node *next_ = nullptr;
  };
  
  struct forward_list {
    forward_list() = default;
    ~forward_list() { while (!empty()) erase_after(&head_); }
    
    forward_list(forward_list const &)            = delete;
    forward_list(forward_list &&)                 = delete;
    forward_list operator=(forward_list const &)  = delete;
    forward_list operator=(forward_list const &&) = delete;

    bool empty() const { return head_.next_; }
    void push_front(int value) { insert_after(&head_, value); }
  
    std::string to_string() const {
      std::string result;
      for (node const *tmp = &head_; (tmp = tmp->next_);)
        result += std::to_string(tmp->data_) + ' ';
      return result;
    }
  
  private:
    node *erase_after(node *pos) {
      node *current = pos->next_;
      pos->next_ = current->next_;
      delete current;
      return pos->next_;
    }
  
    node *insert_after(node *pos, int value) {
      node *thing = new node(value);
      thing->next_ = pos->next_;
      return pos->next_ = thing;
    }
  
    node head_;
  };
} // namespace my

int main() {
  my::forward_list l;

  for (int i = 1; i <= 10; ++i) {
    l.push_front(i);
    std::cout << l.to_string() << '\n';
  }
}

Last edited on
dhayden (5795)
It has the same output as when the line was return head->data;.
it looks different (and correct) to me:
LinkedList has 0 nodes.
[ ]

Now pushing 10, 20, 30...

New Linked List Contents:
[ 10 20 30 ]

Pushing '3000' to front of linked list...

New Linked List Contents:
[ 3000 10 20 30 ]
Note: My professor's code ignore's the first element
when printing out whole thing. If I change that, it
shows: [3000 0 10 20 30]

Get First Element:
3000

LinkedList has 4 nodes.
PiggiesGoSqueal (167)
mbozzi wrote:

Eliminate special cases. Place the head node before the first element of the list. If you do that, each single-element insertion can then be specified in terms of insert_after.

N.B.: The insert_after function should take an unambiguous reference to a node - no searching required. Something like:
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
 
#include <iostream>
#include <string>

namespace my {
  struct node {
    node() = default;
    explicit node(int value, node *next = nullptr) : data_(value), next_(next) {}
  
    int data_;
    node *next_ = nullptr;
  };
  
  struct forward_list {
    forward_list() = default;
    ~forward_list() { while (!empty()) erase_after(&head_); }
    
    forward_list(forward_list const &)            = delete;
    forward_list(forward_list &&)                 = delete;
    forward_list operator=(forward_list const &)  = delete;
    forward_list operator=(forward_list const &&) = delete;

    bool empty() const { return head_.next_; }
    void push_front(int value) { insert_after(&head_, value); }
  
    std::string to_string() const {
      std::string result;
      for (node const *tmp = &head_; (tmp = tmp->next_);)
        result += std::to_string(tmp->data_) + ' ';
      return result;
    }
  
  private:
    node *erase_after(node *pos) {
      node *current = pos->next_;
      pos->next_ = current->next_;
      delete current;
      return pos->next_;
    }
  
    node *insert_after(node *pos, int value) {
      node *thing = new node(value);
      thing->next_ = pos->next_;
      return pos->next_ = thing;
    }
  
    node head_;
  };
} // namespace my

int main() {
  my::forward_list l;

  for (int i = 1; i <= 10; ++i) {
    l.push_front(i);
    std::cout << l.to_string() << '\n';
  }
}

Thanks for your reply! I think your solution is a bit more difficult/off-topic (or not the way I was trying to solve it I mean) than I was going for though. Don't get me wrong, I appreciate the comment and I've bookmarked this page for later use, so it may come in handy later. But for now, I have a ton I need to get done in the next 2-4 weeks so I'm trying to get things I need to get done before I try learning more difficult concepts that I don't need to know yet. As I said though, I appreciate your post. :)


dhayden wrote:
it looks different (and correct) to me:
...

Oh, right.. I'm blind. Was looking at the note. Thanks haha.

- - -
Post has been marked as solved. Thanks :)
Last edited on
Topic archived. No new replies allowed.