How to create a root node in a linked list?

Go To StackoverFlow.com

1

I'm trying to learn linked-lists in Java and had some questions about the code below:

public class List {
    Node root;
    public List() {
        // constructor
    }

    public int pop() {
        // pop logic
    }

    public int push(int data) {
        // push logic
    }
}

I'd like to have a List class for popping and pushing data into the linked list. However, since the list won't have any default data on instantiation, what would be the best way for storing a reference to the root node?

In C, I would just have a pointer like:

Node * root;

But since Java does not have pointer, would having a simple declaration like:

Node root;

... be acceptable? I haven't used Java in a while, but doesn't allocating memory to an object declared as a class variable cause potential memory issues? Thanks!

2012-04-03 22:26
by Sam
Variables store values. For non-primitive types these values are (internally) "the reference" to the object, or null. I prefer to use the term "names", e.g. Node n1 = new Node(); Node n2 = n1; -> the new Node "is named by" n1 and n2 (it is the same Node object) as both variables will "evaluate to" the same object. This behavior similar to pointers in C/C++. For non-primitive types there is no implicit copy/duplicate/clone on an assignment (or when passing to a method); this differs from copy-constructors in C++ - NoName 2012-04-03 22:32


3

Yes, a simple declaration like Node root is acceptable. It is not actually a pointer, but a reference that can potentially refer to any Node.

References in Java are conceptually equivalent to C pointers, but are less flexible and use a simpler syntax.

2012-04-03 22:29
by paislee


1

Yes,

Node root;

Is acceptable. Every non-primitive object (including arrays of primitives or objects) in Java is actually a reference to an object, so it is like a C pointer in many ways.

It is actually so much like a pointer, that this declaration by itself isn't actually creating an object. It is a reference that is not pointing to anything yet, and if you try to use root before assigning it to a new Node() first, you will get a NullPointerException.

2012-04-03 22:29
by trutheality


1

Yes, Node root; is absolutely fine. Just make sure you don't change the value of root. For using it, create another variable, for traversing a path: Node start = root; This way root remains untouched.

I haven't used Java in a while, but doesn't allocating memory to an object declared as a class variable cause potential memory issues?

No it doesn't. While simply writing Node root; doesn't allocate any memory, root = new Node(); does. Take a note here that class members in java are static, the non-static members are global variables. Allocating memory to global variables in java is a common practice. For example, the variable where you actually store the list, will be a global variable, and you will have to allocate memory to it.

Java has a robust memory management system, so you won't run into memory issues too easily.

2012-04-03 22:47
by Rushil Paul