C++

Forum

 
Linked List Program ->

nicholasjb1996 (76)
I've been practising linked list for the past couple days and it's taking a while to stick in my head. I believe that I understand the concept of how it works but sometimes the assigning and pointing confuses me and I code it wrong and then have to reference a text document with my one successful try.

I have managed to create a linked list that asks the user to input a decimal value and store the value along wit the address in a struct. However I wrote a function that is supposed to calculate the total of all the values entered but it instead prints the last value the user entered. Now I am unsure if I fully understand the concept of linked lists. Any assistance is appreciated.

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

struct node
{
	double data;
	double *address;
	double total;
	node()
	{
		data = 0;
		address = &data;
		total = 0;
	}
	node *next;
};

class linkedlist
{
public:
	linkedlist()
	{
		std::cout << "Welcome To The Linked List" << '\n' << std::endl;
		head = NULL;
		tail = NULL;
	}
	
	void addnode()
	{
		node *temp = new node;
		double data;
		std::cout << "Enter Decimal Value: ";
		std::cin >> data;
		std::cout << std::endl;
		temp->data = data;
		temp->address = &data;
		temp->next = NULL;
		if (head == NULL)
		{
			head = temp;
			tail = temp;
		}
		else
		{
			tail->next = temp;
			tail = tail->next;
		}
	}

	void sum()
	{
		node *nodeptr = head;
		while (nodeptr != NULL)
		{

			nodeptr->total += nodeptr->data;
			nodeptr = nodeptr->next;
		}
	}

	void display()
	{
		node *nodeptr = head;
		while (nodeptr != NULL)
		{
			std::cout << "Decimal Value: " << nodeptr->data << " Stored At Address " << nodeptr->address << '\n' << std::endl;
			if (nodeptr->next == NULL)
			{
				std::cout << "Total Value Is: " << nodeptr->total << std::endl;
			}
			nodeptr = nodeptr->next;
		}
	}
	

private:
	node *head, *tail;
};


int main()
{
	linkedlist ll;
	ll.addnode();
	ll.addnode();
	ll.sum();
	ll.display();



	return 0; 
}
Last edited on
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
 
#include <iostream>

struct linked_list
{
    struct node
    {
        double data ;
        node* next ;
    };

    // default initialise both head and tail to null pointers
    // this creates an empty list
    node* head = nullptr ;
    node* tail = nullptr ;

    // the list is empty if head is a null pointer
    bool empty() const { return head == nullptr ; }

    // add a new item to the front of the list
    void push_front( double v )
    {
        // if empty, the new node becomes both head and tail
        // the next of this new node is a null pointer
        if( empty() ) head = tail = new node { v, nullptr } ;

        else // the list is not empty
        {
            // create a new node with value v
            // the next of this new node is the current head
            node* new_node = new node { v, head } ;

            head = new_node ; // and the new head is this new node
        }
    }

    void display() const
    {
        // for each node in the list, starting with head
        // the loop ends when tail has been processed
        // (the next of tail is a null pointer)
        for( node* p = head ; p != nullptr ; p = p->next )
        {
            std::cout << p->data ;
            if( p->next != nullptr ) std::cout << "  =>  " ;
        }
        std::cout << '\n' ;
    }

    double sum() const
    {
        double s = 0 ;
        for( node* p = head ; p != nullptr ; p = p->next ) s += p->data ;
        return s ;
    }

    // destructor etc.
};

int main()
{
    linked_list lst ;

    for( double v : { 1.2, 6.4, 3.8, 9.6, 5.7, 0.8 } ) lst.push_front(v) ;

    lst.display() ;

    std::cout << "sum: " << lst.sum() << '\n' ;
}

http://coliru.stacked-crooked.com/a/12447c890f60e0e2
nicholasjb1996 (76)
Thank you JLBorges, I saw what I did wrong when I looked at your code. I was thought to use a class when creating a linked list using pointers but I realised that you didn't. Is there a reason why you didn't use it? Also the push_front function, is that the same as a push and pop function?
JLBorges (13770)
> was thought to use a class when creating a linked list using pointers but I realised that you didn't.
> Is there a reason why you didn't use it?

I did use a class; though I used the keyword struct for defining the class.

The class keys struct and class are indistinguishable in C++, except that the default access mode and default inheritance mode are public if class declaration uses the struct class-key and private if the class declaration uses the class class-key. Both class and struct can be used in a class definition.
https://en.cppreference.com/w/cpp/language/classes



> Also the push_front function, is that the same as a push and pop function?

No. The push_front function has the similar functionality as your add function;
push_front adds (pushes) a new item to the front of the sequence.

A pop function would remove an item from the list;
for instance pop_front() would remove an item from the front of the sequence.

With pop_front() added:
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
 
#include <iostream>

struct linked_list
{
    struct node
    {
        double data ;
        node* next ;
    };

    // default initialise both head and tail to null pointers
    // this creates an empty list
    node* head = nullptr ;
    node* tail = nullptr ;

    // the list is empty if head is a null pointer
    bool empty() const { return head == nullptr ; }

    // add a new item to the front of the list
    void push_front( double v )
    {
        // if empty, the new node becomes both head and tail
        // the next of this new node is a null pointer
        if( empty() ) head = tail = new node { v, nullptr } ;

        else // the list is not empty
        {
            // create a new node with value v
            // the next of this new node is the current head
            node* new_node = new node { v, head } ;

            head = new_node ; // and the new head is this new node
        }
    }

