Print out and sort values inside LinkedList

Question

I wrote a recursive backtracking algorithm for the so-called "Coin Change Problem". I store the coin values (int) in a self-written LinkedList ("ll") and each of those LinkedLists is stored inside one master LinkedList ("ll_total"). Now, when I try to print out the LinkedLists inside the master LinkedList, all I get is "LinkedList@1e88b3c". Can somebody tell me how to modify the code, in order to print out the coin values properly?

I would also like the algorithm to chose the LinkedList with the least values stored inside, as it would represent the optimal coin combination for the "coin change problem".

import java.util.Scanner;

public class CoinChange_Backtracking {
        
    static int[] coins = {3, 2, 1};
    static int index_coins = 0;
    static int counter = 0;
    static LinkedList ll = new LinkedList();
    static LinkedList ll_total = new LinkedList();
    
    
    public static void main(String[] args) {
        Scanner myInput = new Scanner(System.in);
        int amount;
        System.out.println("Put in the amount of money: ");
        amount = myInput.nextInt();
        if (amount < 101) {
            //Start recursion and display result.
            recursiveFunction(coins, amount, index_coins, ll);
            ll_total.show_ll();
        } else {
            System.out.println("The value must be less than 100!");
        }
    }

    
    public static LinkedList recursiveFunction(int[] coins, int amount, int index_coins, LinkedList ll) {
        //The current coin is being omitted. (If index_coins + 1 is still within range.)
        if ((index_coins + 1) < coins.length) {
            ll = recursiveFunction(coins, amount, index_coins + 1, ll);
            ll_total.insert_ll(ll);
            for (int i = 0; i < counter; i++) {
                ll.deleteAt(0);
            }
            counter = 0;
        }
        
        //The current coin is not being omitted. (If there is still some change left and value of change isn't lower than value of current coin.)
        if (amount != 0) {
            if (amount >= coins[index_coins]) {
                ll.insert(coins[index_coins]);
                counter++;
                ll = recursiveFunction(coins, amount - coins[index_coins], index_coins, ll);
            }
        }
        return ll;
    }
}

public class LinkedList {
    Node head;
    
    public void insert(int data) {
        Node node = new Node();
        node.data = data;
        node.next = null;
        if (head == null) {
            head = node;
        } else {
            Node n = head;
            while(n.next != null) {
                n = n.next;
            }
            n.next = node;
        }
    }
    
    public void insert_ll(LinkedList ll) {
        Node node = new Node();
        node.ll = ll;
        node.next = null;
        if (head == null) {
            head = node;
        } else {
            Node n = head;
            while(n.next != null) {
                n = n.next;
            }
            n.next = node;
        }
    }
    
    public void deleteAt(int index) {
        if(index == 0) {
            head = head.next;
        } else {
            Node n = head;
            Node n1 = null;
            for (int i = 0; i < index - 1; i++) {
                n = n.next;
            }
            n1 = n.next;
            n.next = n1.next;
            n1 = null;
        }
    }
    
    public void show() {
        Node node = head;
        while(node.next != null) {
            System.out.println(node.data);
            node = node.next;
        }
        System.out.println(node.data);
    }
    
    public void show_ll() {
        Node node = head;
        while(node.next != null) {
            System.out.println(node.ll);
            node = node.next;
        }
        System.out.println(node.ll);
    }
    
    //A toString method I tried to implement. Causes an array error.
    /*
    public String toString() {
        Node n = head.next;
        String temp = "";
        while (n != null) {
            temp = temp + n.data + " ";
            n = n.next;
        }
        return temp;
    }
    */
}

public class Node {
    int data;
    LinkedList ll;
    Node next;
}

Answer 1

To answer your question. You are printing the linked list object, see here System.out.println(node.ll);

There are several ways to do it right. One approach is to question why you use Node and LinkedList the way you do ? A node can have a linked list and a linked list can have a node, I believe this is not really what you wanted. Maybe you can make it work, but from a design point of view in my experience it is not good. I find it confusing and it's a great source of bugs.

I try to list some points that caught my eye (or that my IDE had caught for my eyes).

• You are not closing the Scanner object. Just close it at the end of the program or use the try-with-resources.
• As mentioned before you have linked list that has a node and a node that has a linked list. You are not using that correctly in your program. I recommend to review that approach. It is error prone.
• Also simply use the LinkedList of the Java library unless you have a good reason not to. It works fine and offers all you need.
• You use many static, global (within the scope of the package) variables. In this case I think you can avoid that. coins does not need to be given as a parameter every time. It should be an immutable object. It is not supposed to change.
• ...

And I am not sure if it is a backtracking algorithm. It is certainly tree recursive. This just as a side note.

I'd like to propose a solution that looks similar to yours. I'd probably do it differently my way, but then it probably takes time to understand it. I try to adopt your style, which I hope helps. I simplified the program.

In order to print the result, simply write a helper function.
The linked list is an object. You have to make a copy of the list every time you call the recursion in order to work on a dedicated object. Otherwise you modify the same object while recursing different paths.
You can simply use a list of lists. A global list of lists (within package scope), and a list of which you make a copy every time you recurse. When you reach a good base case you add it to the global list. Otherwise just ignore.

import java.util.LinkedList;
import java.util.Scanner;

public class CoinChangeBacktracking {

  static final int[] COINS = {3, 2, 1};
  static final LinkedList<LinkedList<Integer>> changes = new LinkedList<>();

  public static void main(String[] args) {

    Scanner myInput = new Scanner(System.in);
    int amount;
    System.out.println("Put in the amount of money: ");
    amount = myInput.nextInt();
    if (amount < 101) {
      // Start recursion and display result.
      recursiveFunction(amount, 0, new LinkedList<>());
      print(changes);
    } else {
      System.out.println("The value must be less than 100!");
    }
    myInput.close();
  }

  static void recursiveFunction(int amount, int index,
                                LinkedList<Integer> list) {

    // exact change, so add it to the solution
    if (amount == 0) {
      changes.add(list);
      return;
    }

    // no exact change possible
    if (amount < 0 || index >= COINS.length) {
      return;
    }

    // explore change of amount without current coin
    recursiveFunction(amount, index + 1, new LinkedList<>(list));

    // consider current coin for change and keep exploring
    list.add(COINS[index]);
    recursiveFunction(amount - COINS[index], index, new LinkedList<>(list));
  }

  static void print(LinkedList<LinkedList<Integer>> ll) {
    for (LinkedList<Integer> list : ll) {
      for (Integer n : list) {
        System.out.print(n + ", ");
      }
      System.out.println();
    }
  }
}