Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Java: Creating my own Linked List

  1. Sep 26, 2011 #1
    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.

    Code (Text):

    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;
            }
     
     
  2. jcsd
  3. Sep 26, 2011 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Sep 26, 2011 #3

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  5. Sep 27, 2011 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

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

    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).

    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).
     
  6. Sep 27, 2011 #5

    rcgldr

    User Avatar
    Homework Helper

    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.

    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.
     
    Last edited: Sep 27, 2011
  7. Sep 27, 2011 #6

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

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

    Code (Text):

    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)
     
  8. Sep 27, 2011 #7

    rcgldr

    User Avatar
    Homework Helper

    Getting back to the orignal post.

    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.

    Code (Text):

    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.

    Code (Text):

    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?
     
    Last edited: Sep 27, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Java: Creating my own Linked List
  1. Linked list (Replies: 12)

  2. Java linked list (Replies: 1)

Loading...