0

During an interview I was asked to implement some linked list methods in Java. I've only had experience implementing linked list in C++ and there were somethings that concerned me. After having read this question and seeing the answer, I still have concerns.

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    //Link constructor
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    //Print Link data
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

My first problem is Java doesn't have pointers. I'm used to seeing something like Node* nextNode; instead of public Link nextLink;. How can a value be assigned to Link without pointers? Is it because in Java new returns an actual Link object? Or does it return a reference to it? If it returns a reference to it isn't that a problem since a reference is different than an actual Link object? Or in Java is any object's identifier actually a reference?

I know this is a matter of opinion, but why is it that linked lists seem to occur more in C++? I guess the language doesn't have built in support so a lot of tutorials written about linked lists are geared towards C++ (even if the focus was on the data structure).

Community
  • 1
  • 1
Celeritas
  • 14,489
  • 36
  • 113
  • 194
  • In Java any object's identifier is actually a reference? I think that's the solution. – NoDataDumpNoContribution Apr 11 '14 at 07:54
  • Yes to the last sentence in your long paragraph. In Java, any object's identifier is a reference. – Dawood ibn Kareem Apr 11 '14 at 07:54
  • Java objects references are actually pointers, having the value required to find the objects.i.e. address – Keerthivasan Apr 11 '14 at 07:54
  • You know an object reference in `Java` is a pointer, or why do we get a `NullPointerException` when accessing a null reference :-) – Harmlezz Apr 11 '14 at 07:56
  • The language itself doesn't specify that a reference is a pointer, although it is so in every implementation that I've ever seen. – Dawood ibn Kareem Apr 11 '14 at 07:58
  • @Octopus so in a sense when they made Java they said "we're going to have pointers, but to hell with the '*' just forget it"? – Celeritas Apr 11 '14 at 07:59
  • @Celeritas Yeah, might be :) Leave it to the language designers! – Keerthivasan Apr 11 '14 at 08:01
  • No, they said "we're NOT going to have pointers". Then they misnamed one exception class. – Dawood ibn Kareem Apr 11 '14 at 08:06
  • In this question type as Java as a self written linked list, I have concerns that the interviewer has selected a valid question. It makes more sense to ask for a C++ or C linked list. In Java, asking pointed questions on the applicable Java Collection that satisfies performance characteristics of a linked list makes more sense. – CPlusPlus OOA and D Apr 11 '14 at 08:08
  • @DavidWallace so is pointer actually the name of a type of variable? Because in Java there are references, which are essentially the same thing as pointers (as they hold an address)? I mean you say there's no pointers in Java but `Link nextLink = new Link()` makes `Link` look an awful lot like a pointer to me... – Celeritas Apr 11 '14 at 08:16
  • 1
    All object types in Java are reference types. The references are usually implemented with pointers, but they don't have to be. Does that clarify things? – Dawood ibn Kareem Apr 11 '14 at 08:17
  • Yes. That's what I meant by the "to hell with the * just drop it" in the sense that all object types are reference types. When you say references are usually implemented with pointers, what do you mean? Do you mean the JVM is written using pointers? It's my understanding the only difference between the references and pointers is that references can't be null. – Celeritas Apr 11 '14 at 08:24
  • possible duplicate of [Is Java "pass-by-reference"?](http://stackoverflow.com/questions/40480/is-java-pass-by-reference) – Bernhard Barker Apr 11 '14 at 09:32

4 Answers4

1

It's cause java manipulates objects with their references. It's well known that java is pass by value, however the value of the objects is their addresses.

Mohsen Kamrani
  • 7,177
  • 5
  • 42
  • 66
  • So in C++ if you had just `Node nextNode;` instead of `Node* nextNode` everything would be much less efficient because copies are being passed, not pointers? – Celeritas Apr 11 '14 at 08:01
  • about that: is there a way around this? where i'm able to do something like foo(bar a){ a = new bar()} and a is changed outside the scope of bar too? because not being able to do this at all just seems like such a huge pain in the ass that I feel like there must be some way to do this – user2520938 Apr 11 '14 at 08:04
  • @Celeritas- I don't really remember the case in C++, however I think your answer is [here](http://stackoverflow.com/questions/15186196/linked-list-in-c-using-references-instead-of-pointers). – Mohsen Kamrani Apr 11 '14 at 08:07
  • @user2520938> What do you mean by this :" a is changed outside the scope of bar too"? Do you mean `foo`? – Mohsen Kamrani Apr 11 '14 at 08:10
  • @mok yea thats what i mean:p – user2520938 Apr 11 '14 at 08:12
  • @Celeritas I am not sure how exactly you could manage to have a linked list with a unique Node instance at each node, without using a pointer to the next node. How will all the nodes link together in this case? How would a traversal be implemented? In mok's link to using C++ references, the approved answer has pointers and references used together. – CPlusPlus OOA and D Apr 11 '14 at 08:15
  • @CPlusPlusOOAandD "How will all the nodes link together in this case? How would a traversal be implemented?" this is why I'm confused because why can't you say the same about Java? – Celeritas Apr 11 '14 at 08:18
  • @user2520938> So I should say yes, this approach that java uses sometimes makes real difficulties. – Mohsen Kamrani Apr 11 '14 at 08:20
  • Absolutely. Purposely making every single instance a reference, except a String object, does cause confusing thoughts when comparing to other languages. – CPlusPlus OOA and D Apr 11 '14 at 09:26
  • 1
    @Celeritas Probably the best way to find resolution to Java not having pointers is to look at your favorite edition of the Java: The Complete Reference series. Mine is the eighth edition, whereas here is the link to the ninth edition by Herbert Schildt: [Java The Complete Reference 9/E \[Paperback\]](http://www.amazon.com/Java-Complete-Reference-Herbert-Schildt/dp/0071808558). Pages 59 and 113 of the eight edition compares C/C++ pointers to Java references (not the same as declaring a Java instance that is assigned to the result of calling Java new on that object). – CPlusPlus OOA and D Apr 11 '14 at 09:32
  • @Celeritas Regarding C++, there are options to have direct access to pointer manipulation as either a pointer by reference or pointer by value. You can also have an object instance as a value or reference. Regarding C++ linked lists and other data structures using pointers, both C and C++ make it very easy to have an internal pointer (a local instance inside a class or struct) that is technically a variable to store a memory address. The pointer then can be assigned to any memory location, which is intentionally not supported by Java to prevent coding errors. – CPlusPlus OOA and D Apr 11 '14 at 09:43
0

Java has its own LinkedList Class, if thats what you are asking for

check here:

http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Haris Mehmood
  • 854
  • 4
  • 15
  • 26
0

In java, the objects are manipulated by their references, and a reference is similar to the pointer in C++, except that you won't be able to actually manipulate the addresses directly as you do in C++.

In java, when you use an Object, you use its reference, and hence the Link in your code is just a reference to the next Node object in the list.

anirudh
  • 4,116
  • 2
  • 20
  • 35
0

The object references in java are just as good as pointers, the noticeable difference is that you cannot do pointer arithmetic here. MyClass myRef;in java just means a reference that will be pointing to some object. when you do MyClass myRef = new MyClass(); an object and created and its reference is stored in myRef. You should realize the difference between objects in memory and their reference in myRef. It is pretty much same as what we do in C/C++.

Yogesh
  • 565
  • 3
  • 21