JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Publish Your Article Here

Singly linked list implementation


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.

Here is the pictorial view of singly linked list:

Here is the pictorial view of inserting an element in the middle of a singly linked list:

Here is the pictorial view of deleting an element in the middle of a singly linked list:

Below shows the java implementation of singly linked list:


package com.java2novice.ds.linkedlist;

public class SinglyLinkedListImpl<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[]){
		SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<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;
		}
	}
}

Output:
Adding: 3
Adding: 32
Adding: 54
Adding: 89
Traversing to all nodes..
Deleted: 3
Traversing to all nodes..
Deleted: 89
32
54
76
Next Program >>

List of Linked List Data Structure Examples

  1. Singly linked list implementation in java
  2. Doubly linked list in Java
Knowledge Centre
What is OOPs?
Object oriented programming organizes a program around its data, i.e. , objects and a set of well defined interfaces to that data. An object-oriented program can be characterized as data controlling access to code.
Famous Quotations
Success consists of going from failure to failure without loss of enthusiasm.
-- Winston Churchill

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected] or you can comment on the page.

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java is registered trademark of Oracle.
Privacy Policy | Copyright © 2017 by Nataraja Gootooru. All Rights Reserved.