03. Adjacency List

In an adjacency list implementation, we have an array of |V| vertices. Within each array cell, we place a list containing all of that vertex's neighbors.

Example graph data structure.
Example digraph for explanation.
0 -> {1}
1 -> {1,3,4,5}
2 -> null
3 -> null
4 -> null
5 -> {1,6}
6 -> null

In this implementation, we can see how easy it is to add vertices and remove them. In a sparse graph, the efficiency is on average O(1).

The space it takes it O(E+V), much less than adjacency matrix implementation.

Adding a Vertex

Adding a vertex is simple. Just append a new vertex containing an empty list to the end of our ArrayList.

public void addVertex() {
    int v = getNumVertices();
    ArrayList<Integer> neighbors = new ArrayList<Integer>();
    adjListsMap.put(v, neighbors);
    setNumVertices(v+1);
}

Deleting a Vertex

To deleting a vertex, we remove the last ArrayList in our Map.

public void removeVertex() throws VertexOutOfBoundsException {
    // Remove the vertex at the end
    int numV = getNumVertices();
    if (numV == 0)
      throw new VertexOutOfBoundsException();
    adjListsMap.remove(numV);
    setNumVertices(numV+1);
}

Adding an Edge

To add an edge, simply retrieve the ArrayList corresponding to the beginning vertex in our Map, then append the value of the end vertex.

public void addEdge(int v, int w) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v || numV <= w) {
    throw new VertexOutOfBoundsException();
  }
    (adjListsMap.get(v)).add(w);
    setNumEdges(getNumEdges()+1);
}

Removing an Edge

To remove an edge that starts from v and goes to w, remove it from the vertex's list.

public void removeEdge(int v, int w) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v || numV <= w) throw new VertexOutOfBoundsException();
    // Remove edge that starts from v to w
    (adjListsMap.get(v)).remove(w);
    setNumEdges(getNumEdges()+1);
}

Finding in/out-degree

To find the in-degree, find the size of the corresponding vertex in the adjacency list. For out-degree, we must traverse through all ArrayLists in the entire adjacency list and count the number of times our vertex appears.

public int getInDegree(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
    int count = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        if ( (adjListsMap.get(i)).contains(v) ) {
            count++;
        }
    }
    return count;
}
 
public int getOutDegree(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
    return (adjListsMap.get(v)).size();
}

Finding degree sequence

The degree sequence is the same as the Adjacency Matrix implementation.

public List<Integer> getDegreeSeq() throws VertexOutOfBoundsException {
    List<Integer> degreeSeq = new ArrayList<Integer>();
    int degrees = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        degrees = getInDegree(i) + getOutDegree(i);
        degreeSeq.add(degrees);
    }
    Collections.sort(degreeSeq);
    Collections.reverse(degreeSeq);
    return degreeSeq;
}

Getting all Adjacent Neighbors

To obtain a list of all adjacent neighbors, simply return a copy of the list stored in our List.

public List<Integer> getNeighbors(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
  
    List<Integer> neighbors = new ArrayList<Integer>();
    for (Integer x : adjListsMap.get(v)) {
      neighbors.add(x);
    }
    
    return neighbors;
}

Getting all two-distanced neighbors

For getting all two-distanced neighbors, find all one-distanced neighbors, then find the neighbors of those.

public List<Integer> getNeighborsTwoApart(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
  
    List<Integer> oneApart = getNeighbors(v);
    ArrayList<Integer> twoApart = new ArrayList<Integer>();
    // For each integer within one hop of v...
    for (int i = 0; i < oneApart.size(); i++) {
        for (Integer x : oneApart) {
            twoApart.add(x);
        }
    }
    return twoApart;
}

Calculate the efficiencies of these operations and compare them to our Adjacency Matrix implementation!

Ace your Technical Interview

Elements of Programming Interviews

Ace your Technical Interview Try Algorithms

Learn all the different scenarios of . This book is jam packed with code snippets written in C++ and Java to give you the edge you need to ace your technical interviews. Problems come with detailed solutions as well as a hint in case you get stuck, and organized by difficulty level with several variants to help you apply your knowledge more widely.

$ Check price
39.9539.95Amazon 4 logo(240+ reviews)

More Algorithms resources

Learn Enterprise Java Development for a Bright Career

Effective Java

Learn Enterprise Java Development for a Bright Career Try Java

Are you looking for a deeper understanding of the Java so that you can write code that is clearer, more correct, more robust, and more reusable? Look no further! Effective Java brings together seventy-eight indispensable programmer's rules of thumb: working, best-practice solutions for the programming challenges you encounter every day.

$ Check price
54.9954.99Amazon 4.5 logo(219+ reviews)

More Java resources

Ad