Get a site

Head Tail List in Java from scratch

UPDATE SEPTEMBER 22, 2016:

The method insert(Node x) of List.java was not optimized, now I have fixed it and his running time becames O(1)!

Creating a Head Tail LinkedList, this case in Java, it’s similar to the creation of a simple LinkedList, but with a pointer pointing to the tail.

Obviously the worst case running time for returning the last Node of the list would not be O(n) of the LinkedList, but would be O(1), that’s much faster, but the main feature is that now the worst case running time is not O(n), but O(1)!

Below you find the code to implement this List:

 

Main.java:

public class Main {

	public static void main(String[] args) {

		List l = new List();
		l.head = new Node(1);
		l.tail = new Node(10);
		
		l.head.next = l.tail;
		
		
		Node x = new Node(2);
		l.insert(x);
		Node a = new Node(5);
		l.insert(a);

		
		l.print();
		l.printTail();
	}

}

List.java:

public class List {
	
	Node head;
	Node tail;
	
	public void insert(Node x) {
		
		tail.next = x;
		Node temp = tail;
		tail = x;
		
	}
	
	public void print() {
		Node p = head;
		while(p != null) {
			System.out.println(p.val);
			p = p.next;
		}
	}
	
	public void printTail() {
		System.out.println("Tail: " + tail.val);
	}
}

Node.java:

public class Node {
	
	
	int val;
	Node next = null;
	
	public Node(int val) {
		this.val = val;
	}

}

Output:

1
10
2
5
Tail: 5