How to operate on an ArrayList of ArrayList in Java?

Question

I'm facing a problem when operating on an ArrayList of ArrayList in Java. I have this thing in my code-

ArrayList<ArrayList<Integer>> L1 = new ArrayList<ArrayList<Integer>>();

Problem is, I have no idea as to how I should operate on this (addition, removal, traversal etc.). I wish to create an adjacency list (for implementing simple, undirected graphs), and my instructor suggests that I should create an ArrayList of ArrayList. I know I can do the following to add new element-

L1.add(//Something I want to add);

But this throws up an error in the current case for obvious reasons.

Jack · Accepted Answer · 2013-10-01 15:18:06Z

2

An ArrayList of an ArrayList, just think that the outer object is an ArrayList and you are done.

ArrayList<ArrayList<Integer>> list2d = new ArrayList<ArrayList<Integer>>();
// add an element to the list
list2d.add(new ArrayList<Integer>());
// retrieve a list 
ArrayList<Integer> list1d = list2d.get(0);
// add an integer
list2d.get(0).add(123);

By the way, an adjacency list is just a list of edges, there's no need to store them for each vertex, especially if the graph is undirected. A list of Edge would be enough:

class Edge {
  Vertex v1, v2;
}

ArrayList<Edge> adjacencyList;

If you want to store them on a per vertex basis then you could avoid using a list of lists by encapsulating the edges inside the vertex class itself but this will require twice the edges:

class Vertex {
  int value;
  ArrayList<Vertex> adjacency;
}

but which one is best depends on what kind of operation you need to perform on the graph. For a small graph there is no practical difference.

Another possible implementation, if you just need to know if two vertex are connected:

class Edge {
  public final int v1, v2;

  public boolean equals(Object o) { return o != null && o instanceof Edge && o.hashCode() == hashCode(); }

  public int hashCode() { return v1 ^ v2; } // simple hash code, could be more sophisticated
}

Set<Edge> adjacencyList = new HashSet<Edge>();

edited Oct 1, 2013 at 15:18

answered Oct 1, 2013 at 15:06

Jack

134k33 gold badges252 silver badges349 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

kenor Over a year ago

This might be misleading. By adjacencyList, it might be also meant a list of neighbour vertices (their indices) of certain vertex, thus L1.get(i) will return list of all vertex indices neighboring with index with idx i.

kenor Over a year ago

The advancement of per vertex lists of edges is getting all neigbours n of the vertex v in O(n(v)) time where n(v) is the number of neighbours of v. If only edges are stored, it will require O(e) time where e is the number of edges in the graph. The difference could be critical in some applications.

Jack Over a year ago

@kenor: in a context in which such a difference would be critical you won't be using an ArrayList at all, you would use sets for adjacency lists inside vertices in any case. There's no need to have an O(n) lookup when you can have O(1) if performance is critical.

kenor Over a year ago

of course, that was more of a hypothetical note, since the asker was for some reason instructed to use list of lists

Thomas · Accepted Answer · 2013-10-01 15:04:21Z

1

Try L1.get(i).add(whatever);, and of course first check whether L1.get(i) exists, otherwise add that inner list first.

It's something like this:

List<List<Integer>> L1 = new ArrayList<List<Integer>>(); //better use interfaces

List<Integer> first = null;
if( L1.size() > 0) {
 first = L1.get(0); //first element
}
else {
  first = new ArrayList<Integer>();
  L1.add(first);      
}

first.add(4711); //or whatever you like to add

answered Oct 1, 2013 at 15:04

Thomas

88.9k13 gold badges126 silver badges162 bronze badges

Comments

Prabhakaran Ramaswamy · Accepted Answer · 2013-10-01 15:06:09Z

1

List<List<Integer>> L1 = new ArrayList<ArrayList<Integer>>();    
List<Integer> list1 = new ArrayList<Integer>();     
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(4);
list1.add(5);

//add list to the list

L1.add(list1);

iterate over the list of lists

for( List<Integer> list: L1 ){
      for(Integer i:list){
          System.out.println(i);
      }
}

answered Oct 1, 2013 at 15:06

Prabhakaran Ramaswamy

26.1k10 gold badges61 silver badges65 bronze badges

1 Comment

Thomas Over a year ago

L1.add(list1); would not work unless L1 is defined to be List<List<Integer>>.

smcg · Accepted Answer · 2013-10-01 15:06:21Z

1

You can only add objects of type ArrayList to L1. So you could do this:

ArrayList<ArrayList<Integer>> firstList = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> secondList = new ArrayList<Integer>();
secondList.add(0);

firstList.add(secondList);

answered Oct 1, 2013 at 15:06

smcg

3,2733 gold badges32 silver badges40 bronze badges

Comments

thSoft · Accepted Answer · 2013-10-01 15:07:05Z

1

L1.add(new ArrayList<Integer>());

will create a new List within the first list. Then you can

L1.get(0).add(5)

edited Oct 1, 2013 at 15:07

thSoft

22.8k6 gold badges96 silver badges105 bronze badges

answered Oct 1, 2013 at 15:05

kenor

1,9102 gold badges16 silver badges28 bronze badges

1 Comment

kenor Over a year ago

Yep, sorry, no IDE :X

wtekiela · Accepted Answer · 2013-10-01 15:07:36Z

1

To add a new element to the outer array:

ArrayList<Integer> inner = new ArrayList<Integer>();
L1.add(inner);

Then to add element to the inner array:

   int exampleInt = 10;
   ArrayList<Integer> inner = L1.get(0);
   inner.add(exampleInt);

To traverse all elements in all arrays:

   for (ArrayList<Integer> inner : L1)
   {
      for (Integer element : inner)
      {
         System.out.println(element);
      }
   }

answered Oct 1, 2013 at 15:07

wtekiela

1,96915 silver badges18 bronze badges

Collectives™ on Stack Overflow

How to operate on an ArrayList of ArrayList in Java?

6 Answers 6

4 Comments

Comments

1 Comment

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

4 Comments

Comments

1 Comment

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related