Multi tool use

Single linked list still consuming memory after emptied [duplicate]

This question already has an answer here:

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://imgur.com/nQuDfUF

Thank you.

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

removeFirst()

new

new

1 Answer
1

It seems from my testing that the memory is still allocated, but awaiting garbage collection. The java.lang.Runtime class has some methods to inform you about memory usage, and a static method gc() to suggest running a garbage collect. Here's an extra method and a modification of your main() class that might help you:

main()

private final static long MB = 1024*1024;
static void memStats(String when)
{
Runtime rt = Runtime.getRuntime();
long max = rt.maxMemory();
long tot = rt.totalMemory();
long free = rt.freeMemory();
System.out.printf(
"mem(mb): %5d tot, %5d free %5d used %5d max %sn",
tot/MB, free/MB, (tot-free)/MB, max/MB, when);
}

// unit testing (optional)
public static void main(String args) {
Deque<Integer> deck = new Deque<>();
memStats("startup");
for( int i =0; i < 500000;i++) {
deck.addFirst(i);
}
memStats("after alloc");

for( int i =0; i < 500000;i++) {
deck.removeFirst();
}
memStats("after removal");
Runtime.getRuntime().gc();
memStats("after gc");

System.out.println("end");
try {
TimeUnit.MINUTES.sleep(5);
} catch (InterruptedException ex)
{
}
}


Put those in place of main() in your Deque class and run it. I get:

mem(mb): 15 tot, 15 free 0 used 247 max startup
mem(mb): 29 tot, 10 free 19 used 247 max after alloc
mem(mb): 29 tot, 10 free 19 used 247 max after removal
mem(mb): 29 tot, 29 free 0 used 247 max after gc
end


As you can see, (1) memory allocated to Java starts at 15MB total allocation for Java objects, with 0MB used. (Ignore the max figure. That doesn't report what I thought it did.) It indreases to 29MB with 19 used after the allocation.

max

Immediately after releasing all the Nodes in the Deque, there's no change at all!

Node

Deque

After the gc() call, though, notice that the total memory allocated to the heap hasn't changed, but all of is now free for use by other Java objects. That garbage collection would happen eventually--usually as soon as there's not enough contiguous memory in the heap to satisfy a new request.

new

As I said in comments, I'm not surprised that the extra 14MB or so added to the heap wasn't returned to the OS. If you use task manager in Windows, that memory will still be considered "in use". Going to the OS for memory is expensive, so normally that's done only to expand in large blocks (~15 million bytes, in this case, it seems) and only released at end of run. That's implementation-dependent behavior, though, and may be different on a different JVM.

A note on your code. I converted the Node class to:

private static class Node<Item> {
Node<Item> next; // lowercase next
Item item; // You were using Item for both a type and field name!?
}


...and converted pretty much every occurrence of Node to Node<Item>. That's as it should be, since the node item type is generic. That reduced the memory use from 19MB to 15MB on that same report. Non-static inner classes have each instance of the inner class tied to a specific instance of the surrounding class. You don't need that, and it costs time and memory.

Node

Node<Item>

That fix may help you pass tests.

Oh yes, note the field name changes from Next to next and Item to item. Start field and method names with a lowercase letter if you want to fit into traditional Java naming styles. In no case should you use Item for both a field name and a generic type name.