CodesJava

Easy learning with example program codes

Java Singly linked list implementation


Linked list

A linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference or a link to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references. A drawback of linked lists is that access time is linear. Faster access, such as random access, is not feasible. Arrays have better cache locality as compared to linked lists.

Singly linked list: Items can navigate in forward direction only.

Linked list operations

    Insertion: Adds an element at the beginning of the list.
    Deletion: Deletes an element at the beginning of the list.
    Display: Displays the complete list.
    Search: Searches an element using the given key.
    Delete: Deletes an element using the given key.

Linked list examples

package com.codesjava;
 
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;
        }
    }
  }
 
   public class Test<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: "+element);
        if(head == null){
            head = nd;
            tail = nd;
        } else {
            tail.setNextRef(nd);
            tail = nd;
        }
    }
 
    public void addAfter(T element, T after){
 
        Node<T> tmp = head;
        Node<T> refNode = null;
        System.out.println("Traversing nodes");
        while(true){
            if(tmp == null){
                break;
            }
            if(tmp.compareTo(after) == 0){
                refNode = tmp;
                break;
            }
            tmp = tmp.getNextRef();
        }
        if(refNode != null){
            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("Element not found.");
        }
    }
 
    public void deleteFront(){         
        if(head == null){
            System.out.println("Underflow state");
        }
        Node<T> tmp = head;
        head = tmp.getNextRef();
        if(head == null){
            tail = null;
        }
        System.out.println("Deleted element: "+tmp.getValue());
    }
 
    public void deleteAfter(T after){
 
        Node<T> tmp = head;
        Node<T> refNode = null;
        System.out.println("Traversing nodes.");
        while(true){
            if(tmp == null){
                break;
            }
            if(tmp.compareTo(after) == 0){
                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 element: "+tmp.getValue());
        } else {
            System.out.println("Element not found.");
        }
    }
 
    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 args[]){
		try {
			Test<Integer> linkedlist = new Test<Integer>();
			linkedlist.add(13);
			linkedlist.add(23);
			linkedlist.add(4);
			linkedlist.addAfter(6, 13);
			linkedlist.deleteFront();
			linkedlist.deleteAfter(23);
			System.out.println("Traversing all nodes.");
			linkedlist.traverse();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Linked list examples

Adding element: 13
Adding element: 23
Adding element: 4
Traversing nodes
Deleted element: 13
Traversing nodes.
Deleted element: 4
Traversing all nodes.
6
23
Sign Up/ Sign In
Ask a Question


Copyright © 2018 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki