Java: Creating my own Linked List

[trouty323]

Hello everyone. My task here is to construct my own linked list. The outer class is SLList and the inner class is Node. The problem that I seem to be having is when I try to use the fields of the outer class in the inner class, I am getting "cannot make static reference to the non-static field." My code is below. What is causing this to happen? I looked at the book and everything matches up. The only thing that seems to solve this problem is if I make the fields of the outer class static as well, but that is not how it is in the book.

public class SLList<E> {
	private Node<E> head;
	private Node<E> tail;
	private int size;

	/**
	 * Default constructor
	 */
	public SLList() {
		head = null;
		tail = null;
		size = 0;
	}

	/**
	 * Constructor for SLList
	 * 
	 * @param head
	 *            - beginning of the linked list
	 * @param tail
	 *            - end of the linked list
	 */
	public SLList(Node<E> head, Node<E> tail, int size) {
		this.head = head;
		this.tail = tail;
		this.size = size;
	}

	private static class Node<E> {
		private E data;
		private Node<E> next;

		/**
		 * Constructor for Node
		 * 
		 * @param data
		 *            - is of type E. It can contain any data type
		 * @param next
		 *            - next item in the list
		 */
		private Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}

		/**
		 * Adds an item to the tail of the linked list
		 * 
		 * @param newItem
		 *            - item to be added
		 */
		private void addTail(E newItem) {
			if (tail == null) {
				tail = new Node<E>(newItem, null);
				size++;
			} else {
				tail.next = new Node<E>(newItem, null);
				tail = tail.next;
				size++;
			}
		}

		/**
		 * Finds item in the linked list if it exists
		 * 
		 * @param search
		 *            - item to be searched for
		 * @return 0 if found, -1 if not found, -10 if empty list
		 */
		private int find(E search) {
			if (head == null) {
				return -10;
			}

			Node<E> p = head;

			do {
				if (search.compareTo(p.data) == 0) {
					return 0;
				} else {
					return -1;
				}
				p = p.next;
			} while (p != null);
		}

		/**
		 * Gets item at the specified index
		 * 
		 * @param index
		 *            - position where item is located
		 * @return data at specified index
		 */
		private E get(int index) {
			if (head == null || index > size - 1) {
				return null;
			}

			if (index < 0 || index >= size) {
				throw new IndexOutOfBoundsException(Integer.toString(index));
			}

			Node<E> p = head;
			int count = 0;

			while (count < index && p.next != null) {
				p = p.next;
				count++;
			}

			if (count != index) {
				return null;
			} else {
				return p.data;
			}
		}

		/**
		 * Sets the node at position index to item
		 * 
		 * @param index
		 *            - position to be changed
		 * @param item
		 *            - item to be placed at position index
		 */
		private void set(int index, E item) {
			if (index < 0 || index > size - 1) {
				throw new IndexOutOfBoundsException(Integer.toString(index));
			}
			Node<E> p = (Node<E>) get(index);
			p.data = item;
		}

 

[CompuChip]

If you run into trouble like this, it usually means you should reconsider your design.

For a node, it should have to be irrelevant that it is actually in a list. It should just have to know a) what data it contains and b) where it can find the next (and possibly previous) data node.

