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!

A handy guide of sorts for any computer science professional, Data Structures And Algorithms Made Easy in Java: Data Structure And Algorithmic Puzzles is a solution bank for various complex problems related to data structures and algorithms. It can be used as a reference manual by those readers in the computer science industry.

$ Check price(339+ reviews)

Designed for serious programmers, this reliable, unbiased, no-nonsense tutorial illuminates key Java language and library features with thoroughly tested code examples. As in previous editions, all code is easy to understand, reflects modern best practices, and is specifically designed to help jumpstart your projects.

$ Check price(70+ reviews)

Ad