Write a code snippet that would find the sum of the elements present in a Singly linked list

Sum of the nodes of a Singly Linked List

Given a singly linked list. The task is to find the sum of nodes of the given linked list.

Table of Contents Show

Sum of the nodes of a Singly Linked List
Sum of the nodes of a Singly Linked List in C Program
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List
Program to create a singly linked list of n nodes and count the number of nodes
Explanation
LinkedList representation

Task is to do A + B + C + D.

Examples:

Input: 7->6->8->4->1 Output: 26 Sum of nodes: 7 + 6 + 8 + 4 + 1 = 26 Input: 1->7->3->9->11->5 Output: 36

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Recursive Solution:

Call a function by passing the head and variable to store the sum.
- Then recursively call the function by passing the next of current node and sum variable.
  - Add the value of the current node to the sum.

Below is the implementation of above approach:

C++

// C++ implementation to find the sum of 
// nodes of the Linked List 
#include <bits/stdc++.h> 

using namespace std;

/* A Linked list node */

struct Node {

int data;

struct Node* next;
}; 

// function to insert a node at the 
// beginning of the linked list 

void push(struct Node** head_ref, int new_data)
{ 

/* allocate node */

struct Node* new_node = new Node;

/* put in the data */

new_node->data = new_data;

/* link the old list to the new node */

new_node->next = (*head_ref);

/* move the head to point to the new node */

(*head_ref) = new_node;
} 

// function to recursively find the sum of 
// nodes of the given linked list 

void sumOfNodes(struct Node* head, int* sum)
{ 

// if head = NULL

if (!head)

return;

// recursively traverse the remaining nodes

sumOfNodes(head->next, sum);

// accumulate sum

*sum = *sum + head->data;
} 

// utility function to find the sum of nodes 

int sumOfNodesUtil(struct Node* head)
{ 

int sum = 0;

// find the sum of nodes

sumOfNodes(head, &sum);

// required sum

return sum;
} 

// Driver program to test above 

int main()
{ 

struct Node* head = NULL;

// create linked list 7->6->8->4->1

push(&head, 7);

push(&head, 6);

push(&head, 8);

push(&head, 4);

push(&head, 1);

cout << "Sum of nodes = "

<< sumOfNodesUtil(head);

return 0;
}

Java

// Java implementation to find the sum of 
// nodes of the Linked List 

class GFG
{ 

static int sum=0;

// A Linked list node / 

static class Node
{ 

int data;

Node next;
} 

// function to insert a node at the 
// beginning of the linked list 

static Node push( Node head_ref, int new_data)
{ 

// allocate node /

Node new_node = new Node();

// put in the data /

new_node.data = new_data;

// link the old list to the new node /

new_node.next = (head_ref);

// move the head to point to the new node /

(head_ref) = new_node;

return head_ref;
} 

// function to recursively find the sum of 
// nodes of the given linked list 

static void sumOfNodes( Node head)
{ 

// if head = null

if (head == null)

return;

// recursively traverse the remaining nodes

sumOfNodes(head.next);

// accumulate sum

sum = sum + head.data;
} 

// utility function to find the sum of nodes 

static int sumOfNodesUtil( Node head)
{ 

sum = 0;

// find the sum of nodes

sumOfNodes(head);

// required sum

return sum;
} 

// Driver program to test above 

public static void main(String args[])
{ 

Node head = null;

// create linked list 7.6.8.4.1

head = push(head, 7);

head = push(head, 6);

head = push(head, 8);

head = push(head, 4);

head = push(head, 1);

System.out.println( "Sum of nodes = "

+ sumOfNodesUtil(head));
} 
} 

// This code is contributed by Arnab Kundu

Python3

# Python3 implementation to find the sum of 
# nodes of the Linked List 

import math

# class for a Sum 

class Sum:

tsum = None

# A Linked list node 

class Node:

def __init__(self,data):

self.data = data

self.next = None

# function to insert a node at the 
# beginning of the linked list 

def push(head, data):

if not head:

return Node(data)

# put in the data

# and allocate node

new_node = Node(data)

# link the old list to the new node

new_node.next = head

# move the head to point

# to the new node

head = new_node

return head

# function to recursively find 
# the sum of nodes of the given 
# linked list 

def sumOfNode(head, S):

# if head = NULL

if not head:

return