The list should do all the bookkeeping. When I use such a list, I expect that I can ask the list to insert a node for me (or actually, I would like to ask it to insert some data, and I don't care whether it uses nodes or butterflies to store that), and that it will do that (possibly delegating some tasks to the Nodes themselves) and update its administration. It looks like what you want is something like: I ask the list to give me its last node, ask that node to insert a new node to point to and then call back to the list to update the tailNode, right?

 

[rcgldr]

As posted above, all of the list operations should be handled in the list class. The node class doesn't need any functions (other than a constructor), although you might want a function to copy data from a node object.

The list constructor should only create an empty list. You may consider creating a function to initialize a list by appending to the list from an array of nodes.

The node constructor doesn't need to initialize it's next pointer. I don't know Java, so I'm not sure if the next pointer should be placed first in a node class that has a variable data component.

If you want the ability to determine if a node is in a list (without relying on the data content) you may want to add a pointer to list class in the node class to indicate if the node is in a list (pointer to a list) or not in a list (pointer is null). The list functions would maintain this pointer (set to list or null), not the node class.

You could make this more generic by defining the node class to have a generic pointer to a data object (the equivalent of a void pointer in C), rather than including the actual data in the node class.

 

[CompuChip]

I don't know Java, so I'm not sure if the next pointer should be placed first in a node class that has a variable data component.

That's not necessary, Java is quite good at handling memory itself.

If you want the ability to determine if a node is in a list

then you should ask the list whether it contains a node. IMO you shouldn't even need to be able to create a node yourself (its constructor should be private).

You could make this more generic by defining the node class to have a generic pointer to a data object (the equivalent of a void pointer in C), rather than including the actual data in the node class.

In Java, you would do this using generics, and declare a Node<T> object. Then you'd probably also have a List<T> with an add(T newElement) function that creates a Node<T>(newElement).

 

[rcgldr]

If you want the ability to determine if a node is in a list (without relying on the data content) you may want to add a pointer to list class in the node class.

Then you should ask the list whether it contains a node.

Yes. I was only trying to explain that adding a pointer to list in the node class would make this more efficient. I probably shouldn't have mentioned this function, since the usage would be rare other than a classroom exercise.

IMO you shouldn't even need to be able to create a node yourself (its constructor should be private).

Almost all my experience with linked lists has been as part of a queued messaging interface in a multi-tasking or multi-threaded environment. In some cases the threads dealt directly with nodes, while in other cases the threads only dealt with data objects while the list functions dealt with nodes internally. Both types of implementations have their pros and cons, a tradeoff between the overhead of copying data to/from nodes, versus having local data objects that can be accessed directly instead of via pointers. Otherwise the actual code in the threads wasn't affected that much by the choice of implementation.

 

[CompuChip]

Before we really confuse the TS, here is an example of how I would expect a linked list to work:

public static void main(String[] args) 
{
  SLLinkedList<int> list = new SLLinkedList<int>();
  list.addNode(3);
  list.addNode(1);
  Node<int> four = list.addNode(4);
  list.addNode(1);
  list.addNode(5);
  
  assert(list.containsNode(four) == true);
    // or possibly even: list.contains(4), where Node<T> uses T.equals()
  assert(list.size() == 5);
}

How it does that behind the scenes, is none of my business (as a professional once described it to me: the three pillars of Object Oriented programming are not Encapsulation, Polymorphism and Inheritance but Apathy, Ignorance and Selfishness: I don't know how you do it and I don't care - just give me what I need)

 

[rcgldr]

Getting back to the orignal post.

My task here is to construct my own linked list. The outer class is SLList and the inner class is Node. The problem that I seem to be having is when I try to use the fields of the outer class in the inner class ...

Assuming you got this example from a book, my guess is all that is missing is a second closing brace } after the constuctor for Node, so that the functions defined afterwards are members of the SLList class and not the Node class.

public class SLList<E> {
	/** ... */
	private static class Node<E> {
		private E data;
		private Node<E> next;

		/** ... */

		private Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}

	} /** add this brace to fix the code */

	/**
	 * Adds an item to the tail of the linked list
	 * 
	 * @param newItem
	 *            - item to be added
	 */
	private void addTail(E newItem) {
		/** ... */

Also you only need the default constructor for SLList. The other consrtuctor would be using head, tail, and size from another list, and multiple SLList classes for the same list would create problems if the list was modified.

public class SLList<E> {
	private Node<E> head;
	private Node<E> tail;
	private int size;

	/**
	 * Default constructor
	 */
	public SLList() {
		head = null;
		tail = null;
		size = 0;
	}

	/**
	 * This constructor for SLList is not needed
	 * head, tail, size would be parameters from another list
	 */

	/**  public SLList(Node<E> head, Node<E> tail, int size)  */

	/** ... */

Lastly, I don't know Java, but shouldn't SLList member functions such as addTail(...), find(...), get(...), ... , be public instead of private?