Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

LinkedList Implementation  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, everyone

I have recently started with data structures and I have completed the Stack implementation on Array. I found it quite useless to implement stack concepts on an existing Data Structure that could be manipulated in much simpler way. So, I wanted to learn the real thing, so I started off with Linked Lists. I came across this site, http://www.newthinktank.com/2013/03/linked-list-in-java/ which explained the basics of a singly Linked List. But the code has been confusing ever since I visited this website. While trying to make myself understand the code, I came across this weird happening in the program.

The node creation class


The LinkedList class sequencing the nodes


The problem is with this statement in the LinkedList class to which comment has been added as well, System.out.println("Next Link: " + theLink.next);, here next variable is of Link type, and when printed it always prints the bookName variable. There lies my confusion ,why so? Why not print the value in the millionsSold variable? I might have made a silly question, or it may be that my concepts are not clear, but what ever be the case, I'm very much confused. Any help will be appreciated. Thanks in advance.

Regards,
Ranajoy Saha
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What does the toString method of the node class return? If it simply returns the book name, you will get the book name printed.

That webstie has got some very bad habits. Public fields is one. Top‑level classes is another. The class should not be called link but Node. It should have private fields throughout, like any other class. It should probably be a private inner class in the list class. It should not have two fields but two (for a singly inked list): the value and the next node. A doubly linked list would have a previous field too.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay. So, am I following a wrong code here? I've only started data structures a couple of days back and his video on about Linked List was the only one I found I could comprehend. What should I do now? Are there any LinkedList tutorials that I could follow?
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:Are there any LinkedList tutorials that I could follow?

Well, I've always found the Wikipedia page quite useful because it contains lots of diagrams. One of the problems with linked lists is trying to "visualise" them, and in that case a picture is worth a thousand words (for me at least).