# recursively traverse the

# remaining nodes

sumOfNode(head.next, S)

# accumulate sum

S.tsum += head.data

# utility function to find 
# the sum of nodes 

def sumOfNodesUtil(head):

S = Sum()

S.tsum = 0

# find the sum of nodes

sumOfNode(head, S)

# required sum

return S.tsum

# Driver Code 

if __name__=='__main__':

head = None

# create linked list 7->6->8->4->1

head = push(head, 7)

head = push(head, 6)

head = push(head, 8)

head = push(head, 4)

head = push(head, 1)

print("Sum of Nodes = {}" .

format(sumOfNodesUtil(head)))

# This code is contributed 
# by Vikash Kumar 37

// C# implementation to find the sum of 
// nodes of the Linked List 

using System;

class GFG
{ 

public static int sum = 0;

// A Linked list node /

public class Node

{

public int data;

public Node next;

}

// function to insert a node at the

// beginning of the linked list

static Node push(Node head_ref, int new_data)

{

// allocate node /

Node new_node = new Node();

// put in the data /

new_node.data = new_data;

// link the old list to the new node /

new_node.next = (head_ref);

// move the head to point to the new node /

(head_ref) = new_node;

return head_ref;

}

// function to recursively find the sum of

// nodes of the given linked list

static void sumOfNodes(Node head)

{

// if head = null

if (head == null)

return;

// recursively traverse the remaining nodes

sumOfNodes(head.next);

// accumulate sum

sum = sum + head.data;

}

// utility function to find the sum of nodes

static int sumOfNodesUtil(Node head)

{

sum = 0;

// find the sum of nodes

sumOfNodes(head);

// required sum

return sum;

}

// Driver program to test above

public static void Main(String[] args)

{

Node head = null;

// create linked list 7.6.8.4.1

head = push(head, 7);

head = push(head, 6);

head = push(head, 8);

head = push(head, 4);

head = push(head, 1);

Console.WriteLine("Sum of nodes = " +

sumOfNodesUtil(head));

}
} 

// This code is contributed by Rajput-Ji

Javascript

<script> 

// JavaScript implementation to find the sum of 
// nodes of the Linked List 

var sum = 0;

// A Linked list node /
class Node { 

constructor(val) {

this.data = val;

this.next = null;

}
} 

// function to insert a node at the

// beginning of the linked list

function push(head_ref , new_data) {

// allocate node /

var new_node = new Node();

// put in the data /

new_node.data = new_data;

// link the old list to the new node /

new_node.next = (head_ref);

// move the head to point to the new node /

(head_ref) = new_node;

return head_ref;

}

// function to recursively find the sum of

// nodes of the given linked list

function sumOfNodes(head) {

// if head = null

if (head == null)

return;

// recursively traverse the remaining nodes

sumOfNodes(head.next);

// accumulate sum

sum = sum + head.data;

}

// utility function to find the sum of nodes

function sumOfNodesUtil(head) {

sum = 0;

// find the sum of nodes

sumOfNodes(head);

// required sum

return sum;

}

// Driver program to test above

var head = null;

// create linked list 7.6.8.4.1

head = push(head, 7);

head = push(head, 6);

head = push(head, 8);

head = push(head, 4);

head = push(head, 1);

document.write("Sum of nodes = " +

sumOfNodesUtil(head));

// This code contributed by umadevi9616 

</script>

Output: Sum of nodes = 26

Time Complexity: O(N) , N is the number of nodes in a linked list.
Auxiliary Space: O(N), only if the stack size is considered during recursive calls.
Iterative Solution:

Initialize a pointer ptr with the head of the linked list and a sum variable with 0.
Start traversing the linked list using a loop until all the nodes get traversed.
- Add the value of current node to the sum i.e. sum += ptr -> data .
- Increment the pointer to the next node of linked list i.e. ptr = ptr ->next .
Return the sum.

Below is the implementation of above approach:

C++

// C++ implementation to find the sum of 
// nodes of the Linked List 
#include <bits/stdc++.h> 

using namespace std;

/* A Linked list node */

struct Node {

int data;

struct Node* next;
}; 

// function to insert a node at the 
// beginning of the linked list 

void push(struct Node** head_ref, int new_data)
{ 

/* allocate node */

struct Node* new_node = new Node;

/* put in the data */

new_node->data = new_data;

/* link the old list to the new node */

new_node->next = (*head_ref);

/* move the head to point to the new node */

(*head_ref) = new_node;
} 

