Linked List in Java
In this video, I’ll cover how work with a linked list in java. I’ll show you how they work in 4 different ways.
We’ll cover how to create them, what a link is, how to add and delete links, how to search through them and a whole bunch more. The basics you need to understand at the end are that: 1) A Link is an Object 2) Each Link has a reference to another Link in the List 3) The LinkedList has only a reference to the last Link added to it.
If you like videos like this, it helps to tell Google+
Code From the Video
Link.java
public class Link {
// Set to public so getters & setters aren't needed
public String bookName;
public int millionsSold;
// Reference to next link made in the LinkList
// Holds the reference to the Link that was created before it
// Set to null until it is connected to other links
public Link next;
public Link(String bookName, int millionsSold){
this.bookName = bookName;
this.millionsSold = millionsSold;
}
public void display(){
System.out.println(bookName + ": " + millionsSold + ",000,000 Sold");
}
public String toString(){
return bookName;
}
public static void main(String[] args) {
LinkList theLinkedList = new LinkList();
// Insert Link and add a reference to the book Link added just prior
// to the field next
theLinkedList.insertFirstLink("Don Quixote", 500);
theLinkedList.insertFirstLink("A Tale of Two Cities", 200);
theLinkedList.insertFirstLink("The Lord of the Rings", 150);
theLinkedList.insertFirstLink("Harry Potter and the Sorcerer's Stone", 107);
theLinkedList.display();
System.out.println("Value of first in LinkedList " + theLinkedList.firstLink + "\n");
// Removes the last Link entered
theLinkedList.removeFirst();
theLinkedList.display();
System.out.println(theLinkedList.find("The Lord of the Rings").bookName + " Was Found");
theLinkedList.removeLink("A Tale of Two Cities");
System.out.println("\nA Tale of Two Cities Removed\n");
theLinkedList.display();
}
}
LinkList.java
class LinkList{
// Reference to first Link in list
// The last Link added to the LinkedList
public Link firstLink;
LinkList(){
// Here to show the first Link always starts as null
firstLink = null;
}
// Returns true if LinkList is empty
public boolean isEmpty(){
return(firstLink == null);
}
public void insertFirstLink(String bookName, int millionsSold){
Link newLink = new Link(bookName, millionsSold);
// Connects the firstLink field to the new Link
newLink.next = firstLink;
firstLink = newLink;
}
public Link removeFirst(){
Link linkReference = firstLink;
if(!isEmpty()){
// Removes the Link from the List
firstLink = firstLink.next;
} else {
System.out.println("Empty LinkedList");
}
return linkReference;
}
public void display(){
Link theLink = firstLink;
// Start at the reference stored in firstLink and
// keep getting the references stored in next for
// every Link until next returns null
while(theLink != null){
theLink.display();
System.out.println("Next Link: " + theLink.next);
theLink = theLink.next;
System.out.println();
}
}
public Link find(String bookName){
Link theLink = firstLink;
if(!isEmpty()){
while(theLink.bookName != bookName){
// Checks if at the end of the LinkedList
if(theLink.next == null){
// Got to the end of the Links in LinkedList
// without finding a match
return null;
} else {
// Found a matching Link in the LinkedList
theLink = theLink.next;
}
}
} else {
System.out.println("Empty LinkedList");
}
return theLink;
}
public Link removeLink(String bookName){
Link currentLink = firstLink;
Link previousLink = firstLink;
// Keep searching as long as a match isn't made
while(currentLink.bookName != bookName){
// Check if at the last Link in the LinkedList
if(currentLink.next == null){
// bookName not found so leave the method
return null;
} else {
// We checked here so let's look in the
// next Link on the list
previousLink = currentLink;
currentLink = currentLink.next;
}
}
if(currentLink == firstLink){
// If you are here that means there was a match
// in the reference stored in firstLink in the
// LinkedList so just assign next to firstLink
firstLink = firstLink.next;
} else {
// If you are here there was a match in a Link other
// than the firstLink. Assign the value of next for
// the Link you want to delete to the Link that's
// next previously pointed to the reference to remove
System.out.println("FOUND A MATCH");
System.out.println("currentLink: " + currentLink);
System.out.println("firstLink: " + firstLink);
previousLink.next = currentLink.next;
}
return currentLink;
}
}
Hi darek nice video as always.
also i am curious to know, if you have any idea about how to generate 3d data for performance testing, any tool for that, or how to automate it?
Thanks,
Punit
Do you mean how do we show a 3D graph of data? I’m going to cover that in my Java 3D tutorial
Okay more precisely, so far we are creating data (2d data), using xml’s and loading that to our product and testing our application.
now we need for 3d data to test our application, so is there any way to create 3d data?
I was doing a program in the roman numeral using RomanNumeralGUI,RomanNumeralList, RomanNumeralLinkList and RNLinkListIterator. when I built the frame of RomanNumeral and I entered JMenu , it suppose to enter the roman numeral sorted and Unsorted and when I press add ‘M’ for example it should enter it and when i press “delete” it should delete . so my question is to delete the roman numeral….
I’m sorry, but I don’t understand the question? What tutorial are you referring to here?
Great tutorials, thanks. Anyway there is a small typo:
while(theLink.bookName != bookName){
should be
while(!theLink.bookName.equals(bookName)){
thank for save me.wish you have many tutorial very well.
You are very welcome
I’m getting a sort of error. The program is printing the references for theLink.next, instead of the book name. I bypassed this problem by taking your toString() method from Link() and using it inside of LinkList.display() inside of the while loop.
However, I’m curious as to how I can fix this problem otherwise. Everything else worked fine, except for when I was initially making use of the LinkList.display().
When the program printed “Next Link: <expected book name" I got a reference/object instead, not the object's string contents. What should I be looking at to solve this?
Are you using the code I provide on my site?
why are there 2 files? may i put them in 1 file?
You could define an inner class with one of them, but I think that would be confusing
Is a link considered to be a node?
Yes they are very similar
Good lord this is amazing!
Thank you so much!
I wish there were more people like you out there that can I actually teach!
You’re very welcome
Thank you for the nice compliment.
Good work. it’s helpful. Thank you very much.
Thank you
Awesome work !
Thank you very much
Awesome tutorial Derek, as always you are!
I’m having a hard time to understand the difference between newlink.next & newlink….still confused
newLink.next = firstLink;
firstLink = newLink; which one is the address?
Thank you
Each node (link) has a reference to the next node (link) in the chain. When I make the first node here is no other nodes so next gets the value of null.
When I do add a new node I assign it to the the last node that was created. I put a reference to it in next.
Think of it as a bunch of boxes. In each box there is a piece of paper that tells you what box to open up next. If you decide you want to add on a new box just right that boxes name on a piece of paper and stick it in the box that proceeds it.
I hope that helps
Derek
Hi Derek, I watched your video tutorial, and I am very new to Java..
I am having difficultties on how will I Integrate Scanner in Linkedlist “where user can input , say or example the bookname”. I have tried all the possible things that I could try, but still having trouble.
I hope you’ll be able to help me with this..
Thanks
Check out this tutorial for ways to use scanner. I hope it helps