Algorithms-I : 2-Randomized_Queues_Deques: finished

1 files changed, 32 insertions, 25 deletions

diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
index e8a17de..d27629f 100644
--- a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
@@ -10,9 +10,9 @@ public class Deque<Item> implements Iterable<Item>
 
     private class Node
     {
-        Item item;
-        Node next;
-        Node prev;
+        private Item item;
+        private Node next;
+        private Node prev;
     }
 
     // construct an empty deque
@@ -24,16 +24,10 @@ public class Deque<Item> implements Iterable<Item>
     }
 
     // is the deque empty?
-    public boolean isEmpty()
-    {
-        return (head == null);
-    }
+    public boolean isEmpty() { return n == 0; }
 
     // return the number of items on the deque
-    public int size()
-    {
-        return n;
-    }
+    public int size() { return n; }
 
     // insert the item at the front
     public void addFirst(Item item)
@@ -43,8 +37,11 @@ public class Deque<Item> implements Iterable<Item>
         node.item = item;
         node.next = head;
         node.prev = null;
+        if (head == null)
+            tail = node;
+        else
+            head.prev = node;
         head = node;
-        if (tail == null) tail = head;
         n++;
     }
 
@@ -57,14 +54,10 @@ public class Deque<Item> implements Iterable<Item>
         node.next = null;
         node.prev = tail;
         if (tail == null)
-        {
-            head = tail = node;
-        }
+            head = node;
         else
-        {
             tail.next = node;
-            tail = tail.next;
-        }
+        tail = node;
         n++;
     }
 
@@ -73,9 +66,18 @@ public class Deque<Item> implements Iterable<Item>
     {
         if (head == null) throw new java.util.NoSuchElementException();
         Item item = head.item;
-        if (tail == head) tail = tail.next;
-        head = head.next;
-        head.prev = null;
+        if (head == tail)           // head.next == null
+        {
+            head = null;
+            tail = null;
+        }
+        else
+        {
+            Node prevHead = head;
+            head = head.next;
+            head.prev = null;
+            prevHead.next = null;
+        }
         n--;
         return item;
     }
@@ -85,14 +87,17 @@ public class Deque<Item> implements Iterable<Item>
     {
         if (tail == null) throw new java.util.NoSuchElementException();
         Item item = tail.item;
-        if (head == tail)
+        if (head == tail)           // tail.prev == null
         {
-            head = tail = null;
+            head = null;
+            tail = null;
         }
         else
         {
+            Node prevTail = tail;
             tail = tail.prev;
             tail.next = null;
+            prevTail.prev = null;
         }
         n--;
         return item;
@@ -105,8 +110,10 @@ public class Deque<Item> implements Iterable<Item>
     {
         private Node current = head;
 
-        public boolean hasNext() { return current != null; }
-        public void remove() { throw new java.lang.UnsupportedOperationException(); }
+        public boolean hasNext()
+        { return current != null; }
+        public void remove()
+        { throw new java.lang.UnsupportedOperationException(); }
         public Item next()
         {
             if (current == null) throw new java.util.NoSuchElementException();