Skip to content

Instantly share code, notes, and snippets.

@VitalyStakhov
Created February 17, 2013 10:41
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save VitalyStakhov/4970950 to your computer and use it in GitHub Desktop.
Save VitalyStakhov/4970950 to your computer and use it in GitHub Desktop.
Deque on doubly linked list
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* Created with IntelliJ IDEA.
* User: Vitaly Stakhov
* Date: 28/09/2012
* Time: 16:49
* To change this template use File | Settings | File Templates.
*/
public class Deque<Item> implements Iterable<Item> {
private int size;
private Node first;
private Node last;
public Deque() {
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return size;
}
public void addFirst(Item item) {
throwIfNull(item);
Node newFirst = new Node();
newFirst.item = item;
if (first != null) {
newFirst.next = first;
first.previous = newFirst;
}
first = newFirst;
if (last == null) last = first;
size++;
}
public Item removeFirst() {
throwIfEmpty();
Node oldFirst = first;
first = first.next;
if (first == null)
last = null;
else
first.previous = null;
size--;
return oldFirst.item;
}
public void addLast(Item item) {
throwIfNull(item);
Node newLast = new Node();
newLast.item = item;
if (last != null) {
newLast.previous = last;
last.next = newLast;
}
last = newLast;
if (first == null) first = last;
size++;
}
public Item removeLast() {
throwIfEmpty();
Node oldLast = last;
last = oldLast.previous;
if (last == null)
first = null;
else
last.next = null;
size--;
return oldLast.item;
}
private void throwIfEmpty() {
if (first == null)
throw new NoSuchElementException();
}
private void throwIfNull(Item item) {
if (item == null)
throw new NullPointerException();
}
@Override
public Iterator<Item> iterator() {
return new ItemsIterator();
}
private class ItemsIterator implements Iterator<Item> {
private Node current;
public ItemsIterator() {
current = first;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if (current == null)
throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
private class Node {
Item item;
Node next;
Node previous;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment