• Post Reply Bookmark Topic Watch Topic
  • New Topic

LinkedList exercise  RSS feed

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

I am working on this exercise but I don't understand it, Could somebody shed some light on this for me?
Thanks much.

Given the following definition of a node object, traverse a linked
list (given the head of the list and the data you are trying to find)
to determine whether the data is on the list. If the data is stored
in the list, return the node it is stored in, if data is not in the
list return null.

public class Node {
Object data;
Node next;
}

public Node traverseList(Node head, Object data){

}
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Standard exercise. You have to implement a method inside a Node<T> class. Parameterise the class: Node<T>; that will make things easier.
What you need to do to start with, is draw a diagram of a linked list, on paper. Use a soft pencil and an eraser. Preferably a large eraser. Then work out with the pencil how you are going to traverse the List. I think a recursive solution springs to mind first.
Once you have worked out how to traverse the List, you will probably find it easy to code.
 
Ranch Hand
Posts: 187
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Mitch Young
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Campbell and Gaurangkumar for your quick response.


I'm still very confused about what class Node does. Would it be fair to say it is like a Bean? with properties and getters and setters for those properties?

In class Node, does data needs to be some object say a String holding String data that I am searching for? Is next to hold the next element in the list.?

So instead of looping through a LinkedList of say type String or int which are the elements in the list this exercise has a list that contains elements of type Node?

In that case I could loop through the list testing each element(Node) for the value I am looking for then what is the purpose of a Node object holding another Node object.

Thanks again
 
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mitch Young wrote:
So instead of looping through a LinkedList of say type String or int which are the elements in the list this exercise has a list that contains elements of type Node?


The exercise is to create your own implementation of a LinkedList, not use the standard Java implementations. Having a Node class is a standard way to implement a linked list. If you connect multiple Node objects together, they will form a linked list. Connecting one Node to another Node is achieved by setting the "next" property of one Node object so that it references another Node object.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mitch Young wrote:Thanks Campbell and Gaurangkumar for your quick response.
You’re welcome We try to please, and sometimes succeed.
I'm still very confused about what class Node does. Would it be fair to say it is like a Bean? with properties and getters and setters for those properties?
No, it isn’t a bean, and doesn’t need lots of public properties. It records the value in the List, and the position of the next Node. You would only access setXXX methods via insertAfter or setValueAt calls on the whole List, or similar.
What you have is a singly‑linked list. A doubly‑linked list would have a reference to the previous Node, too
In class Node, does data needs to be some object say a String holding String data that I am searching for?
The Object (I would prefer a T, but generics is probably beyond the scope of the discussion just at the moment), as I said, the Object is accurately described as data. That is, the Object, whichever type, actually is the data which live in this particular node.
Is next to hold the next element in the list.?
Spot on. Yes
So instead of looping through a LinkedList of say type String or int which are the elements in the list this exercise has a list that contains elements of type Node?
In that case I could loop through the list testing each element(Node) for the value I am looking for then what is the purpose of a Node object holding another Node object.
Nearly. The nodes are the list. To loop through the list, you have to go from node to node.
Thanks again


You will find a diagram of a singly‑linked list here. That may make the explanation clearer for you.
 
Mitch Young
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Junilu,
I had no idea that this exercise was to create my own implementation of a linked list. I was asked to write this code on a white board in a job interview. Is this a standard interview exercise? In my study of Java I have never come across this exercise. It makes me wonder what other standard exercises I might encounter.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are lots and lots of things you can be asked at an interview. If you have seen how a linked list is constructed, you should be able to reconstruct it on a piece of paper.
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mitch Young wrote:Thanks Junilu,
I had no idea that this exercise was to create my own implementation of a linked list. I was asked to write this code on a white board in a job interview. Is this a standard interview exercise? In my study of Java I have never come across this exercise. It makes me wonder what other standard exercises I might encounter.

A linked list is a fairly common data structure. Granted, few people actually write there own anymore (at least in Java) as the standard API has implementations you can (and probably should) use.

However, my guess is that they weren't really expecting you to write actual code...they wanted to see how you think. Can you communicate ideas to other people? Do you get flustered when you have to present to a team? Can you read a spec, and start extrapolating to what the code should be? Do you know what questions to ask, do you make improper assumptions (are you even aware of what assumptions you are making), or do you just start BSing your way to an answer?

Yes, to a degree, they were seeing what you know, but in my experience, it's usually more a test of your other skills.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:The exercise is to create your own implementation of a LinkedList, not use the standard Java implementations...

Actually, I'm not at all sure it is.

From the sound of it, the question is: "How do you implement the traverseList() method using only the given information" (and, I suspect, assuming that it is in a class in the same package as Node) - and to do that you don't need to implement the Node class.

But feel free to shoot me down.

Winston
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mitch Young wrote:Thanks Junilu,
I had no idea that this exercise was to create my own implementation of a linked list.

Actually, to be more precise, the exercise was to traverse through a linked list that is implemented using the given Node class. This involves holding a reference to the Node that is at the "head" of the list, then iteratively moving to the nodes referenced by each "next" property. At any rate, Fred made some good points about what the interviewer might have been actually looking for besides knowledge about data structures.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
But feel free to shoot me down.

Can't ... draw ... my ... shooter ... you ... already ... got ... me!
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:Can't ... draw ... my ... shooter ... you ... already ... got ... me!

They don't call me 'Ýoung Winston' for nothin', hombre.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!