Populating ArrayList of LinkedList

Question

I've been working on this project that creates a Concordance Data Structure which consists of Hashed structure with buckets. There is a problem I am running into every time I am trying to add a new element. I get a IndexOutOfBoundsExeption I understand that when I create an ArrayList of certain size, it just reserves the memory but does not actually contains any elements yet. How do I populate this ArrayList so i can ad elements in it.

public ConcordanceDataStructure(int i) {

            this.size=fourKPrime(i);
            this.hashtable=new ArrayList<LinkedList<ConcordanceDataElement>(size);


        }

Problem occurs in this method:

public void add(String term, int lineNum){ 
        boolean noError;
        boolean hit = false;
        int pass, q, offset, ip;
        int pk = Math.abs(term.toLowerCase().hashCode()); // preprocess the key
        if (nodes<=getTableSize())// insert the node
        { 
            pass = 0;
            q = pk / getTableSize();
            offset = q;
            ip = pk % getTableSize();
            if(q%getTableSize() == 0)
                offset = 9967;
        }
        else
        {
            System.out.println("FULL");
            return;
        }
        while(pass < getTableSize())
        { 
            if(hashtable.get(ip) == null){  //PROBLEM IS HERE
                hit = true;
                break;
            }
            ip = (ip + offset)%getTableSize();
            pass = pass +1;
        }
        if(hit == true) // insert the node
        { 
            hashtable.add(ip, new LinkedList<ConcordanceDataElement>());

            hashtable.get(ip).add(new ConcordanceDataElement(term));
            hashtable.get(ip).get(hashtable.get(ip).size()).addPage(lineNum);
            nodes++;

        }

I think you want to use array and resize it manually in order to add in a position that was not initialized yet. In other words to write you own ArrayList. Other option is to create a loop to the size and add `null` elements — Royal Bg, Oct 19 '16 at 21:51
I don't get it: why do you need an `ArrayList` for your bucket list, when a simple array of `LinkedList` will do? It's not like you are going to resize it at every insertion. Also, what's the reason for you to avoid using the [`HashMap`](https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html) class and start inventing the wheel anew? — Adrian Colomitchi, Oct 19 '16 at 21:56
@IgorKamalov "Array's size has to be predetermined " Nope. See updated answer — Adrian Colomitchi, Oct 19 '16 at 22:44

Adrian Colomitchi · Accepted Answer · 2016-10-19T22:31:29.597

0

Use an array of LinkedList instead of ArrayList<LinkedList>:

[edited to avoid the compilation error]

protected LinkedList<ConcordanceDataElement>[] hashtable;


public ConcordanceDataStructure(int i) {

   this.size=fourKPrime(i);
   @SuppressWarnings("unchecked")
   this.hashtable=new LinkedList[this.size];


}

protected int getTableSize() {
  return this.hashtable.length;
}

public void add(String term, int lineNum){ 
    boolean noError;
    boolean hit = false;
    int pass, q, offset, ip;
    int pk = Math.abs(term.toLowerCase().hashCode()); // preprocess the key
    if (nodes<=getTableSize())// insert the node
    { 
        pass = 0;
        q = pk / getTableSize();
        offset = q;
        ip = pk % getTableSize();
        if(q%getTableSize() == 0)
            offset = 9967;
    }
    else
    {
        System.out.println("FULL");
        return;
    }
    while(pass < getTableSize())
    { 
        if(hashtable[ip] == null){  // no more problems
            hit = true;
            break;
        }
        ip = (ip + offset)%getTableSize();
        pass = pass +1;
    }

edited Oct 19 '16 at 22:31

answered Oct 19 '16 at 21:59

Adrian Colomitchi

3,974
1
14
23

Cannot create a generic array of LinkedList ConcordanceDataStructure.java – Igor Kamalov Oct 19 '16 at 22:15
I think that array's size has to be determined beforehand. – Igor Kamalov Oct 19 '16 at 22:15
@IgorKamalov "I think that array's size has to be determined beforehand." No that's not it. I [forgot about it](http://stackoverflow.com/questions/14917375/cannot-create-generic-array-of-how-to-create-an-array-of-mapstring-obje). Correcting the code now. – Adrian Colomitchi Oct 19 '16 at 22:28
@IgorKamalov Corrected – Adrian Colomitchi Oct 19 '16 at 22:32
Thank you so much. – Igor Kamalov Oct 19 '16 at 23:08

Populating ArrayList of LinkedList

1 Answers1