• Post Reply Bookmark Topic Watch Topic
  • New Topic

LLink implementation of a list interface -- i don't even understand the question  RSS feed

 
Greenhorn
Posts: 10
Chrome Eclipse IDE Mac
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sigh. So we have an assignment regarding a linked list implementation of a given list interface. I don't know if I can even ASK this question coherently, because I don't totally understand what I'm supposed to do. Maybe someone can help me understand.

In my list interface, the method contains(T anEntry) is defined.
In the LList implementation, contains is already implemented as part of getting the core methods in.

Now I am being tasked with the following:
Provide a second implementation of the method contains2(T anEntry) that calls a private recursive method
private boolean contains(T anEntry, Node startNode) that returns whether the list that starts at startNode contains the entry anEntry.

I've written the private recursive method already. That's not an issue (at least not right now).

But what I don't understand is how startNode is supposed to be populated when this private contains method is called from the public contains2 method? contains2 only takes one parameter: anEntry. the private method takes two parameters: anEntry and startNode. How am i supposed to provide startNode when I am calling contains2?
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Often in a linked list, you have a permanent reference to the startNode - at least we did in the implementations I wrote. Otherwise, how would you find it?
 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brenda Fire,

Even i am facing same problem for assignment, really i dont undersand.

Provide a second implementation of the method contains2(T anEntry) that calls

a private recursive method

Please explain me if you have time

sarayu

 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
brenda flire wrote:But what I don't understand is how startNode is supposed to be populated when this private contains method is called from the public contains2 method?

As Fred says, there will probably already be one in your LList class. In Java's own LinkedList I believe it's called 'header'; in other implementations, I've also seen it called an "anchor". Other possibilities: 'first[Node]', 'top', 'front' ...

HIH

Winston
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With all due respect to both Fred and Winston, i see this implementation a little different.

But with the above said, if my interruption is correct, this problem is very badly worded and worst yet badly thought out…..

Ok, classically when one implements a linked list,they are implemented as circular double linked lists - that is done so that the four normal edge boundaries are eliminated. That said, classically there was always three pointers that we managed: head, tail and current.

What i think this is asking for is set the current pointer to the given node, then find if the entity is in the sub list starting at node.

Now that said - i have written a few hundred linked list implementations in many languages, but i have never had a recursive function/method in a list implementation.

Anyway, i may be total wrong, but i wanted to give a different spin on this.

-steve
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!