LinkedList to be used in a stack or queue

Question

This all works. Just wanted to make sure I didn't miss anything. Coming from C++ and working my way through Algorithms, 4th ed. Here is my LinkedList class:

/*
 Linked List Implementation
 Based on Algorithms, 4th Edition, Section 1.3
 */

import java.util.Iterator;
import java.util.NoSuchElementException;
/**
 *

 * @author Taylor
 */
public class LinkedList<Item> implements Iterable<Item> {

    private String name;  //Holds the name of the list, if applicable
    private Node head;
    private Node tail = head;

    //Constructor with name
    public LinkedList(String name) {
        this.name = name;
        head = null;
        tail = head;
    }

    //Constructor without name
    public LinkedList() {
        this.name = "N/A";
        head = null;
        tail = head;
    }

    //The nodes for the list
    private class Node {

        Item data;  //The generic data the nodes contain
        Node next;
        Node prev;

        //Node constructor
        public Node(Item newData) {
            data = newData;
            next = null;
            prev = null;
        }

        public String toString() {
            return data.toString();
        }

        //Unnecessary?
        private void deleteNode() {  
            if (this.prev != null) {
                this.prev.next = this.next;
            }
            if (this.next != null) {
                this.next.prev = this.prev;
            }
        }
    }

    //Checks if the list is empty
    private boolean isEmpty() {
        return head == null;
    }

    //Adds node to end of list, for a push
    public void addToEnd(Item newData) {
        if (isEmpty()) {  //If it's the first (or all of the nodes have been removed)
            head = new Node(newData);
            tail = head;
        } else {
            tail.next = new Node(newData);
            tail.next.prev = tail;
            tail = tail.next;
        }
    }

    //Removes node from end of list, for a pop or dequeue
    public Item removeFromEnd() {
        if (isEmpty()) throw new NoSuchElementException("List empty");  //Trying to remove when there's no nodes left

        Item toReturn = tail.data;

        if(tail != head) {  //If there's more then one node left
            tail = tail.prev;
            tail.next = null;
        } else {  //Remove the last node
            tail = head = null;
        }

        return toReturn;
    }

    //Adds node to beginning of list, for a queue
    public void addToFront(Item newData) {
        if (isEmpty()) {  //If it's the first (or all of the nodes have been removed)
            head = new Node(newData);
            tail = head;
        } else {
            head.prev = new Node(newData);
            head.prev.next = head;
            head = head.prev;
        }
    }

    //Removes node from end of list
    public Item removeFromFront() {
        if (isEmpty()) throw new NoSuchElementException("List empty");

        Item toReturn = head.data;
        head = head.next;
        head.prev.deleteNode();

        return toReturn;
    }

    //Prints list from head to end
    public void printList() {
        Node currPos = head;
        while (currPos != null) {
            StdOut.print(currPos + " ");
            currPos = currPos.next;
        }
    }

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {

        private Node curr = head;

        public boolean hasNext() {
            return curr != null;
        }

        //Not implemented
        public void remove() {
        }

        public Item next() {
            Item data = curr.data;
            curr = curr.next;
            return data;
        }
    }



    //Test client
    public static void main(String[] args) {
        //LinkedList<Integer> testLL = new LinkedList<Integer>("Test");
        LinkedList testLL = new LinkedList("Test");

        testLL.addToEnd(3);
        testLL.addToEnd(4);
        testLL.addToFront(2);
        testLL.addToEnd(5);
        testLL.addToFront(1);
        testLL.removeFromEnd();
        testLL.addToEnd("String");
        testLL.removeFromFront();
        testLL.addToFront(0);

        //testLL.printList();

        Iterator testIterator = testLL.iterator();
        while(testIterator.hasNext()) {
            Object toPrint = testIterator.next();
            StdOut.print(toPrint.toString() + " ");
        }
    }
}

And here I added a quick implementation of a Stack and a Queue using that Linked List class

public class Stack {
    LinkedList StackList;

    public Stack() {
        StackList = new LinkedList();
    }

    private void push(String toAdd) {
        StackList.addToEnd(toAdd);
    }

    private String pop() {
        return (String) StackList.removeFromEnd();
    }

    public static void main(String[] args) {
        Stack myStack = new Stack();
        myStack.push("Test");
        myStack.push("Test2");
        StdOut.println(myStack.pop());
        StdOut.println(myStack.pop());
        myStack.push("Test3");
        StdOut.println(myStack.pop());
        StdOut.println(myStack.pop());
    }
}

---

public class Queue {
    LinkedList QueueList;

    public Queue() {
        QueueList = new LinkedList();
    }

    private void enqueue(String toAdd) {
        QueueList.addToFront(toAdd);
    }

    private String dequeue() {
        return (String) QueueList.removeFromEnd();
    }

    public static void main(String[] args) {
        Queue myQueue = new Queue();
        myQueue.enqueue("Test");
        myQueue.enqueue("Test2");
        StdOut.println(myQueue.dequeue());
        StdOut.println(myQueue.dequeue());
        myQueue.enqueue("Test3");
        StdOut.println(myQueue.dequeue());
        StdOut.println(myQueue.dequeue());
    }
}

Answer 1

Naming
Variables should be named using camelCase so e.g

LinkedList StackList;

should be

LinkedList stackList;

Comments
Comments should describe why something is done, not what the code is doing. Also redunant comments should be deleted, because sometimes they are just missleading like

//Removes node from end of list
public Item removeFromFront()  

Instead of

//Constructor with name
public LinkedList(String name) {
    this.name = name;
    head = null;
    tail = head;
}

//Constructor without name
public LinkedList() {
    this.name = "N/A";
    head = null;
    tail = head;
}

use constructor chaining

//Constructor without name
public LinkedList() {
    this("N/A");
}

//Constructor with name
public LinkedList(String name) {
    this.name = name;
    head = null;
    tail = head;
}  

Answer 2

Dead data

CTRL + F "name" ... 8 usages... class member variable, comment, comment, constructor argument, setting variable, passed in argument... comment, setting variable...

No reads! It's nice that you gave your LinkedList a name, but if nobody is going to call it by its name AND it doesn't get to tell its name to anybody, it's still gonna feel lonely. Treat it like the inanimate object that it's supposed to be and strip it of its name. (Sorry if that sounds harsh.)

DeleteNode

Who manages the nodes? Node or LinkedList? Pick one and make that one responsible. Heck. Copy the method, paste it in LinkedList, make it private and make it take a Node argument. LinkedList now controls the Nodes like it should (don't ever expose the nodes to the client, they don't want the nodes).

Stack and Queue

You might be better off implementing a generic (yes, generics) type T that you use to initialize your LinkedList. Doing so means you don't have to cast anymore, and that you support more than just String.

Comments

I dunno if your course teaches this, but when you make generic (not generics, just generic) classes like this, you'll want to add javadoc explaining what each method does and what it's side effects may be (such as throwing an exception if the list is empty when removing something).

Answer 3

Reiterating some of the other parts of answers:

• use constructor chaining. My preference is to have just one comprehensive constructor and all the other constructors call that comprehensive one with default parameters.
• don't have the name at all.

Generics

Java by convention uses a single upper-case letter to indicate the Generic type. In this case, Item should be T....:

 public class LinkedList<T> implements Iterable<T> ....

Your Stack and Queue classes should both be generic as well, with:

public class Queue<T> {
    LinkedList<T> queueList = new LinkedList<>();
    ...

Alternatively, if all queues will always be Strings, then you should have:

public class Queue {
    LinkedList<String> queueList = new LinkedList<>();
    ...

and that will remove the need for the (String) cast operations in the code.

Methods like enqueue(String value) will become enqueue(T value) as well.

This applies to both the Queue and the Stack

Constructor variables.

I much prefer initializing class variables outside the constructor, if possible. Certainly, you can do it inside the constructor, if needed, but, don't do both!

private Node head = null;
private Node tail = head;

and then don't reference head and tail in the constructor at all.

Node

Your node class has an instance-pointing variable that you never use. Your node class is a nested class to LinkedList. Because it is not static, the Node class has a pointer to the instance of LikedList that created the node. The Node class can then reference the variables inside the LinkedList instance that created the Node.

You never use this feature, so you have 'baggage' on all your Node instances that is just deadweight.

You should declare your Node as a static class, and make it Generically typed. Do not use T as the generic type though because that may lead people to think that the T is the same type as the outer LinkedList... when they are in fact not the same:

private static class Node<U> {

    U data;  //The generic data the nodes contain
    Node<U> next = null;
    Node<U> prev = null;

    //Node constructor
    public Node(U newData) {
        data = newData;
    }

    public String toString() {
        return String.valueOf(data);
    }

NullPointer

Notice in the above block I used the toString() method:

    public String toString() {
        return String.valueOf(data);
    }

The above toString will be null-safe. If someone stores a null value in your Node, the data.toString() will fail, but the String.valueOf(data) will be right.

Answer 4

For your Iterator implementation, since remove() is not implemented yet, you may want to throw UnsupportedOperation as that is the recommended usage.

For your Queue test class, enqueue is to add to the end of the queue and dequeue is to remove from the front. That is why queues are known as a first-in-first-out data structure. This is probably just semantics, but you should try swapping the operations around and see if there's any unintentional bugs. More info from Wikipedia.