Linked Lists in Java

You might want to check out these before continuing:

https://linuxjunkies.wordpress.com/2010/11/18/data-structures-using-java-part-6-linked-lists-part-1/

https://linuxjunkies.wordpress.com/2010/11/26/data-structures-using-java-part-7-linked-lists-part-2-doubly-linked/

Linked List

ListNode Class


public class ListNode {

	Object data;
	ListNode nextNode;
	
	ListNode (Object object, ListNode node){
		data = object;
		nextNode = node;
	}
	
	ListNode (Object object){
		this(object,null);
	}
	
	Object getObject(){
		return data;
	}
	
	ListNode getNext(){
		return nextNode;
	}
}

List Class


public class List {

	private ListNode firstNode;
	private ListNode lastNode;
	private String name;
	
	public List(){
		this("list");
	}
	
	public List(String listname){
		name = listname;
		firstNode = lastNode = null;
	}
	
	public void insertAtFront(Object item){
		if (isEmpty())
			firstNode = lastNode = new ListNode(item);
		else
			firstNode = new ListNode(item, firstNode);
	}
	
	public void insertAtBack(Object item){
		if (isEmpty())
			firstNode = lastNode = new ListNode(item);
		else
			lastNode = lastNode.nextNode = new ListNode(item);
	}
	
	public Object removeFromFront() throws EmptyListException{
		if (isEmpty())
			throw new EmptyListException(name);
		Object removed = firstNode.data;
		
		if( firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.nextNode;
		
		return removed;
	}
	
	public Object removeFromBack() throws EmptyListException{
		if (isEmpty())
			throw new EmptyListException(name);
		
		Object removed = lastNode.data;
		
		if( firstNode == lastNode)
			firstNode = lastNode = null;
		else{
			
			ListNode current = firstNode;
			
			while(current.nextNode != lastNode)
				current = current.nextNode;
			
			lastNode = current;
			current.nextNode = null;	
		}
		return removed;
		
	}
	
	public boolean isEmpty(){
		return firstNode == null;
	}
	
	public void print(){
		if (isEmpty()){
			System.out.println("List is empty");
			return;
		}
		
		ListNode current = firstNode;
		while (current != null){
			System.out.printf("%s --> ", current.data);
			current = current.nextNode;
		}
		System.out.println();
	}
	
	public int length(){
		int length = 0;
		
		if (isEmpty()){
			return 0;
		}
		
		ListNode current = firstNode;
		while (current != null){
			current = current.nextNode;
			length++;
		}
		return length;
	}
	
	public int recursiveSize(){
		return recursiveLength(firstNode);
	}
	
	public int recursiveLength(ListNode current){
		
		if (isEmpty()){
			return 0;
		}
		
		if (current == null)
			return 0;
		
		return (1 + recursiveLength(current.nextNode));
	}
	
}
	

ListTest Class


public class ListTest {

	public static void main(String[] args){
		
		List list = new List();
		
		list.insertAtFront( "four" ); 
		list.print();             
		list.insertAtFront( "two" ); 
		list.print();            
		list.insertAtBack( "six" );  
		list.print();          
		list.insertAtBack( "nine" );  
		list.print();            
		
		System.out.printf("Length: %d%n", list.recursiveSize());
		System.out.printf("Length: %d%n", list.length());
		
		try{
		    System.out.printf( "%s removed\n", list.removeFromFront());
		    list.print();
		    System.out.printf( "%s removed\n", list.removeFromFront());
		    list.print();
		    System.out.printf( "%s removed\n", list.removeFromBack());
		    list.print();
		    System.out.printf( "%s removed\n", list.removeFromBack());
		    list.print();
		}catch ( EmptyListException e ){
			e.printStackTrace();
		}
		
		System.out.printf("Length: %d%n", list.recursiveSize());
		System.out.printf("Length: %d%n", list.length());
		
		       
	}
}

This is what you get

four --> 
two --> four --> 
two --> four --> six --> 
two --> four --> six --> nine --> 
Length: 4
Length: 4
two removed
four --> six --> nine --> 
four removed
six --> nine --> 
nine removed
six --> 
six removed
List is empty
Length: 0
Length: 0
Advertisements
Linked Lists in Java

Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)

private field
————–
private field is invisible and inacessable to other classes.
Reasons:
1. To prevent data to be corrupted by other classes.
2. You can improve the implementation without causing the other classes to fail.

public class Date{

	private int day;
	private int month;

	public void setMonth(int m){
		month  = m;
	}

	public Date(int month , int date){
	// implementation and error checking code
	}
}
public class Evil{

	public void tamper(){

	Date d = new Date(10,10,2010); // this step is possible

	// these are not going to work!
	d.day =2000;
	d.setMonth(56);
	}
}

Interfaces
————
The interface of a class is made up of two things:
1. prototype for public methods and
2. the descriptions of the method behaviour.

Abstract Data Types(ADT)
——————————
ADT is a class(s) that has a well defined interface, but whose implementation details are firmly hidden from other classes.

Invarient
———-
Invarient is a fact about a data structure that is always true. (assuming there are no bugs). For example the “Date” object always represents a valid date.
Not all classes are ADTs. Some are just store data(no invarients).

The SList ADT
—————–

