Java Tutorial

Linked List

java.util.LinkedList:

LinkedList is the concrete sub-class of collection classes. LinkedList object allows us to group similar or dissimilar type of objects. Creating a LinkedList is nothing but creating an object of java.util.LinkedList class.

The data is organized in LinkedList in the form of nodes. The node contains two parts, they are data part, address part.

Data part always gives the actual data which we want to represent. Address part represents address of the next node.

For the last node in the LinkedList the address part must be NULL which indicates end of the LinkedList.

Linked List API:

Constructors:

LinkedList ();
LinkedList (int size);

Instance methods:

Object getFirst (); - 1 
Object getLast (); - 2
public void addFirst (Object obj); - 3
public void addLast (Object obj); - 4
public void removeFirst (); - 5
public void removeLast (); - 6

Methods 1 and 2 are used for obtaining first and last objects of LinkedList respectively. Methods 3 and 4 are used for adding similar or different objects to the LinkedList object respectively. Methods 5 and 6 are used for removing first and last objects from LinkedList respectively.

Write a java program which implements the concept of LinkedList?

Answer:

import java.util.*;

class Linkedlist {

    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        System.out.println("CONTENTS OF l1 = " + ll);
        System.out.println("SIZE = " + ll.size());
        ll.add(new Integer(10));
        ll.add(new Integer(20));
        ll.add(new Integer(30));
        ll.add(new Integer(40));
        System.out.println("CONTENTS OF ll = " + ll);
        System.out.println("SIZE = " + ll.size());
        // retrieving data of ll using toArray () 
        Object obj[] = ll.toArray();
        int s = 0;
        for (int i = 0; i < obj.length; i++) {
            Integer io = (Integer) obj[i];
            int x = io.intValue();
            s = s + x;
        }
        System.out.println("SUM USING toArray () = " + s);
        ll.addFirst(new Integer(5));
        ll.addFirst(new Integer(6));
        System.out.println("CONTENTS OF ll = " + ll);
        System.out.println("SIZE = " + ll.size());
        // retrieving data of ll using iterator () 
        Iterator itr = ll.iterator();
        int s1 = 0;
        while (itr.hasNext()) {
            Object obj1 = itr.next();
            Integer io1 = (Integer) obj1;
            int x1 = io1.intValue();
            s1 = s1 + x1;
        }
        System.out.println("SUM USING iterator () = " + s1);
        // retrieving data of ll using ListIterator () 
        ListIterator litr = ll.listIterator();
        while (litr.hasNext()) {
            Object obj2 = litr.next();
            System.out.print(obj2 + ",");
        }
        System.out.println("\n");
        while (litr.hasPrevious()) {
            Object obj3 = litr.next();
            System.out.print(obj3 + ",");
        }
        System.out.println("\n");
        Object obj4 = ll.get(2);// random retrieval 
        System.out.println(obj4);
    }
};

Disadvantages of Linked List:

  1. Additional memory space is created for address part of the node in heap memory.
  2. Retrieval time is more.
  3. Since, we are wasting most of the memory space for addresses, performance will be reduced.