Home » DS01 SingleLinkedList and Iterator

Share This Post

Tutorial

DS01 SingleLinkedList and Iterator

SingleLinkedList, Iterator and Unit Test

This is the first article in a data structures tutorial series. We start with a linked list that is a singly linked list. This means it has nodes with only forward pointing pointers. This linked list is also an Iterator which is a design pattern. My version of this iterator has a reset() method to set the position pointer back to the first node in the list. Also this list does not give you access to the nodes themselves, only the element E that the node contains. The list can be made of any type of element E. As an example of unit testing I supply you with the TestNG code. If you are using Apache NetBeans 11 you may use TestNG for unit testing. Currently I could not get JUnit to work in NetBeans.

Java API LinkedList class

Interfaces and Classes

Several interfaces begin this code, Nodes, Position, Iterator and LinkedList. Nodes is for any dynamic type data structure. There is the Position which is needed for a later data structure called Sequence. The Iterator is a design pattern that lets you visit each node in the list. And LinkedList has some (head/tail) insert, remove, get, set and delete, nextElement methods and a few others.

First the Node class implements the Nodes interface. Then SingleLinkedList implements LinkedList interface and Iterator interface and it uses Nodes. To use this all that is needed is the SingleLinkedList. If you needed to modify SingleLinkedList then messing with the Node class could be in order. A possible mod might be a method that adds or inserts another SingleLinkedList into this list. It’s possible to do this add operation using other types of data structures as well. You will also see that there is no sorting or searching functionality.

What can a linked list be used for? The best uses are for other data structures such as Stacks, Queues and maybe Graphs. Linked list can grow in size until you run out of memory. Insertions and deletions are efficient. And another way to have built this data structure is for all methods to return nodes and not elements. Some developers may prefer it that way. The next data structure I will work on is DNode and DoubleLinkedList. In this list you may move forward or backward when traversing. There is also a circularly linked list. A good example of this is an image slider or a music play list. I will also implement Vector data structure based on both arrays and linked list.

The Interfaces

Nodes Interface

This is pretty simple. A node is an object that contains data and pointers. The pointers point to other nodes. So we have a way to set and get the data and set and get the next node pointer in this list. If a node has a null next node pointer then it is the end of the list.

/*
 * CPL Common Public License
 */
package sdz.ds.lists;

/**
 * Base interface for Node types in linked, tree or graph structures. 
 * 
 * @author Larry Gray
 * @param <E>
 */
public interface Nodes<E> {

 /**
  * Gets the element that this node contains.
  * @return the element
  */
 E getElement();

 /**
  * Gets the next Node in the list.
  * 
  * @return next Node
  */
 Node getNext();

 /**
  * 
  * Sets the element that this Node contains.
  *
  * @param element
  */
 void setElement(E element);

 /**
  * Sets the next Node in the list.
  *
  * @param next
  */
 void setNext(Node next);
 
} // Nodes interface

Position Interface

This is for a later data structure called Sequence.

/*
 * CPL Common Public License
 */
package sdz.ds.lists;

/**
 * Position interface.Operation on current Node.
 * 
 * @author Larry Gray
 * @param <E> element type
 */
public interface Position<E> {

 /**
  * Gets the element at the current node.
  * @return E element
  */
 public E getElement();
} // interface Position

Iterator Interface

Iterators allow you to step through the list visiting next items as long as the list has a next item. I didn’t add it to this interface but my SingleLinkedList has a reset() method to set the position to the first item in the list. A method iterator() could be made to return the list itself as an Iterator. Of course it would call reset() just before the return. When an empty list has one item inserted into it the position is the head or first item in the list. The position remains pointing to the head until there is a call to nextElement() or next(). Method nextElement() in the LinkList interface that is similar but returns boolean instead of the next element. So there is two ways to navigate the list LinkList way or Iterator way which are very similar.

/*
 * CPL Common Public License 
 */
package sdz.ds.iterator;

/**
 * This is the interface for Iterator Design Pattern.
 * 
 * @author Larry Gray
 * @param <E> Can be of any Element E
 */
public interface Iterator<E> {

 /**
  * Do we have more elements in list or are we done.
  * @return true if end of list.
  */
 boolean hasNext();

 /**
  * Moves to and returns next element.
  * @return next element in list.
  * 
  */
 E next();
} // interface Iterator

LinkedList Interface

There are quit a few methods here that I came up with from a data structures text book. I also added a couple of my own. The size(), empty() methods are actually a List data structure methods. Methods reset() and nextElement() are for traversing the list. Methods get() and set() are for accessing each nodes data and delete() or remove() eliminates the node at the current position while only remove operation returns the data at that node. Two methods get the head() and tail() get node data without removal. While removeHead() and removeTail() delete and return the node value.

To add to the list we do not have an add() method which is part of the List design pattern. LinkedList has insert methods, insertHead(), insertTail(), insertBefore() and insertAfter(). It’s before and after the current position in the list during traversal. Meaning traversal pointer position which is moved forward with nextElement() or next().

/*
 * CPL Common Public License
 */
package sdz.ds.lists;

/**
 * LinkedList data structure interface. Some methods are based on position of pointer 
 * in list while navigating list. Such as insertAfter() and insertBefore(). I added 
 * the reset() method to reset the pointer to the head of the list. nextElement() 
 * moves the pointer along. If you use the Iterator along with this interface 
 * next() also moves pointer along while returning the current Element.
 * 
 * @author Larry Gray
 * @param <E> element
 */
public interface LinkedList<E> {

 /**
  * Deletes node.
  */
 void delete();

 /**
  * Is the list empty?
  * @return true if empty.
  */
 boolean empty();

 /**
  * Gets element at current pointer.
  * @return element.
  */
 E get();
 
 /**
  * Sets and replaces element at current pointer.
  * @param e new element
  */
 void set(E e);

 /**
  * Gets the head of the list, no delete.
  * @return head element
  */
 E head();

 /**
  * Inserts after the current pointer.
  * @param element new element
  */
 void insertAfter(E element);

 /**
  * Inserts before the current pointer.
  * @param element new element.
  */
 void insertBefore(E element);

 /**
  * Inserts at the head of the list.
  * @param element new element.
  */
 void insertHead(E element);

 /**
  * Inserts at the tail of the list.
  * @param element new element.
  */
 void insertTail(E element);

 /**
  * Removes and returns element at current pointer.
  * @return element
  */
 E remove();

 /**
  * Removes and returns element at head of list.
  * @return element
  */
 E removeHead();

 /**
  * Removes and returns element at tail of list.
  * @return element
  */
 E removeTail();

 /**
  * Resets pointer to head element.
  */
 void reset();

 /**
  * Returns number of elements in list
  * @return number of elements
  */
 int size();

 /**
  * Returns tail element of list, no delete.
  * @return
  */
 E tail();
 
 /**
  * Moves pointer to next element in list.
  * @return false if no more elements
  */
 boolean nextElement();
 
} // interface LinkedList

The Classes

I think I have thoroughly tested these classes. The implementation might be improved a bit. So basically as you see it, I made it work. I have not yet analyzed it for efficiency as I have been itching to get this article out. The code could possibly be written a bit more cleanly. You be the judge.

Node Class

The implementation for the Node class is very basic and simple. Not much to talk about here. I provide two constructors, one for empty node and one for node given the element data and next node. If inserting at the tail there is no next node. Anywhere else and there will be.

/*
 * CPL Common Public License
 */
package sdz.ds.lists;

/**
 * Is a node for Single Linked List.
 * 
 * @author Larry Gray
 * @param <E>
 */
public class Node<E> implements Nodes<E> {
 /** The element that this node holds */
 private E element;
 /** The next node in the list */
 private Node next;

 /**
  * Constructs an empty node.
  */
 public Node() {
  this(null, null);
 } // Node()

 /**
  * Constructs a node given the element to store and the next node in the list.
  *
  * @param element
  * @param next Node
  */
 public Node(E element, Node next) {
  this.element = element;
  this.next = next;
 } // Node(E,Node)

 /**
  * Gets the element that this Node contains.
  * 
  * @return element
  */
 @Override
 public E getElement() {
  return element;
 } // getElement()

 /**
  * Gets the next Node in the list.
  * 
  * @return next Node
  */
 @Override
 public Node getNext() {
  return next;
 } // getNext()

 /**
  * Sets the element this Node contains.
  *
  * @param element
  */
 @Override
 public void setElement(E element) {
  this.element = element;
 } // setElement()