    // remove the first item (the item at the front) in the linked list
    // invariant: there is a first item; the list is not empty
    void pop_front()
    {
        if( !empty() )
        {
            // if there is only one node in the list (head is the same as tail),
            // delete it and set both head and tail to null pointers
            if( head == tail )
            {
                delete head ;
                head = tail = nullptr ;
            }

            else // there is more than one node in the list
            {
                node* old_head = head ; // get a pointer to the current head
                head = head->next ; // after this node is gone, head will be the next node
                delete old_head ; // knock off the old head
            }
        }
    }

    void display() const
    {
        if( empty() ) std::cout << "<empty>\n" ;

        else
        {
            // for each node in the list, starting with head
            // the loop ends when tail has been processed
            // (the next of tail is a null pointer)
            for( node* p = head ; p != nullptr ; p = p->next )
            {
                std::cout << p->data ;
                if( p->next != nullptr ) std::cout << "  =>  " ;
            }
            std::cout << '\n' ;
        }
    }

    double sum() const
    {
        double s = 0 ;
        for( node* p = head ; p != nullptr ; p = p->next ) s += p->data ;
        return s ;
    }

    // destructor etc.
};

int main()
{
    linked_list lst ;

    for( double v : { 1.2, 6.4, 3.8, 9.6, 5.7, 0.8 } ) lst.push_front(v) ;

    lst.display() ;

    while( !lst.empty() )
    {
        lst.pop_front() ;
        lst.display() ;
    }
}

http://coliru.stacked-crooked.com/a/e940ea4f42d4d75e
Last edited on
dhayden (5795)
nicholasjb1996, one problem with your original code is that you're storing a total inside each node. So how is head->total supposed to differ from head->next->total? or tail->total? I think what you want is the total of all the nodes, which is what JLBorges has shown.

Also you don't need the address member. In fact, it's set incorrectly. At line 37 you set it to the address of a local variable that disappears when add_node returns.

Why are you adding items to the tail of the list? Do you need to? If not then you can simplify things by adding to the head of the list and removing the tail pointer altogether.
nicholasjb1996 (76)
@JLBorges Thanks for explaining that, in my lectures they try to explain everything in one session so I forget some stuff that they teach. Sorry if I seem repetitive but I know that a push function adds a piece of data to the top of a stack and increases the size by one. Is the addnode the same?

@dhayden After seeing JLBorges code I saw the error I made and used a while loop in a void function to add the values and set the total each time the total increased before hitting NULL.
Also you don't need the address member. In fact, it's set incorrectly. At line 37 you set it to the address of a local variable that disappears when add_node returns.

I also saw that error and changed it.
 
 
temp->address = &temp->data;

Why are you adding items to the tail of the list? Do you need to? If not then you can simplify things by adding to the head of the list and removing the tail pointer altogether.

How I understand it is that I set the head and then I add a node and move the tail pointer to the point to the next node. Looking at JLBorges code I see that he didn't add nodes to the tail but to the head and moving the head pointer. I didn't know you could do that until just now. Is this the better way to create a linked list?
Last edited on
JLBorges (13770)
> Looking at JLBorges code I see that he didn't add nodes to the tail but to the head and moving the head pointer.

I just gave push_front() as an illustrative example.
I could, as easily, have used push_back() for the example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
// add a new item to the back of the list
void push_back( double v )
{
    // if empty, the new node becomes both head and tail
    // the next of this new node is a null pointer
    if( empty() ) head = tail = new node { v, nullptr } ;

    else // the list is not empty
    {
        // create a new node with value v
        // the next of this new node is the nullptr
        // and it becomes the next of the current tail
        tail->next = new node { v, nullptr } ;

        tail = tail->next ; // and the new tail is this new node
    }
}

http://coliru.stacked-crooked.com/a/6b99a13481daf896


> Is this the better way to create a linked list?

A real life linked list would typically provide for adding and removing items at either end
(as well as a lot of other functions).
In actual code, one would use the list (or far more often vector) implementation from the standard library.

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

// display the contents of a sequence container
template < typename SEQUENCE> void display( const SEQUENCE& seq )
{
    if( seq.empty() ) std::cout << "<empty>\n" ;

    for( auto v : seq ) std::cout << v << ' ' ;
    std::cout << '\n' ;
}

int main()
{
    // https://en.cppreference.com/w/cpp/container/list
    std::list<double> lst ;

    for( double v : { 20.6, 29.2, 24.3, 25.8 } ) lst.push_back(v) ;
    display(lst) ;

    for( double v : { 16.4, 12.2, 18.3, 17.8 } ) lst.push_front(v) ;
    display(lst) ;

    lst.sort() ;
    display(lst) ;

    while( lst.size() > 4 )
    {
        lst.pop_back() ;
        display(lst) ;
    }

    while( !lst.empty() )
    {
        lst.pop_front() ;
        display(lst) ;
    }
}

http://coliru.stacked-crooked.com/a/d17e37c861997b3d
nicholasjb1996 (76)
Thank you for the explanation, I partially understand what you did but I guess that its due to the learning curve since I still have a lot to learn and understand.
dhayden (5795)
Is [adding to the head instead of tail] the better way to create a linked list?
Before the STL, I rarely needed a tail pointer with a linked list. A tail pointer lets you efficiently add to the back of the list, but if you don't need to add there then why do it? Why encumber your code with the extra code, data, and runtime needed to maintain a tail pointer?

So if I had to create a linked list, I wouldn't add a tail pointer unless I needed it. But these days in a professional setting, there's rarely, if ever, a need to create a linked list. It's easier and more reliable to use std::list<> or std::forward_list<>
Topic archived. No new replies allowed.