Linked List in Java 2

Linked List in Java 2In 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+

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;
				
			}
			
		}
		
	}
	
}

4 Responses to “Linked List in Java 2”

  1. Jody says:

    I think that the insertAfterKey method needs to check the double link is not empty.

    if (!isEmpty()) {}
    else {
    lastLink = theNewLink;
    firstLink = theNewLink;
    }

  2. Jody says:

    In the NeighborIterator class, ‘theNeighbors’and ‘currentNeighbor’ may be null and lead to NullPointerException in the constructor, hasNext(), remove()

Leave a Reply

Your email address will not be published.

Google+