CodesJava

Easy learning with example program codes

Java doubly 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.

Doubly linked list: Items can navigate in both forward and backword directions.

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;
 
import java.util.NoSuchElementException;
 
public class Test<T> {
    private Node head;
    private Node tail;
    private int size;
 
    public Test() {
        size = 0;
    }
 
    private class Node {
        T element;
        Node next;
        Node prev; 
        public Node(T element, Node next, Node prev) {
            this.element = element;
            this.next = next;
            this.prev = prev;
        }
    }
 
    public int size() {
    	return size; 
    }     
 
    public boolean isEmpty() {
    	return size == 0; 
    }
 
    public void addFirst(T element) {
        Node tmp = new Node(element, head, null);
        if(head != null ) {
        	head.prev = tmp;
        }
        head = tmp;
        if(tail == null) {
        	tail = tmp;
       }
        size++;
        System.out.println("Adding element: "+element);
    }
 
    public void addLast(T element) {         
        Node tmp = new Node(element, null, tail);
        if(tail != null) {
        	tail.next = tmp;
        }
        tail = tmp;
        if(head == null) {
        	head = tmp;
        }
        size++;
        System.out.println("Adding element: "+element);
    }
 
    public void iterateForward(){         
        System.out.println("Iterating forward.");
        Node tmp = head;
        while(tmp != null){
            System.out.println(tmp.element);
            tmp = tmp.next;
        }
    }
 
 
    public void iterateBackward(){         
        System.out.println("Iterating backword.");
        Node tmp = tail;
        while(tmp != null){
            System.out.println(tmp.element);
            tmp = tmp.prev;
        }
    }
 
    public T removeFirst() {
        if (size == 0) throw new NoSuchElementException();
        Node tmp = head;
        head = head.next;
        head.prev = null;
        size--;
        System.out.println("Deleted element: "+tmp.element);
        return tmp.element;
    }
 
    public T removeLast() {
        if (size == 0) throw new NoSuchElementException();
        Node tmp = tail;
        tail = tail.prev;
        tail.next = null;
        size--;
        System.out.println("Deleted element: "+tmp.element);
        return tmp.element;
    }
 
	public static void main(String args[]){
		try {
			Test<Integer> linkedlist = new Test<Integer>();
			linkedlist.addFirst(14);
			linkedlist.addFirst(546);
			linkedlist.addLast(36);
			linkedlist.iterateForward();
			linkedlist.removeFirst();
			linkedlist.removeLast();
			linkedlist.iterateBackward();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Linked list examples

Adding element: 14
Adding element: 546
Adding element: 36
Iterating forward.
546
14
36
Deleted element: 546
Deleted element: 36
Iterating backword.
14
Sign Up/ Sign In
Ask a Question


Industrial Training

We offers Placement Oriented Training on Java, Spring, JSF, Hibernate, PHP, AngularJS, Angular 4, PLSQL, Oracle BI Publisher etc. We also provides Online training, please mail us at hr@codesjava.com.

Development

We also provides the Development services for Website Development , Java Development, PHP Development, Android App Development etc. You can contact us on hr@codesjava.com.

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