 /**
  * Sets the next Node in the list.
  * @param next
  */
 @Override
 public void setNext(Node next) {
  this.next = next;
 } // setNext
} // Node class

Single Linked List Class

The implementation for some of these methods becomes a bit complex. Because you must handle the case that the operation is at the beginning, end or in the middle of the list. Also for cases of empty list, 1 item in list, 2 items in list or many items in list. Note that the list can accept elements of any type E which may also be primitives thanks to auto boxing.

So we have pointers that keep up with the position of the head node, and tail node. Also one for the position of the node in the list that is in current focus as we navigate the list. There is a temp node used by insertion and remove operations.  An int field size tracks the size of the list as we add or remove nodes. Iterator methods next() and hasNext() use a field currentElement as a temporary store. Method next() returns the element at the next node. Method nextElement() returns false until end of list. Both move the position pointer forward.

The difference is that any node element may have a null value and when you reach the end of the list with next() you get a constant stream of nulls every time its called. So next must be used with hasNext(). But with nextElememnt you keep moving forward until you get true for end of list. I’m sitting here writing this thinking that maybe I needed to make it the other way around and have it return true, then false at end of list. Either way it works as long as you know how it works.

/*
 * CPL Common Public License
 */
package sdz.ds.lists;

import sdz.ds.iterator.Iterator;

/**
 * This is an implementation of Single Linked List data Structure. It also is an 
 * implementation of Iterator data Structure. The advantage of the linked data 
 * structure of course is that it can grow in size until you run out of memory.
 * And certain operations are more efficient or in some cases less efficient. 
 * insert and delete are very efficient. Finding the nth value is less efficient
 * than with arrays. Extending this class makes very good stacks and queues.
 *
 * @author Larry Gray
 * @param <E> of any Element.
 */
public class SingleLinkedList<E> implements LinkedList<E>, Iterator<E> {
 /** Head, front, start or top of list */
 private Node<E> head;
 /** Tail, back, end or bottom of list */
 private Node<E> tail;
 /** Temporary node storage*/
 private Node<E> temp;
 /** Position of pointer in list when traversing list. reset() moves 
  * this pointer back to head.
  */
 private Node<E> position;
 /**
  * Size of list which is kept current by modifications to list that add or
  * remove list items.
  */
 private int size;

 /**
  * Inserts element E head, front, start or top of list.
  *
  * @param element E
  */
 @Override
 public void insertHead(E element) {
  if (head == null) {
   head = new Node(element, null);
   tail = head;
   position = head;
  } else {
   temp = new Node(element, head);
   head = temp;
   position = head;
  } // else head not null
  size++;
 } // insertHead(E)

 /**
  * Inserts element E at tail, back, end or bottom of list.
  * 
  * @param element
  */
 @Override
 public void insertTail(E element) {
  if (tail == null) {
   tail = new Node(element, null);
   head = tail;
   position = head;
  } else {
   temp = new Node(element, null);
   tail.setNext(temp);
   tail = temp;
  } // else tail not null
  size++;
 } //insertTail(E)

 /**
  * Removes head from head, front or top of list. Deletes the element that
  * was removed. 
  *
  * @return head element E
  */
 @Override
 public E removeHead() {
  if(empty())return null;
  temp = head;
  head = head.getNext();
  if(size()==1){
   head=null;
   position=null;
   tail=null;
  }
  if(head!=null)position=head;
  size--;
  return temp.getElement();
 } // E removeHead()

 /**
  * Removes element E from tail, end or bottom of list. Deletes the element
  * that was removed.
  *
  * @return element E
  */
 @Override
 public E removeTail() {
  if(empty())return null;
  temp = head;
  if(size()==1){
   head=null;
   position=null;
   tail=null;
   size=0;
   return temp.getElement();
  }
  // get us to the end of list, if getNext() is = tail we 
  // are at the node previous to tail.
  while (temp.getNext() != tail) {
   temp = temp.getNext();
  } // while
  Node beforeTail = temp;
  temp = tail;
  beforeTail.setNext(null);
  tail = beforeTail;
  position = tail;
  size--;
  return temp.getElement();
 } // E removeTail()

 /**
  * Sets the navigational pointer back to head of list.
  */
 @Override
 public void reset() {
  position = head;
  
 } // reset()
 