Another advantage of having a seperate SList class is that it enforces two invarients:
1. “size” is always correct.
2. list is never circularly linked.

Both of these goals are accomplised through simple Java mechanisms. Only the SList methods can change the lists.

SList ensures this:
1. The fields of the SList class are private. The “head” and “size” are private.
2. No method of SList returns an SListNode.

Doubly Linked Lists
———————

Doubly linked list

Inserting or deleting an element at the front of list is easy:

public void deleteFront(){
	if (head != null){
	head = head.next;
	size--;
	}
}

Inserting or deleting the item from the end of the list takes a lot of time in traversals.

public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

public class DList{

	private DListNode head; // points to start of the list
	private DListNode tail; // points to the end of the list
}

Insert and delete items at both ends in constant running time.
Removes the tail node (at least 2 items in DList):

tail.prev.next = null;
tail = tail.prev;

Sentinel
———
A special node that does not represent an item. It is to be noted that the sentinel node does not store an item.

Circularly linked Doubly linked list
————————————

 // no changes here
 public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

// changes here
public class DList{

	private DListNode head; // head will point to the sentinel
	private int size; // keeps track of the size of the list excluding the sentine.
}

DList invarients with sentinel:
——————————–
1. For any DList data structure d, d.head will never be null.
2. For any DListNode x, x.next is never null.
3. For any DListNode x, x.perv is never null.
4. For any DListNode x, if x.next is == y, then y.perv ==x.
5. For any DListNode x, x.prev ==y, then y.next ==x.
6. A DLists “size” field is number of DListNodes, NOT COUNTING sentinel. The sentinel is always hidden.
7. In empty DLists, the sentinels next and prev point to itselfs.

Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)

Data Structures using Java Part 6: Linked Lists Part 1

Lists
—–
Store a list of integers as an array.

Disadvantages:
1. Suppose you want to insert an item at beginning or middle of the list. This takes time propotional to the length of the array.
2. Arrays have a fixed length.

public class List{

	int[] a; // a reference
	int lastItem; // index to the last item of the list

	public List(){
	a = new int[10];
	lastItem = -1;
	}

	public void insertItem( int newItem, int location){ // inserts a new item at a location in the list
		int i;
		for(i = lastItem; i>= location; i--){  // this moves all the items in the list towards the right till the location is emptied
				a[i+1] = a[i];
		}
	a[location] = newItem; // puts the newItem value into the empty location slot
	lastItem++; // increment number of items
	}
}

Linked Lists ; A recursive data type
—————————————
1. A list that is made up of data structures called nodes.
2. Each node stores two things:
– an item
– a reference to the next node in the list

Singly linked list
public class ListNode{
	int item;
	ListNode next; // a reference called next pointing to next node in the list

}

// creating 3 different nodes
ListNode l1 = new ListNode();
ListNode l2 = new ListNode();
ListNode l3 = new ListNode();

// initialising values for items
l1.item = 10; // giving a value for item for l1
l2.item = 100;
l3.item = 1000;

//linking the nodes
l1.next = l2; // this links the lists
l2.next = l3;
l3.next = null; // l3 does not point to anything

Node operations
—————–

// the constructor for the ListNode
public ListNode(int item, ListNode next){

	this.item = item;
	this.next = next;
}

// for the last node
public ListNode(int item){
	this(item, null);
}

ListNode node1 = ListNode(7, new ListNode(0, new ListNode(6)));

Advantages over arrays
————————-
1. Inserting an item in the middle of the linked list takes constant amount of time if you have a reference to previous node.
2. Moreover, the list can keep growing until the memory runs out.

Inserting a new item after “this”

public void insertAfter(int item){

next = new ListNode(item, next); // the later "next" is the older value on whatever object we can like l2
}

l2.insertAfter(2);

The last statement creates a new node with the item value 2 and the next parameter is the next value of l2( old ) which points to l3. Now the new “next” value is assigned to the newly created node.

Disadvantages
—————
1. Finding the nth item of the linked list takes time propotional to the length of the list n, number of items in the list. With arrays you can do this in constant time.

// to find the nth item in a list
public ListNode nth( int location){

	if(position == 1){  // the current item
		return this;
	}else if ((position < 1) || ( next == null)){  // error checking
		return null;
	}else{
		// we will use recursion
		return next.nth(position -1); // -1 as we the list size keeps on decreasing
	}
}

ListNode l2 = l.nth(4);

Lists of objects
—————–
1. Reference any object by declaring a reference of type Object.

public class SListNode{ // a singly linked list

	public Object item;
	public SLinkNode next;
}

A List Class
————-
There are 2 problems with SListNodes:
1. Insert new item at the begining of the list.

x = new SListNode("Soap", x); // problem when two references to same node

2. How do you represent an empty list?

x = null; // runtime error if you try to call any method on x

Solutions
———-
1. Seperate SList class that maintains the head of the list.

public class SList{
	private SListNode head; // points to the beginning of the linked list
	private int size;  // keeps track of the number of SListNodes

	public SList(){ // initialisation
	head = null; // the idea of an empty list.
	size = 0;
	}

	public void insertFront(Object item){ // we now insert it here and not in SListNode
		head = new SListNode(item, head);
		size++;
 	}
}
Data Structures using Java Part 6: Linked Lists Part 1