Win a copy of Microservices in Action this week in the Web Services 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

linked list pointers?  RSS feed

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
why we need current pointer in linklist to traverse

<<<<<<<<<<<<<<(why cant i just use head to find tail of link list here>>>>>>> ??)>>>>>>>>>>>>>
like this......



please help learning  coding and Data Structure and algorithm...

 
author & internet detective
Posts: 38925
686
Eclipse IDE Java VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Himanshu,
Welcome to CodeRanch!

With pointers, it helps to dra on paper. Draw a box for each node and an arrow for each pointer. Try to traverse the list by going form arrow to arrow.
 
Rancher
Posts: 3352
33
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

why cant i just use head to find tail of link list here


It is a local variable so your idea should work.
Did you try it?  What happened?

Note: The ending code tag wasn't positioned after all the code that was to be wrapped.  Select all the code to be wrapped before clicking on the Code button.
Also use Preview before hitting the Submit button to be sure the code is properly wrapped.
 
Sheriff
Posts: 12749
211
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
head is a marker. It should always point at the current head of the list. If you use it as a cursor to point to the current element you're working with, then how are you going to get back to the actual head of the list?  That's why you need the current variable to point to the element you're currently working with.
 
Norm Radder
Rancher
Posts: 3352
33
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

In this method, head is a local variable.  Changing its value won't change the variable/value that was passed to the method.
 
Junilu Lacar
Sheriff
Posts: 12749
211
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry, didn't read the code thoroughly. I haven't tried your code but Norm is right, your idea should work. I still would use a current local variable though and keep head final. Anyone familiar with the terms head, tail, and current would not normally expect the value of head to be used as a cursor and if you write code that does, people reading your program are likely to think it's wrong at first glance, just like I did.
 
Marshal
Posts: 61805
193
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why have you got that method static? The object‑oriented way to do things would be to make that an instance method of a particular List. If you follow Jeanne's suggestion, you will be able to see why you need a reference to the current node.

Welcome to the Ranch Thank you for using the code button, but you should have put the [/code] part after the rest of the code. Don't worry; I can correct that for you.
 
Norm Radder
Rancher
Posts: 3352
33
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A problem might be with what the calling code does with the returned value.
In the first code, the value in head will be what was passed. Except for  a null value.
In the second code, head will point to the added node.
 
Master Rancher
Posts: 3010
105
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Norm Radder wrote:
In the second code, head will point to the added node.


No, it should return head.next, since that is the last Node added.
 
Junilu Lacar
Sheriff
Posts: 12749
211
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I carefully re-read through both versions of the code OP posted and realized that the second version is NOT equivalent to the first version so no, OP's proposal to use head as the cursor variable will in fact NOT work if you need to keep the same behavior as the first version.

The first version always returns the head node of the linked list.  The second version proposed by OP list correctly returns a reference to the head node only when the list was previously empty. If the list already has elements in it, the returned value is the tail node of the list before the new node is added, which is a pretty useless value to return.

At any rate, neither version is very crisp on the semantics, so the code is confusing to read which is makes it more difficult for someone reading it to determine at first glance whether it is correct.

Since a node actually wraps the data that is passed to the insertAtEnd() method, it would make more sense to me that the method would return a reference to the new node. Also, insertAtEnd is a bit grammatically off.  "Insert" usually means to put between two things.  The word "add" seems to convey the intent better and the grammatical correctness is maintained if you decide to extend the API by adding addBefore(Node, data) and addAfter(Node, data) methods.

Here's a cleaner version:

@OP, see if you can figure out how to write the addBefore(Node, int) and addAfter(Node, int) methods.
 
Piet Souris
Master Rancher
Posts: 3010
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Junilu

I had no trouble understanding OP's second verson, it just returned the latest Node.

Now, your reasoning makes sense, it is about what I had in mind too. What puzzles me is that while OP just described a method, without mentioning the context, you devise a complete context. Can you elaborate why?
 
Junilu Lacar
Sheriff
Posts: 12749
211
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet

Several reasons for devising a complete context:

1. Andy Hunt's Rule #1: Always consider context

2. OP's second version actually returned head, which you correctly pointed out was wrong. It should have returned head.next if the intent was to return a reference to the new Node that was added to the list.

The semantics of the implementation code are poor and potentially confusing/misleading. The name head does not match the intent of returning the new Node. The mismatch between what the code says (return head) and its intent imposes more cognitive load for the reader.

3. OP suggested that his second version works the same as the first version. This is not true since the first version always returns the head node, which is NOT what his second version actually (erroneously) does or seems to be intended to do (see #2)

4. As Campbell pointed out, these methods are defined as static/class methods when they probably should be instance methods of a SinglyLinkedList class. So, I wrote code that was more OO.

5. I always think about the code that you're going to have to write because of the way the API is designed. By focusing only on the code that OP provided, we lose sight of the bigger picture, which includes the code that would use these methods under consideration. Per #4, I would probably want to avoid using the static methods so I provided code that would be used in a more OO way.  Which brings us back to #1.

Hope this gives you more context

 
Piet Souris
Master Rancher
Posts: 3010
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It always strikes me that you are giving much more context than I use to do. Therefore I was curious about your though-processes, where we all learn much from. That's why I asked, and indeed, your response makes perfect sense. Really appreciate it, have a cow from me as well!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!