aspose file tools*
The moose likes Beginning Java and the fly likes Linkedlist get middle algorithms Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Linkedlist get middle algorithms" Watch "Linkedlist get middle algorithms" New topic
Author

Linkedlist get middle algorithms

Adeola Omonira
Greenhorn

Joined: Jan 14, 2013
Posts: 1
Good afternoon!

I have an interview in a few days and they're asking me to find a get middle algorithm to mylinkedlist class, I'm completely confused on how to do and this job will be the start of my career since I graduated last year, your help will be appreciated, thanks!


Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2854
    
  11

Hi Adeola, and welcome to Java Ranch!

First, a couple of hints for your interview: always capitalize class names, never capitalize method names, and a LinkedList class is going to be more useful if you make it public. Little things like that convince interviewers that you know what you're doing.

I think keeping the current size of the linked list in your class would make finding the middle element easier. You could always find this size by walking through the list, but it would just be nicer to have it all ready. You'd also have to decide if you want retrieval of the element to take linear, aka O(n), time, or if you need it to be constant, aka O(1), time and are willing to pay a price as nodes are added or removed. That's as much of a hint as I'm willing to give for something that's meant as a test of your skill!

Good luck!
harshvardhan ojha
Ranch Hand

Joined: Jul 26, 2007
Posts: 157
    
    1

Thanks greg for the explanation, here if Adeola will keep count then he needs to retrive only n/2 elements from head or else all next in an array, where he can get in O(1)?
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

Greg Charles wrote:First, a couple of hints for your interview: always capitalize class names, never capitalize method names, and a LinkedList class is going to be more useful if you make it public. Little things like that convince interviewers that you know what you're doing.

Also pay attention to the fact that Java is case sensitive. So Class MyLinkedList is different from class MyLinkedList; in fact, the first one (that you wrote) is wrong.
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2854
    
  11

harshvardhan ojha wrote:Thanks greg for the explanation, here if Adeola will keep count then he needs to retrive only n/2 elements from head or else all next in an array, where he can get in O(1)?


Good question! If adding nodes can only be done at the tail, then enhancing the add to move the middle element to "middle.nextElement" every other time would allow you to retrieve the middle element in constant time, while keeping the add also constant. If you allow for adds at random positions, then the add would probably become O(n), but the retrieve of the middle could remain constant. Then it becomes a question of which operation you want to optimize for.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Linkedlist get middle algorithms