CODEWITHSUNDEEP
javaarraysgenericscollections
Bryan Glazer
Bryan Glazer

Reputation: 852

How to implement a 2d array of LinkedLists

I'm working on implementing an algorithm from a paper. The paper describes using a grid, where each grid square holds a linked list of integers that represent objects in that grid square.

I decided to implement this using LinkedList<Integer>[][], which of course gives me a generic array creation error.

I can't think of a better way of representing the idea of a grid of linked lists. I also understand that using LinkedList[][] would compile but is bad practice as it is untyped. However, I would prefer not to use ArrayList<ArrayList<LinkedList<Integer>>> because that is unreadable, at least to me.

Is there a way around using an untyped LinkedList here? Or perhaps some other solution?

Upvotes: 3

Views: 9338

Answers (7)

Sagar Kumar
Sagar Kumar

Reputation: 92

You can declare an array of the linked list as follows.. but do not forget to declare when you are going to use the linked list otherwise you will get the nullpointeexception 

    LinkedList<Integer>[][] ll = new LinkedList[24][24];
    ll[0][0] = new LinkedList<>();
    ll[0][0].addFirst(3);
    System.out.println(ll[0][0].removeFirst());

Output : 3

Upvotes: 1

newacct
newacct

Reputation: 122489

I decided to implement this using LinkedList[][], which of course gives me a generic array creation error.

I can't think of a better way of representing the idea of a grid of linked lists. I also understand that using LinkedList[][] would compile but is bad practice as it is untyped.

Simple. To solve those problems just do

LinkedList<Integer>[][] grid = (LinkedList<Integer>[][])new LinkedList<?>[5][3];

Upvotes: 0

Paul Bellora
Paul Bellora

Reputation: 55223

Bohemian's answer is on the mark. If you're using Guava, a possible alternative is to use an ArrayTable<Integer, Integer, List<Integer>>. From the documentation:

Fixed-size Table implementation backed by a two-dimensional array.

The allowed row and column keys must be supplied when the table is created. The table always contains a mapping for every row key / column pair. The value corresponding to a given row and column is null unless another value is provided.

The table's size is constant: the product of the number of supplied row keys and the number of supplied column keys. The remove and clear methods are not supported by the table or its views. The erase(java.lang.Object, java.lang.Object) and eraseAll() methods may be used instead.

Here's an example of its usage:

private static final int NUM_ROWS = 20; //for example
private static final int NUM_COLS = 20; //

private static final ArrayTable<Integer, Integer, List<Integer>> TABLE =
        ArrayTable.create(
                Ranges.closed(1, NUM_ROWS).asSet(DiscreteDomains.integers()),
                Ranges.closed(1, NUM_COLS).asSet(DiscreteDomains.integers())
        );

public static List<Integer> getGridQuareList(int row, int col) {
    @Nullable List<Integer> list = TABLE.at(row, col);
    if (list == null) {
        list = Lists.newArrayList(); //or newLinkedList() if you insist
        TABLE.set(row, col, list);
    }
    return list;
}

Upvotes: 2

szegedi
szegedi

Reputation: 873

I don't know why on earth you would need a 3 dimensional list (2d array of a list, considering ArrayLists is really a 3d list/array). But if you do need that, then you should use what @Bohemian wrote:

List<List<List<Integer>>> grid;

What you should consider:

Declare variables to interfaces, not implementations, eg.:

List<Integer> list = new ArrayList<Integer>

instead of 

ArrayList<Integer> list = new ArrayList<Integer>

Also, generally it's not a good idea to mix generics with arrays, it can get nasty. If you wan't to do it in java and that's what you need do it the java way, as the others stated:

List<List<List<Integer>>>

Upvotes: 1

AlexWien
AlexWien

Reputation: 28747

First: You proably can avoid LinkedList. In Algorithm books, they did not know the ArrayList, Linked List, is more a synonym for dynamic list.
In nearly all cases ArrayList is faster, and especially for 2D arrays, need much less memory.

I personaly when having a fixed grid, with dynamic content, I use arrays:

List grid[][];

// init with
grid = new ArrayList[numX][numY];

that way i have an grid of object. This uses much less memory.

That way its is much handier when adding objetcs:

 List list = grid[i][j];
 if (list == null) {
      list = new ArrayList();
      this.cells[i][j] = list;
 }
 list.add(obj);

Upvotes: 0

Sotirios Delimanolis
Sotirios Delimanolis

Reputation: 280112

I would use the embedded ArrayList/LinkedList. What you can do to clean it up, since you know what kind of generic type they will have, is to wrap them inside some other class. Like so:

public class Grid {
    private List<List<List<Object>>> inner;

    public List<Object> objectsAtPosition(int x, int y) {
        return inner.get(x).get(y);
    }

    // etc
}

Upvotes: 1

Bohemian
Bohemian

Reputation: 425208

The list version

List<List<List<Integer>>> grid;

is not unreadable. To access a grid square it's just

List<Integer> items = grid.get(x).get(y);

Not that tough on the brane.

Upvotes: 5

Related Questions