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.

```
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 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);
}
```

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);
}
```

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);
}
```

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);
}
```

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();
}
```

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;
}
```

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;
}
```

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!

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(240+ reviews)

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(219+ reviews)

Ad