RewindProb.md

Designing an append() method that would concatenate a second queue onto the calling queue in Java. The method needed to traverse the appended queue’s nodes instead of dequeueing its items.

My solution at the time involved iterating until the node that was currently being checked had a null pointer and then transferring the node contents one more time after my while loop condition was met (since the node with the null pointer never got read/appended), but I could’ve iterated through by using the size() method at the start and iterating while i < [variable storing size()]

package jv.test;

import static java.lang.System.out;
import java.util.*;
import java.util.stream.*;

public class RewindProb {
  
  static class LinkedQueueNode<T> {
    public T value; // all members public for simplicity
    public LinkedQueueNode<T> next;
    public LinkedQueueNode(T value) {this.value = value;}
  }

  static class LinkedQueue<T> {
    private int size = 0;
    public int size() { return size; }
    private LinkedQueueNode<T> head = null;
    public LinkedQueueNode<T> getHead() { return head; }
    public boolean empty() { return head == null; }

    // what i would do is also keep track of the tail so you can append in O(1) time...
    public void push(T value) {
      size++; // assume queue is unbounded in size 
      if (head == null) { head = new LinkedQueueNode<T>(value); return; }
      LinkedQueueNode<T> tmp = head;
      while (tmp.next != null) tmp = tmp.next;
      tmp.next = new LinkedQueueNode<T>(value);
    }

    public T peek() {
      if (size == 0) return null;
      return head.value;
    }

    public T pop() {
      if (size == 0) throw new IllegalStateException("can't pop from an empty queue");
      size--;
      T value = head.value;
      head = head.next;
      return value;
    }

    public void append(LinkedQueue<T> otherQueue) {
      size += otherQueue.size();
      if (head == null) {head = otherQueue.getHead(); return;}
      LinkedQueueNode<T> tmp = head;
      while (tmp.next != null) tmp = tmp.next;
      tmp.next = otherQueue.getHead();
    }
  }

  public static void main(String[] args) {
    Random rand = new Random();
    List<Integer> firstList = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    LinkedQueue<Integer> firstQueue = new LinkedQueue<>();
    int i = 100; while(i-- > 0) firstList.add(rand.nextInt(1000));
    for (int j : firstList) firstQueue.push(j);
    out.println(String.format("init'ed first queue with %s random ints", firstQueue.size()));
    out.println("popping the first 20 elements");
    i = 20; while(i-- > 0) tmp.add(firstQueue.pop());
    out.println(String.format("size of first queue now: %s", firstQueue.size()));
    out.println("popped: " + String.join(" ", tmp.stream().map(String::valueOf).collect(Collectors.toList()) ) );
    out.println("reference: " + String.join(" ", firstList.subList(0, 20).stream().map(String::valueOf).collect(Collectors.toList())));

    List<Integer> secondList = new ArrayList<>();
    LinkedQueue<Integer> secondQueue = new LinkedQueue<>();
    i = 100; while(i-- > 0) secondList.add(rand.nextInt(1000));
    out.println(String.format("init'ed second queue with %s random ints", secondQueue.size()));
    for (int j : secondList) secondQueue.push(j);
    
    out.println("appending the second queue to the first");
    firstQueue.append(secondQueue);
    out.println(String.format("size of first queue now: %s", firstQueue.size()));

    tmp.clear();
    out.println("then popping all items...");
    while (!firstQueue.empty()) tmp.add(firstQueue.pop());
    out.println(String.format("size of first queue now: %s", firstQueue.size()));
    firstList = new ArrayList<>(firstList.subList(20, firstList.size())); firstList.addAll(secondList);
    out.println("same as reference? " + (tmp.equals(firstList) ? "TRUE" : "FALSE"));
    out.println(String.format("size of first queue now: %s", firstQueue.size()));
     // note that the head of the other queue (and thus all the subsequent nodes!) are still kept in memory, hence this should print 100!
    out.println(String.format("size of second queue now: %s", secondQueue.size()));
    
  }
}

Sample output

%  cd /Users/transfusion/code_sandbox ; /usr/bin/env /opt/homebrew/Cellar/openjdk/18.0.2.1/libexec/o
penjdk.jdk/Contents/Home/bin/java --enable-preview -XX:+ShowCodeDetailsInExceptionMessages -cp /Users/transfusion/Library/Application\ Support
/Code/User/workspaceStorage/74fcfe200bdf4f33a775a7f70624ffba/redhat.java/jdt_ws/code_sandbox_b3647d2e/bin jv.test.RewindProb 
init'ed first queue with 100 random ints
popping the first 20 elements
size of first queue now: 80
popped: 174 752 948 789 721 916 451 14 288 955 538 801 775 341 818 47 502 938 779 576
reference: 174 752 948 789 721 916 451 14 288 955 538 801 775 341 818 47 502 938 779 576
init'ed second queue with 0 random ints
appending the second queue to the first
size of first queue now: 180
then popping all items...
size of first queue now: 0
same as reference? TRUE
size of first queue now: 0
size of second queue now: 100