Java Singly Linked List Implementation

Question

I've implemented a singly linked list in Java as a practice exercise and would appreciate a review.

LinkedList.java

public class LinkedList {
 private Node head;
 private int size;
 public LinkedList() {
 }
 public void addToEnd(char data) {
 addAtIndex(data, size);
 }
 public void addToBeginning(char data) {
 addAtIndex(data, 0);
 }
 public void addAtIndex(char data, int index) {
 Node temp = new Node(data);
 if (index < 0 || index > size) {
 throw new IndexOutOfBoundsException();
 } else if (index == 0) {
 temp.setNextNode(head);
 head = temp;
 incrementCount();
 } else {
 Node current = head;
 for (int i = 1; i < index; i++) {
 current = current.getNextNode();
 }
 temp.setNextNode(current.getNextNode());
 current.setNextNode(temp);
 incrementCount();
 }
 }
 public void deleteFromBeginning() {
 deleteFromIndex(0);
 }
 public void deleteFromEnd() {
 deleteFromIndex(size - 1);
 }
 public void deleteFromIndex(int index) {
 if (index < 0 || index >= size) {
 throw new IndexOutOfBoundsException();
 } else if (index == 0) {
 head = head.getNextNode();
 decrementCount();
 } else {
 Node current = head;
 for (int i = 1; i < index; i++) {
 current = current.getNextNode();
 }
 current.setNextNode(current.getNextNode().getNextNode());
 decrementCount();
 }
 }
 public char getFirst() {
 return getAtIndex(0);
 }
 public char getLast() {
 return getAtIndex(size - 1);
 }
 public char getAtIndex(int index) {
 if (index < 0 || index >= size) {
 throw new IndexOutOfBoundsException();
 } else {
 Node current = head;
 for (int i = 0; i < index && current != null; i++) {
 current = current.getNextNode();
 }
 return current.getData();
 }
 }
 public void decrementCount() {
 size--;
 }
 public void incrementCount() {
 size++;
 }
 public int getSize() {
 return size;
 }
 public Node getHead() {
 return head;
 }
}

Node.java

public class Node {
 private char data;
 private Node next;
 public Node(char data) {
 this.data = data;
 }
 public char getData() {
 return data;
 }
 public Node getNextNode() {
 return next;
 }
 public void setData(char data) {
 this.data = data;
 }
 public void setNextNode(Node next) {
 this.next = next;
 }
}

• ASA: There is no real reason not to make it generic. If you don't want to implement List<>, you could implement Iterable<T> or Iterable<Character>, since list iterators are used a lot (;.

Answer 1

Your code seems good to me. It's readable, well structured and formatted. So just a couple of minor points:

When implementing a list, it's always a good idea to implement the List interface, as it's well thought out.

The main differences to your interface I am seeing:

• naming: your method names contain an xIndex at the end. This isn't really needed, as the argument name index already suggests this.
• extra methods: you have a lot of methods which deal with the corner cases of other methods. So eg you have deleteFromBeginning, deleteFromEnd, and deleteFromIndex (same for add and get). This doesn't really seem necessary. List for example only has this for add, as adding happens quite often. It doesn't happen so often to want to delete from the beginning/end though.
• extra public methods: you also have some methods which are just not needed. decrementCount isn't needed and will cause problems when used, as the size will be wrong then. getHead is also not needed, it just exposes Node, which isn't really needed outside of the list context. Just make these private.
• you are missing some useful methods and your list is not generic, I'm assuming that both are on purpose as this is just for practice.

Misc

• Node should be a private class of LinkedList, as it's not needed outside of the list at all.
• I would use this for fields. It's a question of preference, but I prefer it as it makes it explicit where the variable comes from.
• initialize size explicitly to 0 in the constructor.

• j.castillo: Thanks a lot for the useful suggestions. Main points I overlooked: -made Node public to outside users, therefore violating the principle of encapsulation. -also violated encapsulating by making the size variable directly accessible which could lead to problems if incrementing/decrement without adding/deleting nodes. -inclusion of unecessary methods.
• flyingdrifter: implements List and immediately regrets it when he see's how many methods to override.

Answer 2

Good encapsulation should hide information and access to internal state that users don't need to know, and shouldn't know.

Tim pointed out about moving Node inside the LinkedList and make it hidden. Thanks to the getHead method, the internals of the class are exposed, open to abuses. For example a user may get the head, traverse the list manually, add and delete nodes, wreaking all kinds of havoc.

Another failure of encapsulation is by the decrementCount and incrementCount methods. These should not be called from outside the class. Calling them from outside without appropriate changes to the underlying nodes can lead to null pointer exceptions or memory leaks.

It's not that users are evil and want to break your class. It's that a program might be buggy and mistakenly misuse the class. To minimize the points of failure, it's extremely important to not expose more methods than really necessary for the functioning of a class.

• j.castillo: Good explanation on how I violated encapsulating in various different ways and the potential consequences.