Created
February 17, 2013 10:41
-
-
Save VitalyStakhov/4970950 to your computer and use it in GitHub Desktop.
Deque on doubly linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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