0
\$\begingroup\$

There are many if statements. How can I write more clean and readable code?

package com.company;

/**
 * Created by qulain on 5/12/2017.
 */


public class AddTwoLinkedLists {

    static Node head1, head2;

    static class Node {

        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    public static Node addTwoLinkedLists(Node head1, Node head2) {
        /*ALGORITHM:
        1. Create a resultant list and move the tail pointer whenever add a node
        2. Loop the linkedLists while anyone exists
        3. calculate the sum of two nodes: If node does not exist in any of the linkedlist-> add zero for that node
               if sum of two nodes > 10, carry = 1 : else carry = 0;
        4. create a temporary node with data = sum and append it it to resultant list
        5. increment pointers of linkedlist1 and linkedlist2 (if they are not null)
        */
        Node resultantList = null;
        Node tail = null;
        int sum,carry = 0;

        /* loop will continue if any of the list exists */
        while( (head1 != null) || (head2 != null) ) {
            int dataFrom1stLinkedList = 0;
            int dataFrom2stLinkedList = 0;

            /* Check if node in 1st list exist and then get the data, otherwise get 0 */
            dataFrom1stLinkedList = head1 != null? head1.data : 0;
            /* Check if node in 2nd list exist and then get the data, otherwise get 0 */
            dataFrom2stLinkedList = head2 != null ? head2.data : 0;

            /* Get sum of two nodes and update carry value for next calculation */
            int sumOfTwoNodes = dataFrom1stLinkedList + dataFrom2stLinkedList + carry;
            if(sumOfTwoNodes >= 10) {
                sum = sumOfTwoNodes  % 10;
                carry = 1;
            } else {
                sum = sumOfTwoNodes;
                carry = 0;
            }
            if ( head1 != null ) {
                head1 = head1.next;
            }

            if ( head2 != null ) {
                head2 = head2.next;
            }

            /* create a new node and append it in resultant list */
            Node temp = new Node(sum);
            // if its a first element in list
            if (resultantList == null ) {
                resultantList = temp;
                tail = temp;
            } else  {
                tail.next = temp;
            }
            tail = temp;

        }

        return resultantList;
    }

    /* Utility function to print a linked list */
    void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        AddTwoLinkedLists testCase1 = new AddTwoLinkedLists();
        AddTwoLinkedLists testCase2 = new AddTwoLinkedLists();

        // creating first list for testCase 1
        testCase1.head1 = new Node(7);
        testCase1.head1.next = new Node(5);
        testCase1.head1.next.next = new Node(9);
        testCase1.head1.next.next.next = new Node(4);
        testCase1.head1.next.next.next.next = new Node(6);
        System.out.print("First List is ");
        testCase1.printList(head1);

        // creating seconnd list
        testCase1.head2 = new Node(8);
        testCase1.head2.next = new Node(4);
        System.out.print("Second List is ");
        testCase1.printList(head2);

        // add the two lists and see the result
        Node rs1 = testCase1.addTwoLinkedLists(head1, head2);
        System.out.print("Resultant List is ");
        testCase1.printList(rs1);

        // creating first list for testCase 1
        testCase2.head1 = new Node(5);
        testCase2.head1.next = new Node(6);
        testCase2.head1.next.next = new Node(3);
        System.out.print("First List is ");
        testCase1.printList(head1);

        // creating seconnd list
        testCase2.head2 = new Node(8);
        testCase2.head2.next = new Node(4);
        testCase2.head2 = new Node(2);
        System.out.print("Second List is ");
        testCase1.printList(head2);

        // add the two lists and see the result
        Node rs2 = testCase1.addTwoLinkedLists(head1, head2);
        System.out.print("Resultant List is ");
        testCase1.printList(rs2);
    }
}
\$\endgroup\$
2
\$\begingroup\$

The code in general looks okay going by the method you are doing. The only main thing I could think to streamline is your sumOfTwoNodes section and combine a few lines. Because you want to check if you're going to have a carry, you could actually perform the code like this;

        /* Get sum of two nodes and update carry value for next calculation */
        int sumOfTwoNodes = dataFrom1stLinkedList + dataFrom2stLinkedList + carry;

        carry = sumOfTwoNodes >= 10 ? 1 : 0;
        sum = sumOfTwoNodes % 10

We can do this because any number less than 10 modulo 10 will be that number regardless. 6 % 10 is still 6. So instead of selectively applying modulo if the number is greater than 10, we can just apply it anyway after we see if it's greater than 10 for the carry.

Some other streamlining options you could do would be immediately assigning the data variables;

        int dataFrom1stLinkedList = head1 != null ? head1.data : 0;
        int dataFrom2stLinkedList = head2 != null ? head2.data : 0;

