Sunday, 11 March 2012

Use of java.util.LinkedList or LinkedList as Stack, Queue and Double-Ended Queue

The java.util.LinkedList<E> class implements Collection<E>, Deque<E>, List<E> and Queue<E> interfaces .The LinkedList can be used as
  • stack 
  • queue
  • double-ended queue
Let us discuss about it one by one.

LinkedList as stack

The LinkedList provides the following methods to implement LIFO(Last-In-First-Out) stacks.

public void push(E e)

Pushes an element onto the stack represented by this list. In other words, inserts the element at the front of this list.If the element cannot be added at this time due to capacity restrictions, throws IllegalStateException(NOTE:LinkedList has no capacity restrictions).

public E pop()

Pops an element from the stack represented by this list. In other words, removes and returns the first element of this list.If the stack is empty ,throws NoSuchElementException.

public E peek()

Retrieves, but does not remove, the head (first element) of this stack,or null if this stack is empty.
See the simple implementation given below

import java.util.*;

public class Main {

public static void main(String args[]) {

LinkedList<Integer> stack = new LinkedList<Integer>();

stack.push(1);
System.out.println("Pushed element: 1");
System.out.println("First element: " + stack.peek());
System.out.println("Popped element: " + stack.pop());
System.out.println("Is stack empty: " + stack.isEmpty());

}
}

The output is

Pushed element: 1
First element: 1
Popped element: 1
Is stack empty: true

LinkedList as queue

The LinkedList provides the following methods to implement FIFO(First In First Out) queues, where new elements insert at the back and elements remove from the front.

Throws exceptionReturns special value
Insertadd(e)offer(e)
Removeremove()poll()
Examineelement()peek()

boolean add(E e)

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateExceptionif no space is currently available.

boolean offer(E e)

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E), which can fail to insert an element only by throwing an exception.

E remove()

Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

E poll()

Retrieves and removes the head of this queue, or returns null if this queue is empty.

E element()

Retrieves, but does not remove, the head of this queue. This method differs from peek only in that it throws an exception if this queue is empty.

E peek()

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

See the simple implementation given below

import java.util.*;

public class Main {

public static void main(String args[]) {

LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(1);
queue.offer(2);
System.out.println("Removed elemenet: " + queue.remove());
System.out.println("Polled element: " + queue.poll());
System.out.println("Is queue empty:" + queue.isEmpty());
System.out.println("First element: " + queue.peek());
System.out.println("First element: " + queue.element());

}
}

The output is

Removed elemenet: 1
Polled element: 2
Is queue empty:true
First element: null
Exception in thread "main" java.util.NoSuchElementException
at java.util.LinkedList.getFirst(LinkedList.java:126)
at java.util.LinkedList.element(LinkedList.java:476)
at Main.main(Main.java:14)

LinkedList as double-ended queue

The LinkedList implements Deque<E> interface ,supports element insertion and removal at both end.
The LinkedList provides the following methods for implementing the double-ended queue.

First Element (Head)Last Element (Tail)
Throws exceptionSpecial valueThrows exceptionSpecial value
InsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)
RemoveremoveFirst()pollFirst()removeLast()pollLast()
ExaminegetFirst()peekFirst()getLast()peekLast()

No comments:

Post a Comment