javaarraylistqueuepass-by-referencememory-address

Does the original list decrease in size when I convert a list to a queue and poll?


Assume I have an array list like

List<Integer> list = [1,2,3,4]; // ignore the syntax here

Then I convert the collection to a queue

Queue<Integer> queue = new LinkedList(list);

Then I do

queue.poll(); // remove element from queue

Does the original list also reduce in size For the mere fact both queue and list reference the same collection of Integers?

I was expecting that after queue.poll(), then list.size() will be less in size as well but that's not the case. Does it mean the queue and list are different datasets in memory?


Solution

  • They may point to the same elements but they're different containers. The Queue is not backed by that list. References to the elements are copied from the list to the queue, but if you remove something from the queue it shouldn't (and doesn't) reflect on the list.

    In particular the constructor for LinkedList looks like this

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    

    The addAll method, in turn, look like this (after calling a version of itself and providing the size):

    public boolean addAll(int index, Collection<? extends E> c) {
        // omitted for brevity
    
        Object[] a = c.toArray();
    
        // omitted for brevity
    
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
    
        // omitted for brevity
    }
    

    (where first is the first node of the linked list)

    So, as you can see, it creates its own nodes. So yeah, if you remove any of those nodes you're not removing anything from the original list.