For an assignment we were asked to implement a data structure using single linked list.
My problem is that after adding items and then removing them the java program is still using the same memory as before.
Here is a simple example
Deque<Integer> deck = new Deque<>();
for( int i =0; i < 500000;i++) {
deck.addFirst(i);
}
for( int i =0; i < 500000;i++) {
deck.removeFirst();
}
System.out.println("end"); //Debugger here
Adding half a million items consumes 27mb of memory. After removing them is still at 27mb. Jumping with the debugger at the end, the variable deck has the fields first = null and count = 0;
Why is this the case? deck is empty and has no items but the memory is still used as before.
The code passes all the correctness tests but fails on the memory ones.
I also looked with the step by step debugger and is doing what is supposed to do.
Could it be that in removeFirst() I'm not setting anything to null and just assign first to be first.next ?
Edit: here is the output of a memory test
Test 10: Total memory usage after inserting 4096 items, then successively
deleting items, seeking values of n where memory usage is maximized
as a function of n
n bytes
---------------------------------------------------
=> passed 3200 65592
=> passed 1600 65592
=> FAILED 800 65592 (1.7x)
=> FAILED 400 65592 (3.4x)
=> FAILED 200 65592 (6.7x)
=> FAILED 100 65592 (13.1x)
=> FAILED 50 65592 (25.3x)
==> 2/7 tests passed
As you can see at 50 elements is still using 65592
Edit2:
// remove and return the item from the front
public Item removeFirst() {
if (this.isEmpty()) throw new java.util.NoSuchElementException();
Item current = first.Item;
first = first.Next;
count--;
return current;
}
This is removeFirst()
Edit3:
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.TimeUnit;
/**
* Created by Alex on 6/30/2018.
*/
public class Deque<Item> implements Iterable<Item> {
private Node first;
private int count;
private class Node {
private Node Next;
private Item Item;
}
// construct an empty deque
public Deque() {
first = null;
count = 0;
}
// is the deque empty?
public boolean isEmpty() {
if (count == 0) {
return true;
}
return false;
}
// return the number of items on the deque
public int size() {
return count;
}
// add the item to the front
public void addFirst(Item item) {
if (item == null) throw new IllegalArgumentException();
Node temp = new Node();
temp.Item = item;
temp.Next = first;
first = temp;
count++;
}
// add the item to the end
public void addLast(Item item) {
if (item == null) throw new IllegalArgumentException();
if (isEmpty()) {
addFirst(item);
} else {
Node last = first;
while (last.Next != null) {
last = last.Next;
}
Node newLast = new Node();
newLast.Item = item;
newLast.Next = null;
last.Next = newLast;
count++;
}
}
// remove and return the item from the front
public Item removeFirst() {
if (this.isEmpty()) throw new java.util.NoSuchElementException();
Item current = first.Item;
first = first.Next;
count--;
return current;
}
// remove and return the item from the end
public Item removeLast() {
if (isEmpty()) throw new java.util.NoSuchElementException();
if (size() == 1) {
return removeFirst();
}else {
Node newLast = first;
Node oldLast = first;
while (oldLast.Next != null) {
newLast = oldLast;
oldLast = oldLast.Next;
}
newLast.Next = null;
count--;
// Item lastItem = ;
return oldLast.Item;
}
}
// return an iterator over items in order from front to end
public Iterator<Item> iterator() {
return new DequeIterator();
}
private void debug() {
Iterator<Item> deckIter = iterator();
while(deckIter.hasNext()) {
System.out.println(deckIter.next());
}
System.out.println(isEmpty());
System.out.println("Size:" + size());
}
// an iterator, doesn't implement remove() since it's optional
private class DequeIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.Item;
current = current.Next;
return item;
}
}
// unit testing (optional)
public static void main(String[] args) throws InterruptedException {
Deque<Integer> deck = new Deque<>();
for( int i =0; i < 500000;i++) {
deck.addFirst(i);
}
for( int i =0; i < 500000;i++) {
deck.removeFirst();
}
System.out.println("end");
TimeUnit.MINUTES.sleep(5);
}
}
Edit4: Those are the memory constraints
https://i.stack.imgur.com/8d5iD.jpg
Thank you.
