Java Singly Linked List Implementation

Chapter: Interview Programs Last Updated: 30-10-2016 16:49:05 UTC

Program:

            /* ............... START ............... */
                package InterView;

public class JavaSinglyLinkedListImplementation<T> {

	private Node<T> head;
	private Node<T> tail;

	public void add(T element) {

		Node<T> nd = new Node<T>();
		nd.setValue(element);
		System.out.println("Adding: " + element);
		/**
		 * check if the list is empty
		 */
		if (head == null) {
			// since there is only one element, both head and
			// tail points to the same object.
			head = nd;
			tail = nd;
		} else {
			// set current tail next link to new node
			tail.setNextRef(nd);
			// set tail as newly created node
			tail = nd;
		}
	}

	public void addAfter(T element, T after) {

		Node<T> tmp = head;
		Node<T> refNode = null;
		System.out.println("Traversing to all nodes..");
		/**
		 * Traverse till given element
		 */
		while (true) {
			if (tmp == null) {
				break;
			}
			if (tmp.compareTo(after) == 0) {
				// found the target node, add after this node
				refNode = tmp;
				break;
			}
			tmp = tmp.getNextRef();
		}
		if (refNode != null) {
			// add element after the target node
			Node<T> nd = new Node<T>();
			nd.setValue(element);
			nd.setNextRef(tmp.getNextRef());
			if (tmp == tail) {
				tail = nd;
			}
			tmp.setNextRef(nd);

		} else {
			System.out.println("Unable to find the given element...");
		}
	}

	public void deleteFront() {

		if (head == null) {
			System.out.println("Underflow...");
		}
		Node<T> tmp = head;
		head = tmp.getNextRef();
		if (head == null) {
			tail = null;
		}
		System.out.println("Deleted: " + tmp.getValue());
	}

	public void deleteAfter(T after) {

		Node<T> tmp = head;
		Node<T> refNode = null;
		System.out.println("Traversing to all nodes..");
		/**
		 * Traverse till given element
		 */
		while (true) {
			if (tmp == null) {
				break;
			}
			if (tmp.compareTo(after) == 0) {
				// found the target node, add after this node
				refNode = tmp;
				break;
			}
			tmp = tmp.getNextRef();
		}
		if (refNode != null) {
			tmp = refNode.getNextRef();
			refNode.setNextRef(tmp.getNextRef());
			if (refNode.getNextRef() == null) {
				tail = refNode;
			}
			System.out.println("Deleted: " + tmp.getValue());
		} else {
			System.out.println("Unable to find the given element...");
		}
	}

	public void traverse() {

		Node<T> tmp = head;
		while (true) {
			if (tmp == null) {
				break;
			}
			System.out.println(tmp.getValue());
			tmp = tmp.getNextRef();
		}
	}

	public static void main(String a[]) {
		JavaSinglyLinkedListImplementation<Integer> sl = new JavaSinglyLinkedListImplementation<Integer>();
		sl.add(3);
		sl.add(32);
		sl.add(54);
		sl.add(89);
		sl.addAfter(76, 54);
		sl.deleteFront();
		sl.deleteAfter(76);
		sl.traverse();

	}

}

class Node<T> implements Comparable<T> {

	private T value;
	private Node<T> nextRef;

	public T getValue() {
		return value;
	}

	public void setValue(T value) {
		this.value = value;
	}

	public Node<T> getNextRef() {
		return nextRef;
	}

	public void setNextRef(Node<T> ref) {
		this.nextRef = ref;
	}

	@Override
	public int compareTo(T arg) {
		if (arg == this.value) {
			return 0;
		} else {
			return 1;
		}
	}
}
                /* ............... END ............... */
        

Output

Adding: 3
Adding: 32
Adding: 54
Adding: 89
Traversing to all nodes..
Deleted: 3
Traversing to all nodes..
Deleted: 89
32
54
76

Notes:

  • Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node. It is called a singly linked list because each node only has a single link to another node. To store a single linked list, you only need to store a reference or pointer to the first node in that list. The last node has a pointer to nothingness to indicate that it is the last node.

Tags

Singly Linked List Implementation, Java, Interview Programs

Similar Programs Chapter Last Updated
Java Program To Find Frequency Of Character In String Interview Programs 28-09-2017
Java Program To Find Power Of Number Using While Loop Interview Programs 30-08-2017
Java Program To Count Divisors Of Integer Number Interview Programs 24-06-2017
Java Program To Sort N Names In Ascending Order Interview Programs 24-06-2017
Java Program To Count Total Number Of Words In String Interview Programs 24-06-2017
Java Program To Print All Prime Numbers From 1 to N Interview Programs 24-06-2017
Java Program To Extract Digits / Numbers From String Interview Programs 22-09-2018
Java First Repeated Character In String Interview Programs 16-05-2017
Java String Character Repetition Count Interview Programs 15-05-2017
Java Program To Check Vowel Or Not Interview Programs 25-09-2018
Java Program To Check Alphabet Or Not Interview Programs 06-04-2017
Java Program To Find First Repeated And Non Repeated Character In String Interview Programs 25-03-2017
Java Spiral Matrix Interview Programs 22-09-2018
Java Program To Reverse A Number Using Strings Interview Programs 13-02-2017
Java Program To Print Diamond Star Pattern Interview Programs 16-12-2016
Java Program To Print Pyramid Pattern Of Star Interview Programs 16-12-2016
Java Program To Find Second Largest Number In Array Interview Programs 04-12-2016
Java Depth First Search Interview Programs 04-12-2016
Java Breadth First Search Interview Programs 04-12-2016
Java Linked List Length Recursive Solution Interview Programs 17-11-2016
Java Linked List Length Iterative Solution Interview Programs 17-11-2016
Java Linked List Node Deletion At Given Position Interview Programs 17-11-2016
Java Linked List Node Delete Interview Programs 17-11-2016
Java Sum Of Digits Using Recursion Interview Programs 06-11-2016
Java Program To Reverse Vowels Of String Interview Programs 05-11-2016
Java Program To Remove Vowels From String Interview Programs 05-11-2016
Java Find Top Two Maximum Numbers In Array Interview Programs 05-11-2016
Java QuickSort Example Interview Programs 05-11-2016
Java Binary Tree Spiral Level Traversal Interview Programs 04-11-2016
Java Binary Tree Preorder Traversal Interview Programs 04-11-2016

1 2 3 4 5