// function to find the sum of 
// nodes of the given linked list 

int sumOfNodes(struct Node* head)
{ 

struct Node* ptr = head;

int sum = 0;

while (ptr != NULL) {

sum += ptr->data;

ptr = ptr->next;

}

return sum;
} 

// Driver program to test above 

int main()
{ 

struct Node* head = NULL;

// create linked list 7->6->8->4->1

push(&head, 7);

push(&head, 6);

push(&head, 8);

push(&head, 4);

push(&head, 1);

cout << "Sum of nodes = "

<< sumOfNodes(head);

return 0;
}

Java

// Java implementation to find the sum of 
// nodes of the Linked List 

class GFG
{ 

static Node head;

/* A Linked list node */

static class Node
{ 

int data;

Node next;
}; 

// function to insert a node at the 
// beginning of the linked list 
// Inserting node at the beginning 

static Node push(Node head_ref, int new_data)
{ 

/* allocate node */

Node new_node = new Node();

/* put in the data */

new_node.data = new_data;

/* link the old list to the new node */

new_node.next = head_ref;

/* move the head to point to the new node */

head_ref = new_node;

return head=head_ref;
} 

// function to find the sum of 
// nodes of the given linked list 

static int sumOfNodes( Node head)
{ 

Node ptr = head;

int sum = 0;

while (ptr != null)

{

sum += ptr.data;

ptr = ptr.next;

}

return sum;
} 

// Driver code 

public static void main(String[] args)
{ 

// create linked list 7.6.8.4.1

push(head, 7);

push(head, 6);

push(head, 8);

push(head, 4);

push(head, 1);

System.out.println("Sum of nodes = "

+ sumOfNodes(head));
} 
} 

/* This code is contributed by PrinciRaj1992 */

Python3

# Python3 implementation to find the 
# sum of nodes of the Linked List 

import math

# A Linked list node 

class Node:

def __init__(self, data):

self.data = data

self.next = None

# function to insert a node at the 
# beginning of the linked list 

def push(head_ref, new_data):

# allocate node

new_node = Node(new_data)

# put in the data

new_node.data = new_data

# link the old list to the new node

new_node.next = head_ref

# move the head to po to the new node

head_ref = new_node

return head_ref

# function to find the sum of 
# nodes of the given linked list 

def sumOfNodes(head):

ptr = head

sum = 0

while (ptr != None):

sum = sum + ptr.data

ptr = ptr.next

return sum

# Driver Code 

if __name__=='__main__':

head = None

# create linked list 7.6.8.4.1

head = push(head, 7)

head = push(head, 6)

head = push(head, 8)

head = push(head, 4)

head = push(head, 1)

print("Sum of nodes =",

sumOfNodes(head))

# This code is contributed by Srathore

// C# implementation to find the sum of 
// nodes of the Linked List 

using System;

class GFG
{ 

static Node head;

/* A Linked list node */

public class Node
{ 

public int data;

public Node next;
}; 

// function to insert a node at the 
// beginning of the linked list 
// Inserting node at the beginning 

static Node push(Node head_ref, int new_data)
{ 

/* allocate node */

Node new_node = new Node();

/* put in the data */

new_node.data = new_data;

/* link the old list to the new node */

new_node.next = head_ref;

/* move the head to point to the new node */

head_ref = new_node;

return head=head_ref;
} 

// function to find the sum of 
// nodes of the given linked list 

static int sumOfNodes( Node head)
{ 

Node ptr = head;

int sum = 0;

while (ptr != null)

{

sum += ptr.data;

ptr = ptr.next;

}

return sum;
} 

// Driver code 

public static void Main(String[] args)
{ 

// create linked list 7.6.8.4.1

push(head, 7);

push(head, 6);

push(head, 8);

push(head, 4);

push(head, 1);

Console.WriteLine("Sum of nodes = "

+ sumOfNodes(head));
} 
} 

// This code is contributed by 29AjayKumar

Javascript

<script> 
// javascript implementation to find the sum of 
// nodes of the Linked List 

var head;

/* A Linked list node */

class Node {

constructor() {

this.data = 0;

this.next = null;

}

}

// function to insert a node at the

// beginning of the linked list

