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>();
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();
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();
}
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
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++) {
count++;
}
}
return count;
}

public int getOutDegree(int v) throws VertexOutOfBoundsException {
int numV = getNumVertices();
if (numV <= v) throw new VertexOutOfBoundsException();
}``````

## 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);
}
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)) {
}

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

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

### Learn how data is stored

#### Data Structures and Algorithms in Java Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate.

\$ Check price (97+ reviews)

### Want to avoid becoming a code monkey?

#### Code Complete 2 This book synthesizes the most effective techniques and must-know principles into clear, pragmatic guidance. No matter what your experience level, development environment, or project size, this book will inform and stimulate your thinking - and help you build the highest quality code.

\$ Check price (291+ reviews)