Making first object with a recursive class defination

Question

I was experimenting a bit in java and stumbled across this problem

Suppose i have a class with this recursive defination

public class Node<T> implements Iterable<T>{
    public final T element;
    public final Node<T> next;

    public Node(T head, Node<T> tail) {
        this.element = head;
        this.next = tail;
    }
// Contains few more methods and implementation of iteratable like add, remove etc
}

Now, the thing is I will be using this class as a field in another class with final keyword. Now if in the beginning i would be making an empty list and then add it to the list, how should i proceed.

TO make it simple

class NodeList <T>{
    private final Node<T> head;

    public NodeList(){
    }

    // Few more functions
}

Using NodeList class how can i create an empty list and later on add data using add function

Your problem can be reduced to: *how do I use `final` modifier in Java*? — Luiggi Mendoza, Aug 20 '14 at 14:50

Braj · Answer 1 · 2014-08-20T14:49:53.020

In java reference works as pointer to an object in memory that internally can point to another one in the same way.

Let's try to understand it visually:

What happens to the pointer head when the object obj is added to an empty linked list?

You have to remove final keyword from head because it's reference that changes every time when new node is added to point the new node.

In below snapshot head is a reference that point to first object in the memory and first object contains another reference next that points to second object and so on...

enter image description here

how should i proceed.

create a new node
point next of new node to next of head
point head to new node

Sample code:

class Node<T> {
    public final T element;
    public final Node<T> next;

    public Node(T head, Node<T> tail) {
        this.element = head;
        this.next = tail;
    }
}

class NodeList<T> {
    private Node<T> head;

    public void add(T value) {
        if (head != null) { 
            Node<T> node = new Node<T>(value, head); // create a new node 
            head = node;   // point `head` to new node 
        } else {
            // if head is null then assign it to head
            head = new Node<T>(value, null);
        }
    }
}

NodeList<String> nodeList = new NodeList<String>();
nodeList.add("First");
nodeList.add("Second");
nodeList.add("Third");

// print all nodes
Node<String> node = nodeList.head;
while (node != null) {
    System.out.println(node.element);
    node = node.next;
}

output:

Third
Second
First

That's pretty ok, but the thing is can i create the head node. Because i am using final keyword because of which i just cannot go away with a default constructor. I wish if i could just use default constructor like Node l = new Node(); and then i would add items using l.add("some random objects"); — Ayush choubey, Aug 20 '14 at 14:36
why are you using `final`? Just remove it. give me some time to share the code as well. — Braj, Aug 20 '14 at 14:39

score 0 · Accepted Answer · answered Aug 20 '14 at 14:30

0

You cannot do it with the final keyword on the head attribute, since it will force you to initialize it during the instanciation : you should then initalize it to null to represent the empty list and won't be able to append an element to it. Remove the final keyword, it has no use there.

I'm not even convinced of the use of final in your Node class. What if you want to add or remove an element in the middle of the list ? Using final there limits considerably the number of operations you can perform on your data structure.

answered Aug 20 '14 at 14:30

Dici

25,226
7
41
82

Well i wanted it to immutable. – Ayush choubey Aug 20 '14 at 14:38
I came across this two links for my reference and probably got lost http://programmers.stackexchange.com/questions/183766/how-to-increase-the-efficiency-of-an-immutable-queue-in-java (Answer number two) and http://stackoverflow.com/questions/10045446/efficient-implementation-of-immutable-double-linkedlist (Probably C#, idk) – Ayush choubey Aug 20 '14 at 14:40
You can make it immutable without using final. Typically, an immutable collection returns a copy of itself on which the operation was performed instead of performing it on the object itself. – Dici Aug 20 '14 at 14:41
@Ayushchoubey you could make it immutable but then your linkedlist could not add elements in the middle. In fact, your list could only add elements from the beginning, which will make it a fine implementation for a stack. – Luiggi Mendoza Aug 20 '14 at 14:47
@Ayushchoubey also, if you declare `final` in `NodeList#head` then you won't be able to add any element in the list outside the constructor. – Luiggi Mendoza Aug 20 '14 at 14:49
Ok, after reading the link above, its pretty clear that if i want to use final and want to make the list, then i can only do it at the time of instanciation using some parameterized constructor. @LuiggiMendoza : its alright, the question was out of curiosity if it can be done. Thanks – Ayush choubey Aug 20 '14 at 15:11
@Ayushchoubey well, now you know you can't. – Luiggi Mendoza Aug 20 '14 at 15:12

Making first object with a recursive class defination

2 Answers2