 /**
  * Moves pointer to next position and returns the Element. 
  * 
  * @return E element at next position. A return value of null does not necessarily 
  * mean end of list. You must use hasNext() with next()
  */
 @Override
 public E next(){
  nextElement();
  return currentElement;
 } // next()

 /**
  * Inserts new element after element at current pointer position.
  * @param element the new element to be inserted.
  */
 @Override
 public void insertAfter(E element) {
  if (position == tail) {
   insertTail(element);
  } else {
   temp = new Node(element, position.getNext());
   temp.setNext(position.getNext());
   position.setNext(temp);
  } // else position not tail
  size++;
 } // insertAfter(E)

 /**
  * Inserts new element before element at current position.
  * 
  * @param element the new element to be inserted.
  */
 @Override
 public void insertBefore(E element) {
  if (position == head) {
   insertHead(element);
  } else {
   temp = head;
   while (temp.getNext() != position) {
    temp = temp.getNext();
   } // else position not head
   Node previous = temp;
   Node newNode = new Node(element, position.getNext());
   previous.setNext(newNode);
  }
  size++;
 } // insertBefore(E)

 /**
  * Deletes the element at the current position.
  */
 @Override
 public void delete() {
  if(empty())return;
  if (position == head && head == tail) {
   position = null;
   head = null;
   tail = null;
  } else if (position == head) {
   removeHead();
   size++;
  } else if (position == tail) {
   removeTail();
   size++;
  } else {
   temp = head;
   while (temp.getNext() != position) {
    temp = temp.getNext();
   } // while
   temp.setNext(position.getNext());
  } // else position is not head or tail.
  if(position!=tail)position = position.getNext();
  size--;
 } // delete()
 /**
  * Deletes and returns the element at the current position.
  * @return element to be removed.
  */
 @Override
 public E remove() {
  if(empty())return null;
  Node<E> removed = position;
  if (position == head && head == tail) {
   position = null;
   head = null;
   tail = null;
  } else if (position == head) {
   return removeHead();
  } else if (position == tail) {
   return removeTail();
  } else {
   temp = head;
   while (temp.getNext() != position) {
    temp = temp.getNext();
   } //while
   temp.setNext(position.getNext());
  } // else position is not head or tail
  if(position!=tail) position = position.getNext();
  size--;
  return removed.getElement();
 } // E remove()
 /** Stores element at current position. */
 private E currentElement;

 /**
  * Iterator method that returns false at end of list.
  * @return true if more elements in list.
  */
 @Override
 public boolean hasNext() {
  if(position!=null){
   currentElement=position.getElement();
  }else{
   currentElement=null;
   return false;
  }
  return true;
 } // hasNext()

 /**
  * Returns the current size of the list or number of elements in the list. This is 
  * kept current by insert and remove or delete methods.
  * @return number of elements in the list.
  */
 @Override
 public int size() {
  return size;
 } // size()

 /**
  * Is the list empty? If there is no head element then yes it is.
  * @return true if list contains no elements. 
  */
 @Override
 public boolean empty() {
  if (head == null) {
   return true;
  } // if
  return false;
 } // empty()

 /**
  * Retrieves the element at the head. Does not remove it.
  * 
  * @return head element.
  */
 @Override
 public E head() {
  if(empty())return null;
  return head.getElement();
 } // head()

 /**
  * Retrieves the element at the tail. Does not remove it.
  *  
  * @return tail element.
  */
 @Override
 public E tail() {
  if(empty())return null;
  return tail.getElement();
 } // E tail()

 /**
  * Gets the element at the current position.
  * @return element at current position.
  */
 @Override
 public E get() {
  if (position == null) {
   return null;
  } // if
  return position.getElement();
 } // E get()

 /**
  * Sets and replaces the element at the current position.
  * 
  * @param E new element
  */
 @Override
 public void set(E e) {
  if (position == null) {
   insertHead(e);
  } // if
  position.setElement(e);
  
 } // set(E)

 /**
  * Moves pointer position to next element if there is one.
  * @return returns false if position is null (at end of list)
  */
 @Override
 public boolean nextElement() {
  if (position==null) return false;
  if (position.getNext()==null){
   position=null;
   return false;
  }
  position=position.getNext();
  return true;
 } // nextElement()
} // SingleLinkedList

Unit Testing with TestNG

I had to split this article into two. The next article Testing SingleLinkedList with TestNG Framework cover the testing with code.

 

Share This Post

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>