Below is an implementation of a queue using linked lists. To test it, you amy use the the solution for the packaging problem or any other program that uses IntQueue class. The LinkedList and Node implementations are included on the page. The linked list implementation has the removeFront() method.

What is the efficiency of each of the queue methods? What would the efficiency be if we insert elements in the front of the queue and remove them from the back (still using singly linked lists)?



public class IntQueue {
    private LinkedList list = new LinkedList();
    private Node endOfQueue; // the last element on the queue

    public boolean isEmpty() {
	return list.isEmpty();
    }
    
    public void enqueue(int k) {
	// insert the element at the end of the queue
	Node newLast = new Node(k);
	if (this.isEmpty()) { // calling the isEmpty method of this queue
	    list.setFirst(newLast); 
	    endOfQueue = list.getFirst(); // the new node created by setFirst
	} else {
	    endOfQueue.setNext(newLast);
	    endOfQueue = newLast;
	}	
    }

    public int dequeue() {
	// remove the element from the front of the queue
	int data = list.getFirst().getData();
	list.removeFront();
	if (list.isEmpty()) endOfQueue = null;
	return data;
    }

    // can be used for testing
    public void printQueue() {
	Node n = list.getFirst();
	while (n != null) {
	    System.out.println(n.getData());
	    n = n.getNext();
	}
    }
}


// This is a second implementation of Linked Lists.
// It makes sure that the list is in the consistent state 
// when elements are added to it. 

public class LinkedList {
    private Node first;

    public LinkedList() {
	first = null;
    }

    public boolean isEmpty() {
	return (first == null);
    }

    public Node getFirst() {
	return first;
    }

    // allows to set the first node to null
    public void setFirst(Node n) {
	if (n == null) {
	    first = null;
	} else {
	    Node newFirst = new Node(n.getData());
	    newFirst.setNext(null); // this is the only element on the list
	    first = newFirst;
	}
	
    }

    // works for non-null parameters only
    public void addFront(Node n) {
	// assume that n != null, otherwise NullPointerException
	Node internal = new Node(n.getData());
	internal.setNext(first);
	first = internal;
    }

    public void removeFront() {
	// assume that there is an element to remove,
	// otherwise NullPointerException
	first = first.getNext();
    }
}


public class Node {
    private int data;
    private Node next;

    public Node(int d) {
	data = d;
	next = null; // can skip this line: null is the default value
    }

    public int getData() {
	return data;
    }

    // return the next node
    public Node getNext() {
	return next;
    }

    // set the node 
    public void setNext(Node n) {
	next = n;
    }
}

This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.