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
Dataproperty on theHeadnode, then 3, then 2, and lastly 1 (4->3->2->1). - Largest digits first:
Head.Datacontains 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;
}
LinkedList implementation:
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("{ToString()}")]
public class LinkedList
{
public LinkedList()
{
}
public LinkedList(int data)
{
Head = new Node(data);
}
public LinkedList(IEnumerable<int> values)
{
int count = 0;
foreach (var value in values)
{
if (count == 0)
{
Head = new Node(value);
}
else
{
AddNode(value);
}
count++;
}
}
public LinkedList(Node headNode)
{
Head = headNode;
}
public Node Head { get; set; }
public void AddNodes(IEnumerable<int> value)
{
foreach (var i in value)
{
AddNode(i);
}
}
public void AddNode(int value)
{
AddNode(new Node(value));
}
public void AddNode(Node node)
{
if (Head == null)
{
Head = node;
return;
}
Node n = Head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = node;
}
public override string ToString()
{
var sb = new StringBuilder();
var node = Head;
while (node != null)
{
sb.Append(node.Data);
node = node.Next;
}
return sb.ToString();
}
public override bool Equals(object obj)
{
return obj is LinkedList other
? Equals(other)
: false;
}
public bool Equals(LinkedList other)
{
if (ReferenceEquals(other, null))
{
return false;
}
if (Head.Data != other.Head.Data)
{
return false;
}
if (OnlyOneNodeNull(Head.Next, other.Head.Next))
{
return false;
}
var thisNode = Head.Next;
var otherNode = other.Head.Next;
while (thisNode != null && otherNode != null)
{
if (OnlyOneNodeNull(Head.Next, other.Head.Next))
{
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()
{
return 1473396059 + EqualityComparer<Node>.Default.GetHashCode(Head);
}
}
Algorithm implementation:
using System.Collections.Generic;
public class SumLinkedListDigits
{
public LinkedList SmallestDigitsFirst(LinkedList ll1, LinkedList ll2)
{
var left = ll1.Head;
var right = ll2.Head;
var ll = new LinkedList();
int carriedValue = 0;
int onesValue = 0;
while (left != null && right != null)
{
(carriedValue, onesValue) = AdditionValues(left.Data, right.Data, carriedValue);
ll.AddNode(new Node(onesValue));
left = left.Next;
right = right.Next;
}
if (left == null)
{
while (right != null)
{
(carriedValue, onesValue) = AdditionValues(0, right.Data, carriedValue);
ll.AddNode(onesValue);
right = right.Next;
}
if (carriedValue != 0)
{
ll.AddNode(carriedValue);
}
}
if (right == null)
{
while (left != null)
{
(carriedValue, onesValue) = AdditionValues(left.Data, 0, carriedValue);
ll.AddNode(onesValue);
left = left.Next;
}
if (carriedValue != 0)
{
ll.AddNode(carriedValue);
}
}
return ll;
}
public LinkedList LargestDigitsFirst(LinkedList ll1, LinkedList ll2)
{
var left = StackFromLinkedList(ll1);
var right = StackFromLinkedList(ll2);
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
? new LinkedList(node)
: new LinkedList(PrefixValuesToLargestDigitFirstNode(node, previouslyCarried));
}
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
? new LinkedList(updatedNode)
: new LinkedList(PrefixValuesToLargestDigitFirstNode(updatedNode, onesValue));
}
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);
}
private Stack<int> StackFromLinkedList(LinkedList linkedList)
{
var node = linkedList.Head;
var stack = new Stack<int>();
while (node != null)
{
stack.Push(node.Data);
node = node.Next;
}
return stack;
}
}
```