It also explains the different choices you have for storage. For example, I have a single-linked implementation called 'Ring' that I use all the time, which is a circular linked list with a sentinel node, which has a few advantages:
1. You don't have to worry about nulls because the list always has at least one Node in it.
2. To get a "previous" Node in a forward-linked list, you go forward n times, where n is the number of real Nodes in the list (I'll let you work out why). Maybe not the most efficient, but extremely simple.

And don't worry. Other than the stuff Campbell pointed out, you're pretty close.

HIH

Winston
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But could someone please explain how this statement works, "System.out.println("Next Link: " + theLink.next);", I'm still unable to figure out how this corresponds to the OUTPUT this program provides.

OUTPUT:

Harry Potter and the Sorcerer's Stone: 107,000,000 Sold
Next Link: The Lord of the Rings

The Lord of the Rings: 150,000,000 Sold
Next Link: A Tale of Two Cities

A Tale of Two Cities: 200,000,000 Sold
Next Link: Don Quixote

Don Quixote: 500,000,000 Sold
Next Link: null
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:But could someone please explain how this statement works, "System.out.println("Next Link: " + theLink.next);", I'm still unable to figure out how this corresponds to the OUTPUT this program provides.

Campbell already suggested why in the first line of his post.

Question: Forget about linked lists for moment. What does the expression
  "Some text " + anObject
return?

Explain it to us in detail, and then go back and look at the line that's causing you problems.

If you still have problems come back and we'll give you more hints, but you'll be MUCH happier if you work it out for yourself.

Winston
 
J. Kevin Robbins
Bartender
Posts: 1801
28
Chrome Eclipse IDE Firefox Browser jQuery Linux MySQL Database Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:For example, I have a single-linked implementation called 'Ring' that I use all the time, which is a circular linked list with a sentinel node, which has a few advantages:

Excuse me for hijacking this thread. I can split this off if needed. But I'm curious what you use this class for "all the time". I've never even had the need to use a Linked List so I'm at a loss to understand what this Ring class is for.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
J. Kevin Robbins wrote:Excuse me for hijacking this thread. I can split this off if needed. But I'm curious what you use this class for "all the time". I've never even had the need to use a Linked List so I'm at a loss to understand what this Ring class is for.

Linked lists are great when you don't know how many elements you're going to create, which is often the case with a Stack or a Queue - you don't know how many elements are going to be pushed into it before you start popping elements off - from either end. It only takes as much space as is needed; albeit that each element takes up a bit more space. If I used an array (or an ArrayList), I'd have to "guesstimate" how much space I need and then re-allocate if I run out of room.

And if you're interested in a concrete example: HashMap uses a single-linked list for it's "buckets" internally, because it's pretty much a perfect fit: The class has no idea how many items will be put in any particular bucket, and linked lists provide O(1) insertion and deletion from one end - and in the case of a ring with a sentinel, from both ends (you either add after the sentinel, or you replace the sentinel with a value and add a new one).

Hope it explains it for you.

Winston
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
J. Kevin Robbins wrote:I've never even had the need to use a Linked List so I'm at a loss to understand what this Ring class is for.

Another thing: Adding an element (or a bunch of elements) in the middle of a linked list is also an O(1) operation; and that's definitely not the case for an array, because you first have to shift things (and possibly increase the capacity) to "make room" for what you're adding.

However, in order to do that for a LinkedList, you first have to locate the point where you want to insert and that is an O(n) operation.

An Iterator that is already positioned at that point, however, can do it very quickly. Indeed, it's a big failing of the ListIterator class IMO (among many) that it doesn't have an add(Collection) method, which is why my Ring.Iterator class has one.
(sheesh, do I sound smug, or what? )

Winston
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, this was the code snippet I wrote to test out what "Some text" + object returns



OUTPUT:

I love you Practice@659e0bfd

So, the line "System.out.println("I love you " + obj);" prints the String "I love you" followed by the Class name to which this object belongs and this value "659e0bfd" should most probably be the address of that object. (I did not say the address of the class because, sometime back in Class 9, I learnt in a book that, Classes are blueprints which do not have a physical existence in memory while the instances that contain all the methods,variables, etc occupy memory). But I still don't know what I am getting at. And even if I remove the line "static int aValue = 10;" the output remains unaffected. Winston Gutkowski, please see if my answer is correct or not. I really need to understand why that happens.

EDIT:

This is my new code



OUTPUT:

I love you darling!

That @Override was not added by me, I use NetBeans IDE, the IDE was giving me an Warning "Add @Override Annotation", so I added it, but I do not understand the use of it. By the name, toString(), I remember of a method in ArrayList class in the util package. When ever I used to create an instance of ArrayList class and wrote the statement System.out.println(someList.toString());, it used to print [1,2,3...] some what in this format. But, how the does the compiler know, that when I'm calling the objName.ClassType, it must call the toString() method?

Regards,
Ranajoy Saha
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Practice@659e0bfd" is the output of the toString() method of the Object class, which is the superclass of all classes. In order the get your own toString() method, you need to override Object's. Try this and post your code.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:"Practice@659e0bfd" is the output of the toString() method of the Object class, which is the superclass of all classes. In order the get your own toString() method, you need to override Object's. Try this and post your code.


Yes, I did that. Thank you very much, now I understand why that was happening!
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That @Override was not added by me, I use NetBeans IDE, the IDE was giving me an Warning "Add @Override Annotation", so I added it, but I do not understand the use of it

That annotation is used to state your intention to override a method. It's easy to overload a method instead of override it, so the compiler (and most IDEs) will complain if you do the wrong thing.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But, how the does the compiler know, that when I'm calling the objName.ClassType, it must call the toString() method?

When calling System.out.println(), the method will use the toString() method to convert the object into a string representation first. Not all methods do this, though.
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm sorry if it seems I'm in your hair a lot today, Winston. It just means I enjoy your posts ;)

Winston Gutkowski wrote:Linked lists are great when you don't know how many elements you're going to create, which is often the case with a Stack or a Queue - you don't know how many elements are going to be pushed into it before you start popping elements off - from either end. It only takes as much space as is needed; albeit that each element takes up a bit more space. If I used an array (or an ArrayList), I'd have to "guesstimate" how much space I need and then re-allocate if I run out of room.

I've never really had much problems with just using ArrayList and ArrayDeque. If I know the amount of items I will add, then I will instantiate them with the correct capacity, otherwise it's no big deal. Usually I have no cause for more optimization.

linked lists provide O(1) insertion and deletion from one end - and in the case of a ring with a sentinel, from both ends (you either add after the sentinel, or you replace the sentinel with a value and add a new one).

If memory serves, LinkedList is doubly linked, and has constant time for getting the last element. Also, ArrayList has amortized constant time for addition, and in practice is usually faster than LinkedList with most operations.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you very much Knute Snortum,Winston Gutkowski and Campbell Ritchie for helping me clear out my basic concepts. I was not aware of this before the the System.out.println() calls the toString() method to convert the objects into a String representation and then gives the output, guess you learn new things each day.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:But, how the does the compiler know, that when I'm calling the objName.ClassType, it must call the toString() method?

Erm, because that's what it does when it sees a '+' in a String context.

And VERY WELL DONE. You worked it out for yourself. Give yourself a gold star! In fact...have a Cow, because that's what we like to see.

That @Override was not added by me, I use NetBeans IDE, the IDE was giving me an Warning "Add @Override Annotation", so I added it, but I do not understand the use of it.

It's used to indicate that the method you're defining overrides one at a higher level, and it tells the compiler to check that that is, in fact what it does.

The most obvious example is equals(), whose signature is:
  public boolean equals(Object obj) { ...

Look simple, right? But lots of beginners (and me too, when I'm not thinking ) will define it as:
  public boolean equals(MyClass obj) { ...
which is incorrect.

@Override ensures that that will NOT COMPILE.

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:If memory serves, LinkedList is doubly linked, and has constant time for getting the last element. Also, ArrayList has amortized constant time for addition, and in practice is usually faster than LinkedList with most operations.

Yes, but I've taken this thread to be about "linked lists" in general, not LinkedList. And amortized time is a generalization. If I have an ArrayList created with new ArrayList(), I'd be quite surprised if can call add() fifty times in any less time than a LinkedList created the same way.

And my posts were about single-linked lists (which was the example given), which are simpler (?), faster, more space-efficient and much easier to make Thread-safe.

So there.

Winston
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:and much easier to make Thread-safe.

Correction: what I meant to say was "concurrent". A single-linked List does not have to lock the entire structure in order to support concurrent update operations. This is also true of a doubly-linked list, but the mechanism is much more complex.

Winston
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!