Linked List in Java 2
In my previous Linked List in Java tutorial, I showed you how to create Linked Lists and how to manipulate them.
In this tutorial, I will cover Double Ended Linked Lists which have a reference to the first and last link. I cover how a Doubly Linked List allows you to go backwards and forwards in a list. Then we take a look at Iterators.
Numerous other topics are covered and the code and video below will help you learn.
If you like videos like this, it helps to tell Google+ [googleplusone]
Code From the Video
// A Double Ended LinkedList has a reference to
// the first and last Link in the List
public class DoubleEndedLinkedList {
Neighbor firstLink;
Neighbor lastLink;
public void insertInFirstPosition(String homeOwnerName, int houseNumber){
Neighbor theNewLink = new Neighbor(homeOwnerName, houseNumber);
// If no items in the list add the new Link
// to lastLink in the LinkedList
if(isEmpty()){
lastLink = theNewLink;
} /* FOR DOUBLY LINKED LIST */ else {
firstLink.previous = theNewLink;
} // END OF DOUBLY LINKED LIST ADDITION
// DOUBLY LINKED LIST
// Just like you can go forward in the list with next
// with a doubly linked list you can go backwards
// because it also has a previous as well as a next
// Assign the reference to the previous
// firstLink and assign the new Link
// to firstLink in LinkedList
theNewLink.next = firstLink;
firstLink = theNewLink;
}
public void insertInLastPosition(String homeOwnerName, int houseNumber){
Neighbor theNewLink = new Neighbor(homeOwnerName, houseNumber);
// If empty put the new Neighbor in first position
if(isEmpty()){
firstLink = theNewLink;
} else {
// Assign the last Neighbors next to the new Neighbor
lastLink.next = theNewLink;
theNewLink.previous = lastLink; // FOR DOUBLY LINKED LIST
}
lastLink = theNewLink;
}
// DOUBLY LINKED LIST ADDITION
// Insert after the provided key
public boolean insertAfterKey(String homeOwnerName, int houseNumber, int key){
Neighbor theNewLink = new Neighbor(homeOwnerName, houseNumber);
Neighbor currentNeighbor = firstLink; // Starts search at first link
// while the current houseNumber isn't the key keep looking
while(currentNeighbor.houseNumber != key){
currentNeighbor = currentNeighbor.next; // Switch to the next Neighbor
// If we get to the last Neighbor without a match leave the method
if(currentNeighbor == null){
return false;
}
}
// If we make it here we have a match for the key
// If the match was for the last Neighbor in the list
if(currentNeighbor == lastLink){
// Assign the new Neighbor as the last link
theNewLink.next = null;
lastLink = theNewLink;
} else {
// It didn't match for the last link
// So take next from the Neighbor that was
// here previously and assign theNewLink to
// the previous Neighbor
theNewLink.next = currentNeighbor.next;
currentNeighbor.next.previous = theNewLink;
}
theNewLink.previous = currentNeighbor;
currentNeighbor.next = theNewLink;
return true;
}
public static void main(String[] args) {
DoubleEndedLinkedList theLinkedList = new DoubleEndedLinkedList();
theLinkedList.insertInFirstPosition("Mark Evans", 7);
theLinkedList.insertInFirstPosition("Piers Polkiss", 9);
theLinkedList.insertInFirstPosition("Doreen Figg", 6);
theLinkedList.insertInLastPosition("Petunia Dursley", 4);
/*
theLinkedList.insertInOrder("Mark Evans", 7);
theLinkedList.insertInOrder("Piers Polkiss", 9);
theLinkedList.insertInOrder("Doreen Figg", 6);
theLinkedList.insertInOrder("Petunia Dursley", 4);
*/
theLinkedList.display();
theLinkedList.insertAfterKey("Derek Banas", 2, 6);
theLinkedList.display();
System.out.println("\n");
// Send the LinkedList to the iterator
NeighborIterator neighbors = new NeighborIterator(theLinkedList);
// Get the first neighbor and display
neighbors.currentNeighbor.display();
// Is there another?
System.out.println(neighbors.hasNext());
// Switch to the next Neighbor
neighbors.next();
neighbors.currentNeighbor.display();
neighbors.remove();
neighbors.currentNeighbor.display();
}
// Returns true if LinkList is empty
public boolean isEmpty(){
return(firstLink == null);
}
// Inserts Neighbors in order based on house number
public void insertInOrder(String homeOwnerName, int houseNumber){
Neighbor theNewLink = new Neighbor(homeOwnerName, houseNumber);
// Holds he last Neighbor searched so we can change
// its value for next if we input a new Neighbor
Neighbor previousNeighbor = null;
Neighbor currentNeighbor = firstLink;
// While there are still Neighbors and the new houseNumber
// is greater than the current focused houseNumber
// Change the > to < for opposite sort
while((currentNeighbor != null) && (houseNumber > currentNeighbor.houseNumber)){
previousNeighbor = currentNeighbor;
currentNeighbor = currentNeighbor.next; // Get the next Neighbor
}
// We are still at the beginning of the list
if(previousNeighbor == null){
// Save new Neighbor in the first position
firstLink = theNewLink;
} else {
// Assign the new Neighbor as the value for next
previousNeighbor.next = theNewLink;
}
// Assign the value of next to the next Neighbor
theNewLink.next = currentNeighbor;
}
public void display(){
Neighbor theLink = firstLink;
while(theLink != null){
theLink.display();
System.out.println("Next Link: " + theLink.next);
theLink = theLink.next;
System.out.println();
}
}
}
class Neighbor {
public String homeOwnerName;
public int houseNumber;
public Neighbor next;
public Neighbor previous; // Used with Doubly Linked List
public Neighbor(String homeOwnerName, int houseNumber){
this.homeOwnerName = homeOwnerName;
this.houseNumber = houseNumber;
}
public void display(){
System.out.println(homeOwnerName + ": " + houseNumber + " Privet Drive");
}
public String toString(){
return homeOwnerName;
}
}
// An iterator provides an easy way to cycle through all
// the objects in a LinkedList
class NeighborIterator{
Neighbor currentNeighbor; // The current focus Neighbor
Neighbor previousNeighbor; // The previous Neighbor
DoubleEndedLinkedList theNeighbors;
// hasNext, next, remove are common iterator methods
NeighborIterator(DoubleEndedLinkedList theNeighbors){
this.theNeighbors = theNeighbors;
currentNeighbor = theNeighbors.firstLink;
previousNeighbor = theNeighbors.lastLink;
}
public boolean hasNext(){
if(currentNeighbor.next != null){
return true;
}
return false;
}
public Neighbor next(){
if(hasNext()){
previousNeighbor = currentNeighbor;
currentNeighbor = currentNeighbor.next;
return currentNeighbor;
}
return null;
}
public void remove(){
// If at the beginning of the list
if(previousNeighbor == null){
theNeighbors.firstLink = currentNeighbor.next;
} else {
previousNeighbor.next = currentNeighbor.next;
// If at end of list
if(currentNeighbor.next == null){
// Assign first link as the current link
currentNeighbor = theNeighbors.firstLink;
previousNeighbor = null;
} else {
currentNeighbor = currentNeighbor.next;
}
}
}
}
I think that the insertAfterKey method needs to check the double link is not empty.
if (!isEmpty()) {}
else {
lastLink = theNewLink;
firstLink = theNewLink;
}
Thank you for the input 🙂
In the NeighborIterator class, ‘theNeighbors’and ‘currentNeighbor’ may be null and lead to NullPointerException in the constructor, hasNext(), remove()
Yes you are correct