// Inserting node at the beginning

function push(head_ref , new_data) {

/* allocate node */

var new_node = new Node();

/* put in the data */

new_node.data = new_data;

/* link the old list to the new node */

new_node.next = head_ref;

/* move the head to point to the new node */

head_ref = new_node;

return head = head_ref;

}

// function to find the sum of

// nodes of the given linked list

function sumOfNodes(head) {

var ptr = head;

var sum = 0;

while (ptr != null) {

sum += ptr.data;

ptr = ptr.next;

}

return sum;

}

// Driver code

// create linked list 7.6.8.4.1

push(head, 7);

push(head, 6);

push(head, 8);

push(head, 4);

push(head, 1);

document.write("Sum of nodes = " + sumOfNodes(head));

// This code contributed by aashish2995 
</script>

Output: Sum of nodes = 26

Time Complexity: O(N), N is the number of nodes in a linked list.
Auxiliary Space: O(1)

Article Tags :

Linked List

Algorithms-Recursion

Data Structures-Linked List

Traversal

Practice Tags :

Linked List

Traversal

Read Full Article

Sum of the nodes of a Singly Linked List in C Program

CServer Side ProgrammingProgramming

A singly linked list is a data structure in which an element has two parts one is the value and other is the link to the next element. So to find the sum of all elements of the singly linked list, we have to navigate to each node of the linked list and add the element's value to a sum variable.

For example

Suppose we have a linked list: 2 -> 27 -> 32 -> 1 -> 5 sum = 2 + 27 + 32 + 1 + 5 = 67.

This can be done by using two methods :

Method 1- Using a loop that loops over all the values of the linked list and finds the sum.

The loop runs till the end of the linked list i.e. when the pointer of an element points to null, this loop will run and find the sum of values of each element.

Linked List Operations: Traverse, Insert and Delete

In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.

There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

Traversal - access each element of the linked list
Insertion - adds a new element to the linked list
Deletion - removes the existing elements
Search - find a node in the linked list
Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

head points to the first node of the linked list
next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

struct node { int data; struct node *next; };

Program to create a singly linked list of n nodes and count the number of nodes

Explanation

In this program, we need to create a singly linked list and count the nodes present in the list.

To accomplish this task, traverse through the list using node current which initially points to head. Increment current in such a way that current will point to its next node in each iteration and increment variable count by 1. In the end, the count will hold the value which denotes the number of nodes present in the list.

Algorithm

Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
Create another class which has two attributes: head and tail.
addNode() will add a new node to the list:
1. Create a new node.
2. It first checks, whether the head is equal to null which means the list is empty.
3. If the list is empty, both head and tail will point to the newly added node.
4. If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
countNodes() will count the nodes present in the list:
1. Define a node current which will initially point to the head of the list.
2. Declare and initialize a variable count to 0.
3. Traverse through the list till current point to null.
4. Increment the value of count by 1 for each node encountered in the list.
display() will display the nodes present in the list:
1. Define a node current which will initially point to the head of the list.
2. Traverse through the list till current points to null.
3. Display each node by making current to point to node next to it in each iteration.

Solution

Python

Output:

Nodes of singly linked list: 1 2 3 4 Count of nodes present in the list: 4

Output:

Nodes of singly linked list: 1 2 3 4 Count of nodes present in the list: 4

JAVA

Output:

Nodes of the singly linked list: 1 2 3 4 Count of nodes present in the list: 4

C#

Output:

Nodes of singly linked list: 1 2 3 4 Count of nodes present in the list: 4

PHP

Output:

Nodes of singly linked list: 1 2 3 4 Count of nodes present in the list: 4

LinkedList representation

Each element in the LinkedList is called the Node. Each Node of the LinkedList contains two items: 1) Content of the element 2) Pointer/Address/Reference to the Next Node in the LinkedList.

This is how a LinkedList looks:

Note:
1. Head of the LinkedList only contains the Address of the First element of the List.
2. The Last element of the LinkedList contains null in the pointer part of the node because it is the end of the List so it doesn’t point to anything as shown in the above diagram.
3. The diagram which is shown above represents a singly linked list. There is another complex type variation of LinkedList which is called doubly linked list, node of a doubly linked list contains three parts: 1) Pointer to the previous node of the linked list 2) content of the element 3) pointer to the next node of the linked list.