7
\$\begingroup\$

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;
    }

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;
        }
    }
```
\$\endgroup\$
7
\$\begingroup\$
  • I don't think exposing the Node class is useful. It should probably be mostly an internal class within your class (or at least package/namespace)
  • 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.

Overall, good job :)

\$\endgroup\$
  • \$\begingroup\$ (For bools, I find != clearer than ^) \$\endgroup\$ – canton7 Jun 20 '20 at 11:40
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Simon Forsberg Jun 20 '20 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.