Win a copy of Soft Skills: The software developer's life manual this week in the Jobs Discussion forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Linkedlist get middle algorithms

 
Adeola Omonira
Greenhorn
Posts: 1
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2984
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 157
1
Android Java MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 825
5
Java Python Ruby
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2984
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Don't get me started about those stupid light bulbs.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic