Last week, we had the author of TDD for a Shopping Website LiveProject. Friday at 11am Ranch time, Steven Solomon will be hosting a live TDD session just for us. See for the agenda and registration link
  • 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
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

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: 13050
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: 75702
354
  • 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,
 
It means our mission is in jeapordy! Quick, read this tiny ad!
free, earth-friendly heat - a kickstarter for putting coin in your pocket while saving the earth
https://coderanch.com/t/751654/free-earth-friendly-heat-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic