Custom linked list implementing Iterable used as stack

Question

I have created a custom linked list that implements the Iterable interface. I am then using this linked list to implement my custom stack. I have also thrown a custom exception while removing elements.

LinkedList class:

package collections.customCollections.linkedList; import java.util.Iterator; public class LinkedList<T> implements Iterable<T>{ private Link<T> head; private Link<T> tail; private int size; public int getSize() { return size; } public LinkedList(){ head = null; tail = null; size=0; } public void addAtEnd(T data){ Link<T> newNode = new Link<T>(data); //Insert as first element if(head == null){ head = newNode; tail = newNode; } else{ newNode.previous = tail; tail.next = newNode; tail = newNode; } size++; } public void addAtStart(T data){ Link<T> newNode = new Link<T>(data); if(head == null){ head = newNode; tail = newNode; } else{ newNode.next = head; head.previous = newNode; head = newNode; } size++; } //prints the entire linked list public void print(){ Link<T> traversalNode = head; if(head == null){ System.out.println("Empty Linked List"); } else{ while(traversalNode != null){ System.out.print(traversalNode.data +"->"); traversalNode = traversalNode.next; } } } public T remove(int index){ int i = 1; Link<T> traversalNode = head; while(i < index){ traversalNode = traversalNode.next; i++; } if(traversalNode.next == null){ removefromEnd(); } else if(traversalNode.previous == null){ removeFromStart(); } else{ traversalNode.previous.next = traversalNode.next; traversalNode.next.previous = traversalNode.previous; traversalNode.next = null; traversalNode.previous = null; } return traversalNode.data; } public T removefromEnd(){ Link<T> nodeToRemove = tail; tail = nodeToRemove.previous; tail.next = null; size--; return nodeToRemove.data; } public T removeFromStart(){ Link<T> nodeToRemove = head; head = nodeToRemove.next; head.previous = null; size--; return nodeToRemove.data; } public T get(int index) { Link<T> returnedNode = head; int i = 1; while(i < index){ returnedNode = returnedNode.next; i++; } return returnedNode.data; } private class Link<T>{ private T data; private Link<T> next = null; private Link<T> previous = null; public Link(T data){ this.data = data; } } @Override public Iterator<T> iterator() { return new Iterator<T>(){ private int position = 1; @Override public boolean hasNext() { if(position <= getSize()){ return true; } return false; } @Override public T next() { T data = get(position); position++; return data; } @Override public void remove() { LinkedList.this.remove(position); } }; } } 

The Stack class:

package collections.cutomcollections.stack; import collections.customCollections.exceptions.UnderFlowException; import collections.customCollections.linkedList.LinkedList; public class Stack<T> { private LinkedList<T> list; public Stack(){ list = new LinkedList<>(); } public int getSize() { return list.getSize(); } public void push(T data){ list.addAtEnd(data); } public T pop(){ if(list.getSize() <= 0){ throw new UnderFlowException("Empty Stack.No Elements in the Stack to pop."); } return list.removefromEnd(); } public T peek(){ if(list.getSize() <= 0){ throw new UnderFlowException("Empty Stack.No Elements in the Stack to pop."); } return list.get(list.getSize()-1); } } 

The Exception class:

package collections.customCollections.exceptions; public class UnderFlowException extends RuntimeException{ public UnderFlowException(String message){ super(message); } public UnderFlowException(String message,Throwable cause){ super(message,cause); } } 

I tried to incorporate all the comments I received from my previous questions into this code. What all are the further improvements I can make?

I also have some questions. I had to use LinkedList.this.remove(position) inside the remove method of the anonymous iterator class while I could simply call removeFromEnd(). The answer I got for this was that the compiler cannot differentiate due to the same name (even though they have different number of arguments) since the anonymous class is still a completely different class. Does that mean if I have a class that implements two different interfaces have methods that have same name but different arguments, I'll get the same error?

Another question is regarding the Link class inside the LinkedList class. I get a warning saying "The type parameter T is hiding the type T" where I declare the private class Link. I searched about it but couldn't understand the answers I found.

Then the custom exception that I created is an unchecked exception since I don't want users to explicitly handle it when they use my stack or list. But I am throwing this exception in my stack impl. If another class uses my linked list they would get a null pointer exception if say they invoked the remove method on an empty list. Should I do it at the list level?

Answer 1

Package declaration

package collections.customCollections.linkedList; 

• By convention, packages should be all lower-case.
• It should be something more uniquely identifiable to you. If you own a domain, you can start with com.mydomain
• It probably does not need to end with .linkedlist
• My suggestion would be: com.mydomain.collections or com.stackexchange.codereview.ishansoni.collections if you don't own a domain (or you can probably just make a domain up, use com.ishansoni for example).

Formatting

Yes, the boring stuff. You are a bit inconsistent with spacing and I would recommend changing things like this:

if(list.getSize() <= 0){ 

Into:

if (list.getSize() <= 0) { 

---

What happened here with the formatting?

public T get(int index) { Link<T> returnedNode = head; int i = 1; while(i < index){ returnedNode = returnedNode.next; i++; } return returnedNode.data; } 

Tidying it up:

public T get(int index) { Link<T> returnedNode = head; int i = 1; while (i < index) { returnedNode = returnedNode.next; i++; } return returnedNode.data; } 

---

Another question is regarding The Link class inside the LinkedList class.I get a warning saying "The type parameter T is hiding the type T" where i declare the private class link.I searched about it but couldn't understand the answers i found.

This is because your Link class is not static. Non-static inner classes can access all properties and methods of their parent class, therefore the compiler warns you that if you use Link<T> you won't be able to access the <T> from LinkedList<T>. Making the class static will solve this warning, and will effectively tell the compiler that you're just not interested in the outside class.

i had to use LinkedList.this.remove(position); inside the remove method of the anonymous iterator class while i could simply call removeFromEnd(). The answer i got for this was that the compiler cannot differentiate due to the same name (Even thou they have different number of arguments) since the anonymous class is still a completely different class. Does that mean if i have a class that implements two different interfaces have methods that have same name but different arguments i'll get the same error?

When using inner classes, this can be an issue yes. But when implementing two different interfaces, this will not be an issue.

Then the custom exception that i created is an unchecked exception since i don't want users to explicitly handle it when they use my stack or list .But i am throwing this exception in my stack impl. If another class uses my linked list they would get a null pointer exception if say they invoked the remove method on an empty list. Should i do it at the list level ?

Yes, you should handle that in your LinkedList class. It is good to make your classes as re-usable as possible. The remove method is part of your LinkedList class so it should handle all aspects of that method properly. You might want to throw a NoSuchElementException if remove is called on an empty list.

Answer 2

I am impressed by this solution. It looks good. The code is neat, and it has all the @Overrides, etc. in the right places (at least the ones I could see).

UnderFlowException

The UnderFlowException is redundant. You should reuse NoSuchElementException.

Stack

The Stack actually looks really good. I have a preference, when I build a stack on a linked list, to work at the 'front' of the list, not the 'tail', so, your code like:

public void push(T data){ list.addAtEnd(data); } public T pop(){ if(list.getSize() <= 0){ throw new UnderFlowException("Empty Stack.No Elements in the Stack to pop."); } return list.removefromEnd(); } public T peek(){ if(list.getSize() <= 0){ throw new UnderFlowException("Empty Stack.No Elements in the Stack to pop."); } return list.get(list.getSize()-1); } 

would just be:

public void push(T data){ list.addAtStart(data); } public T pop(){ if(list.getSize() <= 0){ throw new UnderFlowException("Empty Stack.No Elements in the Stack to pop."); } return list.removefromStart(); } public T peek(){ if(list.getSize() <= 0){ throw new UnderFlowException("Empty Stack.No Elements in the Stack to pop."); } return list.get(0); } 

Note, if your list implemented an isEmpty() method it would tidy up the stack a bit too.

Link

The Link class should be a static class. There is no reason for it to have an implied reference to the outer class. That makes it slightly larger in memory if you do that.

LinkedList

Your list is good as well. There's a few things to say in here, one of them is 'big', and also sometimes a little controversial, so you can choose to ignore this:

... you should have a non-null head and tail in the list. Create 'sentry' entries:

public class LinkedList<T> implements Iterable<T>{ private final Link<T> head = new Link<>(null); private final Link<T> tail = new Link<>(null); private int size; public LinkedList(){ size=0; head.next = tail; tail.previous = head; } 

Note, the head and tail instances are final. With non-null head and tail, you can have more interesting and simpler add/remove methods:

public void addAtStart(T data){ Link<T> newNode = new Link<T>(data); newNode.next = head.next; newNode.previous = head; head.next = newNode; newNode.next.previous = newNode; size++; } 

In all the places where you check for null, you can instead just check for identity-equality with either head or tail.

I would also add a locate(int index) method that was smarter, and more general than what you have. This method would loop from the end if the index was closer to that:

private Link<T> locate(int index) { if (index == size) { //special case for largest... return tail; } if (index >= (size / 2)) { int cnt = size - index - 1; Lint<T> link = tail.previous; while (--cnt >= 0) { link = link.previous; } return link; } Link<T> link = head.next; while (--index >= 0) { link = link.next; } return link; } 

That method will get you to any index. Then, methods like:

public T remove(int index){ Link<T> link = locate(index); link.next.previous = link.previous; link.previous.next = link.next; link.next = null; link.previous = null; size--; return link.data; } 

The add methods also become interesting with a helper method:

private void insertBefore(T data, Link<T> before) { Link<T> after = before.previous; Ling<T> link = new Link(data); link.previous = after; link.next = before; before.previous = link; after.next = link; size++; } 

With that method, you have methods like:

public void addAtEnd(T data){ insertBefore(data, locate(size)); } public void addAtStart(T data){ insertBefore(data, locate(0)); } 

etc.

Iterator

In the Iterator, with the sentry items for the head and tail, it could look like:

public Iterator<T> iterator() { return new Iterator<T>(){ private Link<T> cursor = head.next; private boolean canRemove = false; @Override public boolean hasNext() { return cursor != tail; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException("..."); } T data = cursor.data; cursor = cursor.next; canRemove = true; return data; } @Override public void remove() { // this is more complicated to get right, and you // need to check a state. remove() is only allowed after a call // to next(); if (!canRemove) { throw new IllegalStateException("Cannot remove unless previous next()"); } toRemove = current.previous; toRemove.previous.next = current; current.previous = toRemove.previous; toRemove.next = null; toRemove.previous = null; canRemove = false; } }; } 

Note, in the iterator, I have made the remove() contract 'right'. As it was, a person calling remove() before a next() would have done odd things, and so on. The contract for Iterator is clear:

IllegalStateException - if the next method has not yet been called, or the remove method has already been called after the last call to the next method

Also, I saw in your next() code that you don't first check to see whether there is a next(). Your code should throw NoSuchElementException:

NoSuchElementException - if the iteration has no more elements

Answer 3

The code is good but I just have few comments.

1. The class that represents a node should be called Node and not Link, this class could live in the package with no public access

2. the print method could be replace by toString for more flexibility

   @Override public String toString(){ Link<T> traversalNode = head; StringBuilder sb = new StringBuilder() if(head!=null{ while(traversalNode != null){ sb.append(traversalNode.data +"->"); traversalNode = traversalNode.next; } } return sb.toString(); }