Help with implementing a linked list as an array in JAVA

[greyfox32]

In my Advanced Data Structures class we have an assignment to implement a linked list using arrays. One array holds the data item, while another contains a reference to the next item. I'm not really sure about how to add/remove items.

// ****************************************************
// Reference-based implementation of ADT list using arrays.
// Due to the limitations with array of generics, the
// "data type" for the list items is fixed to be of type
// PageUsage.  Any program using this class must specify
// <PageUsage> as the value for the type parameter.
// ****************************************************
public class List<T> {
  // reference to linked list of items

  public static final int MAX_LIST = 20;
  public static final int NULL = -1;

  private PageUsage item[] = new PageUsage[MAX_LIST];  // data
  private int      next[] = new int[MAX_LIST];       // pointer to next item

  private int head;     // pointer to front of list
  private int free;     // pointer to front of free list
  private int numItems; // number of items in list

// Constructor must initialize used list to empty and free list to 
// all available nodes.

     public List() 
    {
         int index;
         for (index = 0; index < MAX_LIST-1; index++)
           next[index] = index + 1;

         next[MAX_LIST-1] = NULL;

         numItems = 0;
         head = NULL;
         free = 0;
     }  // end default constructor

    public void removeAll() 
    {   // reinitialize all nodes to free
         int index;
         for (index = 0; index < MAX_LIST-1; index++)
              next[index] = index + 1;

          next[MAX_LIST-1] = NULL;

         numItems = 0;
         head = NULL;
         free = 0;
     } // end removeAll

    public boolean isEmpty() 
    {  // ** YOU IMPLEMENT **
        if(head == NULL)
        {
            return true;
        }
        else
        {
            return false;
        }         
    }  // end isEmpty

    public int size() 
    {  // ** YOU IMPLEMENT **
        int count = 0;
        int i = head;
        while(i != -1)
        {
            count++;
            i = next[i];
        }
        return count;

    }  // end size

    private int find(int index) 
    {  // ** YOU IMPLEMENT **
    // --------------------------------------------------
    // Locates a specified node in a linked list.
    // Precondition: index is the number of the desired
    // node. Assumes that 1 <= index <= numItems
    // Postcondition: Returns a reference to the desired 
    // node.
    // --------------------------------------------------
        for(int i = 0; i <= numItems; i++)
        {
            if(next[i] == index)
            {
                return i;
            }
        }
        return -1;
    } // end find

    public PageUsage get(int index) 
    { // ** YOU IMPLEMENT **
        return item[find(index)];
    } // end get

 /* public void add(int index, PageUsage newItem) {  // ** YOU IMPLEMENT **
  }  // end add

  public void remove(int index) {  // ** YOU IMPLEMENT **
  }   // end remove*/
} // end List

[bguild]

You use -1 on line 66 when I'm sure you actually mean NULL. They may be represented using the same int, but NULL is more meaningful to someone reading your source code.

It looks like size is just counting the number of items in the list. Why doesn't it just return numItems?

Your find method doesn't do what it is supposed to do. It is also returning -1 when a precondition is violated, but you should throw an exception when a precondition is violated; returning a nonsense value will only make things harder to debug by causing later exceptions or incorrect behaviour instead of giving you an exception near the true location of the problem.

To add a node, just use find to get the node before the index where you want to insert, then take the first node from the free list and make it the next node. Of course, you also need to update the next index of the new node so that it points to the proper next node instead of the next free node, and you also need to update the head of the free list. You will need handle adding at index 0 as a special case.

To remove a node, start with the same find to get the index before the index you want to remove, and then do the add operations in reverse.

There is no real reason why you couldn't use a generic array for this. You can't do new T[MAX_LIST], but Java will reluctantly allow you to do (T[])new Object[MAX_LIST]. You need to suppress the warning that it gives you, but that's fine because it is actually perfectly safe.

[somjit{}]

first of all , welcome to daniweb. :)

now, regarding your code, when you say linked list as an array , im supposing this to be an implementation of a singly linked list. in which case , as you said , one array will hold the data , and another array will hold the "next" feild of a traditional linked list.

in that case , im having some doubts regarding your find() method:

      for(int i = 0; i <= numItems; i++)
        {
            if(next[i] == index)
            {
                return i;
            }
        }

this seems unnecessary. the disadvantage of linked list is in random access , finding/returning any "node" at random requires you to search from the head (in case of singly linked list) or either of the two ends (doubly linked list)... which you are doing here. But as you are using array ,you can just use the values from the arra that holds the "next" feilds to reference any data element directly.

also , it would be helpful if you post your code for the pageUsage[] class.
its easier to test for errors in debuggers and IDE's when the full code is available. :)

edit: i saw bguild had already posted after i posted.
a lot of the code looks like what it would do if the data structure was linked list , but its not , its arrays. i cant compile and check the code as the pageUsage class is missing , but regarding the size() method, i dont think all that effort is really needed to get the size of an array.

[greyfox32]

Thanks for the help. I definietely have a clearer picture of what I need to do. I would post the code for pageUsage[] but I don't have access to it, we were only given the .class file.

[somjit{}]

i suppose then your not using some IDE etc. if you have recently started java , its good practise to do java in command line. but , i have eclipse , if you want , you can attach the class file here , ill open it in eclipse and post the code back for you. :)

[greyfox32]

I have modified the code for the find() method.

int curr = head;
for(int i = 0; i < index; i++)
{
    curr = next[cur];
}
return curr;

I think it's correct now.

This is what I have so far for adding a new node.

int prev = find(index-1);
next[prev] = index;
item[free] = newitem;
next[free] = index +1;
free = next[free];
numItems++;

I tried attaching the .class file for PageUsage() but it says the file type is not allowed. However here is the link to my classes webpage where the files can be downloaded http://www.cs.ecu.edu/rws/c3310/p2/.

[bguild]

In your code for adding a new node you are confusing the meaning of index. This is a perfectly natural confusion because your list contains two kinds of index values that are both ints, both refer to nodes, and both stored in variables called index in your code, but they are not interchangeable. I'll call one of them "list index" and the other one "node reference".

A list index is what the user of your list uses. List indices number the items of your list from 0 to numItems - 1 in the order in which they appear to be stored. I say "appear" because we know that they aren't truly stored in that order; list index 0 is the head of the list, which could easily be stored near the end of the array. Because find expects an index between 0 and numItems - 1, it is clearly wanting a list index, and I believe add and remove also want list indices.

The other kind of index is the node reference which is the kind of index that find returns. The entire purpose of find is to convert from list indices to node references. A node reference is the actual position of some node within the arrays and so you have node references from 0 to MAX_LIST - 1, plus NULL is a special node reference that indicates the end of the list. The next array contains node references; this is critical, because you wouldn't be able to use the list if next contained list indices.

So I hope it is now clear to you that you shouldn't be doing next[prev] = index or anything like that when index is a list index given to add by the user. You must carefully keep track of which kind of index you are dealing with.

[greyfox32]

If I am understanding you correctly, then the code should look something like this?

int prev = find(index-1);
free = next[free];
item[free] = newItem;
next[free] = next[prev]
next[prev] = free;
numItems++;

[greyfox32]

Sorry about the double post, didn't see anyway to edit my previous post. Noticed an error in my code, here's the upadated version.

int prev = find(index-1);
    int temp = free;
    free = next[free];
    item[temp] = newItem;
    next[temp] = next[prev];
    next[temp] = next[prev];
    next[prev] = temp;
    numItems++;