Or we could rearrange the null checking if statements of the head1 and head2 to before the summing since we're already checking if they're null. Minimizing redundant if statements is always useful.

        int dataFrom1stLinkedList = 0;
        int dataFrom2stLinkedList = 0;

        if( head1 != null ){
            dataFrom1stLinkedList = head1.data;
            head1 = head1.next;
        }
        if( head2 != null ){
            dataFrom2stLinkedList = head2.data;
            head2 = head2.next;
        }

Other than that, here are some tips to consider when writing code.

Variable Naming

It may seem minor, but naming variables, functions, what have you helps immensely in readability and clarity. Many languages have their own traditional naming conventions but in general keeping variable names shorter and self explanatory helps cut down errors in typos, misremembering variables, etc...

For example, instead of using this in your code;

        int dataFrom1stLinkedList = 0;
        int dataFrom2stLinkedList = 0;

Something like this might be more readable and less prone to typos (noticing "2st" in the second variable);

        int listData1 = 0;
        int listData2 = 0;

Since, after all, we know this is a linked list program, we don't need to constantly reference "linked", or heck we could just have "data1" and "data2" if we really feel like it. Short, sweet, as detailed as it needs to be.

Brackets

This is more of a personal preference, but for many languages an if/else statement that has only one line of code it is executing you can remove the brackets and just have that line of code be immediately below it. For example;

        // This...
        if ( head1 != null ) {
            head1 = head1.next;
        }

       // Becomes this...
       if ( head1 != null )
            head1 = head1.next;

It's minor, but some people prefer it as it removes unnecessary lines and brackets to keep track of.

\$\endgroup\$
  • \$\begingroup\$ I fully disagree with your "Brackets" comment. You should always put curly braces after each if/else/for/... As already explained here on stackoverflow \$\endgroup\$ – Imus May 16 '17 at 7:09
1
\$\begingroup\$

I started refactoring the addTwoLinkedLists with some crazy ideas like returning fast if one of the arguments was null, or later on if the carry is 0 and one of the lists is null (in those cases you can just add the non-empty list to the result and return the resulting list).

But I kept duplicating code to handle the separate cases without really improving the readability. So I started over and just tried to rename and restructure your current implementation a bit instead to see how readable that becomes. The result looks like this:

public static Node addTwoLinkedLists(Node head1, Node head2) {
    /*ALGORITHM:
    1. Create a resultant list and move the tail pointer whenever add a node
    2. Loop the linkedLists while anyone exists
    3. calculate the sum of two nodes: If node does not exist in any of the linkedlist-> add zero for that node
           if sum of two nodes > 10, carry = 1 : else carry = 0;
    4. create a temporary node with data = sum and append it it to resultant list
    5. increment pointers of linkedlist1 and linkedlist2 (if they are not null)
    */
    Node resultantList = null;
    Node previousNode = null;
    int carry = 0;

    while( (head1 != null) || (head2 != null) ) {
        int sum = carry;
        if(head1 != null){
            sum += head1.data;
        }
        if(head2 != null) {
            sum += head2.data;
        }

        carry = sum / 10;
        Node currentNode = new Node(sum % 10);

        if (resultantList == null ) {
            resultantList = currentNode;
            previousNode = currentNode;
        } else  {
            previousNode.next = currentNode;
            previousNode = previousNode.next;
        }

        if ( head1 != null ) {
            head1 = head1.next;
        }
        if ( head2 != null ) {
            head2 = head2.next;
        }
    }

    if(carry > 0) {
        previousNode.next = new Node(carry);
    }

    return resultantList;
}

