# Summing digits of a singly linked list

I want to familiarize myself with more data structures. As such I implemented a Node, singly-linked-list, as well as an algorithm to sum the digits of two such lists where each node contains the digits of a number. The order of the digits can either be largest digits first or smallest. Taking the number 1,234 as an example:

• Smallest digits first: the linked list will contain 4 as the Data property on the Head node, then 3, then 2, and lastly 1 (4->3->2->1).
• Largest digits first: Head.Data contains 1, then 2, etc... (1->2->3->4).

In the linked list I overrode the Equals method to permit value equality rather than reference equality for comparison with another list.

Algorithm logic: I first solved the algorithm manually and implemented the result in code.

Smallest digits first: Starting from the LinkedList.Head each nodes Data property can be sequentially accessed and added together. This process is repeated until the end of both lists has been reached. I thought of a Queue data structure but didn't see the need to traverse each list twice so omitted it.

Largest digits first: the position of the digits may not line up. Given a list containing 1->2 and another with 3->4->5->6 should produce 12 + 3456 = 3468. I thought it best to access each node in the list to Push them onto a stack. After all nodes had been accessed this way, each digit could be Poped off to add their values together.

The logic for each type of list is duplicated as they are essentially checking the same conditions. I would like to eliminate this duplication to have the logic in one location. The thought crossed my mind of converting the largest digits first to a smallest digits first. Doing that doesn't feel correct however.

Below are my implementations.

Node implementation:

using System.Collections.Generic;
using System.Diagnostics;

[DebuggerDisplay("{Data}")]
public class Node
{
public Node(int d)
{
Data = d;
}

public int Data { get; }

public Node Next { get; set; } = null;
}


using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("{ToString()}")]
{
{
}

{
}

{
int count = 0;
foreach (var value in values)
{
if (count == 0)
{
}
else
{
}

count++;
}
}

{
}

public Node Head { get; set; }

{
foreach (var i in value)
{
}
}

{
}

{
{
return;
}

while (n.Next != null)
{
n = n.Next;
}

n.Next = node;
}

public override string ToString()
{
var sb = new StringBuilder();

while (node != null)
{
sb.Append(node.Data);
node = node.Next;
}

return sb.ToString();
}

public override bool Equals(object obj)
{
? Equals(other)
: false;
}

{
if (ReferenceEquals(other, null))
{
return false;
}

{
return false;
}

{
return false;
}

while (thisNode != null && otherNode != null)
{
{
return false;
}

if (thisNode.Data != otherNode.Data)
{
return false;
}

thisNode = thisNode.Next;
otherNode = otherNode.Next;
}

return true;
}

private bool OnlyOneNodeNull(Node lhs, Node rhs)
{
return lhs.Next == null && rhs.Next != null
|| lhs.Next != null && rhs.Next == null;
}

public override int GetHashCode()
{
}
}


Algorithm implementation:

using System.Collections.Generic;
{
{
int carriedValue = 0;
int onesValue = 0;

while (left != null && right != null)
{
(carriedValue, onesValue) = AdditionValues(left.Data, right.Data, carriedValue);

left = left.Next;
right = right.Next;
}

if (left == null)
{
while (right != null)
{
(carriedValue, onesValue) = AdditionValues(0, right.Data, carriedValue);

right = right.Next;
}

if (carriedValue != 0)
{
}
}

if (right == null)
{
while (left != null)
{
(carriedValue, onesValue) = AdditionValues(left.Data, 0, carriedValue);

left = left.Next;
}

if (carriedValue != 0)
{
}
}

return ll;
}

{

int previouslyCarried = 0;
int onesValue = 0;
Node node = null;

while (left.Count > 0 && right.Count > 0)
{
var leftValue = left.Pop();
var rightValue = right.Pop();

(previouslyCarried, onesValue) = AdditionValues(leftValue, rightValue, previouslyCarried);
node = PrefixValuesToLargestDigitFirstNode(node, onesValue);
}

if (left.Count == 0 && right.Count == 0)
{
return previouslyCarried == 0
}

if (left.Count == 0)
{
return PrefixRemainingStackValues(node, right, previouslyCarried);
}

if (right.Count == 0)
{
return PrefixRemainingStackValues(node, left, previouslyCarried);
}

return null;
}

private LinkedList PrefixRemainingStackValues(Node node, Stack<int> stack, int previouslyCarried)
{
int onesValue = 0;
while (stack.Count > 0)
{
(previouslyCarried, onesValue) = AdditionValues(stack.Pop(), 0, previouslyCarried);
}

var updatedNode = PrefixValuesToLargestDigitFirstNode(node, onesValue);

return previouslyCarried == 0
}

private Node PrefixValuesToLargestDigitFirstNode(Node node, int value)
{
var newFirst = new Node(value)
{
Next = node
};

return newFirst;
}

private (int carryDigit, int onesValue) AdditionValues(int left, int right, int carriedValue)
{
int carry = 0;
int onesValue = 0;
int summed = left + right + carriedValue;
if (summed > 9)
{
carry = 1;
onesValue = summed % 10;
}
else
{
carry = 0;
onesValue = summed;
}

return (carry, onesValue);
}

{
var stack = new Stack<int>();
while (node != null)
{
stack.Push(node.Data);
node = node.Next;
}

return stack;
}
}
$$$$


• Node could be using generics, so Node<T> instead of always having an int
• At least some of your AddNode-methods could simply be called Add instead. Because they're actually adding a number, a list of numbers, or something else that is not exactly a Node.
• Think about the current time complexity of AddNodes(IEnumerable<int> value) and think about if it's possible to improve it somehow. (Hint: Yes, it is. A single AddNode operation gets more and more costly the more you add, but adding a bunch of them at the same time could be almost as cheap as simply adding just one)
• OnlyOneNodeNull can be simplified by using the XOR operator: lhs.Next == null ^ rhs.Next == null.
• (For bools, I find != clearer than ^) Jun 20 '20 at 11:40
• @canton7 That's also a good option yes. In this particular case I think it might be a bit confusing to mix ==, != and ==`, but it'd definitely be a valid option and might just be preference. Jun 20 '20 at 11:54