This week's book giveaway is in the JDBC and Relational Databases forum.
We're giving away four copies of Murach's MySQL and have Joel Murach on-line!
See this thread for details.
Win a copy of Murach's MySQL this week in the JDBC and Relational Databases forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

different ways to implement singly linked list

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
so I had a question on stackoverflow on 2 different ways to implement a linked list and I sort of got my answer, but I need reassurance.

When creating a linked list class why do some people make 'head' the start of the list, while others make 'head' the current node of the list. In other words, in the first case head will always be the first position in the list, and so when implementing methods you must traverse the list. In the second case, head will always be the last node entered, so if I have 10 nodes than head is the 10th node, and when you add to it, you dont have to traverse the list.

I am so confused on why there exists these 2 different ways and which one to use, mainly for interviews. I am on day 3 of watching linked list videos over and over again and every tutorial does it differently and it is throwing me off. Also why do some singly linked lists have a head AND tail while most only have a head. I am currently viewing like 10 different linked list and they are all different..
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Everything in computer science involves trade-offs. having a 'head' and a 'tail' involves (slightly) more memory, more complexity, and more maintenance, but gives you flexibility in how you use your list.

Having the head always point to the last element entered speeds up the insertion, but at the cost of not preserving the order - i.e. you now have a LIFO rather than a FIFO. That may be OK for some applications, but not for others.

Which to use always depends on the specific case where you will be needing it - there is no "THIS is ALWAYS the right way to do it" answer in CS, ever.
 
john hog
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks your use of FIFO and LIFO cleared things up
 
Marshal
Posts: 79006
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And welcome to the Ranch
 
john hog
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks, i just finished my implementation can anyone take a look and see if its missing anything? edge cases/etc. I am learning in prep for interviews so it must be presentable

 
Ranch Hand
Posts: 116
2
Eclipse IDE PHP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

john hog wrote: can anyone take a look and see if its missing anything? edge cases/etc. I am learning in prep for interviews so it must be presentable


A friend of mine got this same question and I am trying to work on it myself in case I get something similar during an interview.

How did this implementation turn out?

Thanks,
 
reply
    Bookmark Topic Watch Topic
  • New Topic