The most notable changes here are:

  • putting the headX = headX.next handling at the end of the loop.
  • renaming temp to currentNode and tail to previousNode to fit better with what they actually are.
  • removed the `dataFromXLinkedList variables in favor of directly adding it to the sum.
  • Inlined your sum variable in the temp node creation.
  • put redundand tail=temp inside the else (as opposed to removing it from the if statement) and changed it to tail = tail.next to better show what's happening.
  • removed redundant comments. If you need a comment to tell what the code does it's usually a sign that you want to rename things.

I also fixed a bug that you ignored the carry if both lists are empty. For examle if you have the list {8} and {9} you want the result {7,1} but got {7}.

This actually looks good enough to me :)


Next is the printList method. Having to create an instance of the class just to call this method seems wrong to me. It should be static just like the addTwoLinkedLists method. I also noticed that you call that last one on an instance. But I'll come back to that after rewriting the printList method.

After refactoring most of the previous method I finally understood that the "lists" are actualy linked list representations of numbers. So when you want to print such a number, the most natural way would be from the most significant to the least. I would write this like so:

/* Utility function to print a linked list */
public static void printList(Node head) {
    StringBuilder result = new StringBuilder();
    while (head != null) {
        result.append(head.data);
        head = head.next;
    }
    System.out.println(result.toString());
}

Next I'm wondering how you intend to use this class. You have an internal static class Node that can only be accessed inside the package of this class. This doesn't really make sense, since that means we can access the AddTwoLinkedLists class from outside the package, but can't do anything with it. So let's at least make the Node class public as well.

There are also 2 Node fields inside the class. I see absolutely no reason why these exist. You use them in your main method, and even overwrite the exact same variables for the second test case. So I guess you don't know what static means.

Here is a main method that does exactly the same thing as yours did, but without instantiating the class:

public static void main(String[] args) {
    Node head1;
    Node head2;

    // creating first list for testCase 1
    head1 = new Node(7);
    head1.next = new Node(5);
    head1.next.next = new Node(9);
    head1.next.next.next = new Node(4);
    head1.next.next.next.next = new Node(6);
    System.out.print("First List is ");
    AddTwoLinkedLists.printList(head1);

    // creating seconnd list
    head2 = new Node(8);
    head2.next = new Node(4);
    System.out.print("Second List is ");
    AddTwoLinkedLists.printList(head2);

    // add the two lists and see the result
    Node rs1 = addTwoLinkedLists(head1, head2);
    System.out.print("Resultant List is ");
    AddTwoLinkedLists.printList(rs1);

    // creating first list for testCase 1
    head1 = new Node(5);
    head1.next = new Node(6);
    head1.next.next = new Node(3);
    System.out.print("First List is ");
    AddTwoLinkedLists.printList(head1);

    // creating seconnd list
    head2 = new Node(8);
    head2.next = new Node(4);
    head2 = new Node(2);
    System.out.print("Second List is ");
    AddTwoLinkedLists.printList(head2);

    // add the two lists and see the result
    Node rs2 = addTwoLinkedLists(head1, head2);
    System.out.print("Resultant List is ");
    AddTwoLinkedLists.printList(rs2);
}

Notice how the head1 and head2 variables are re-used for both tests? You also did this since they were static. Calling testCase1.head1 is exactly the same as calling AddTwoLinkedLists.head1. You never needed that instance in the first place.

If we now look at the class it becomes clear that it's actually a collection of utility functions. So let's make this perfectly clear in the code as well like so:

public class LinkedListNumberUtils {

    private LinkedListNumberUtils(){}

I renamed the class to point out that it's a collection of utility functions that work on some LinkedListNumber. And I added a private constructor so that nobody can instantiate an instance of this class (they shouldn't do so in the first place).



Now that I showed you how your solution could look like with some basic restructuring I'll also show a completely different approach. Here's what happens if you make the Node class do most of the work:

public static class Node implements Cloneable {
    public int data;
    public Node next = null;

    /**
     * data should be a number between 0 and 9.
     * To create a new Node from a higher number use createNode(int number) instead.
     */
    public Node(int data){
        this.data = data;
    }

    public static Node createNode(int number){
        Node result = new Node(0);
        result.add(number);
        return result;
    }

    public void add(int d){
        int sum = d+data;
        int carry = sum/10;
        data = sum%10;
        if(carry > 0){
            if(next == null){
                next = new Node(carry);
            } else {
                next.add(carry);
            }
        }
    }

    @Override
    public Node clone(){
        Node result = new Node(data);
        Node head = next;
        Node current = result;
        while(head != null){
            current.next = head;
            current = current.next;
            head = head.next;
        }
        return result;
    }

    @Override
    public String toString(){
        StringBuilder result = new StringBuilder(Integer.toString(data));
        Node head = next;
        while(head != null){
            result.insert(0,head.data);
            head = head.next;
        }
        return result.toString();
    }
}

public static Node add(Node head1, Node head2){
    if(head1 == null){
        if(head2 == null) {
            return new Node(0); // nicer to return the number 0 instead of null
        }
        return head2.clone();
    }
    if(head2 == null){
        return head1.clone();
    }

    Node result = head1.clone();
    Node previousNode = result;
    previousNode.add(head2.data);
    head2 = head2.next;

    while(previousNode.next != null && head2 != null){
        previousNode = previousNode.next;
        previousNode.add(head2.data);
        head2 = head2.next;
    }
    if(head2 != null){
        previousNode.next = head2.clone();
    }
    return result;
}

Important note here is that I never used recursion. That way we can use our program for large numbers as well without being afraid of a stackoverflow. Take this for example:

public static void main(String[] args) {
    Node head2 = Node.createNode(Integer.MAX_VALUE);
    System.out.println(head2);
    Node head1 = Node.createNode(Integer.MAX_VALUE);
    System.out.println(head1);
    System.out.println(LinkedListNumberUtils.add(head1, head2));
}

It also shows what makes this linked list representation so useful. Namely that we can represent really large numbers as well (although this implementation isn't really that great memory wise, with all those ints for each digit).

\$\endgroup\$

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.