The lesson implements a graph as an adjacency list. Each vertex's unique data value identifies a key, and its entry stores neighboring vertices. The constructor chooses directed or undirected behavior, defaulting to undirected. This makes edge insertion and vertex removal concrete without requiring a separate object for every possible pair of vertices.
Establish vertices before connecting them
Adding a vertex creates an empty neighbor collection. A newly created isolated vertex still belongs to the graph even though it has no edges. Decide what repeated insertion of the same key should do; blindly replacing an existing neighbor collection would erase connections.
Adding an edge updates the source vertex's neighbors. In an undirected graph it must also update the reverse relationship. That symmetry is an invariant to check after every mutation. A directed graph adds only the requested direction. The choice affects reachability, so a traversal cannot infer the reverse edge unless it is actually stored or guaranteed by the model.
Remove incoming references as well as the vertex
Deleting a vertex's own entry does not remove references to it from other adjacency lists. The removal operation must also delete those incoming edges. In an undirected graph, affected neighbors contain the reverse entries. In a directed graph, incoming edges may originate anywhere unless another index records them.
Test a vertex with several neighbors, an isolated vertex, a self-loop if permitted, and a missing vertex. Decide whether repeated edges are allowed or whether neighbor collections represent sets. Arrays and sets provide different duplicate behavior and removal costs, so the API should choose deliberately.
Analyze operations using the stored collections
An adjacency list occupies O(V + E) storage, counting an undirected edge in both endpoint lists. Adding a neighbor can be direct, while checking uniqueness or removing it from an array may require a scan. Removing a vertex may inspect many neighbor collections; it is not automatically constant time because a top-level key deletion is quick.
Open the current implementation and trace an add-remove-add sequence to check for stale edges. Then apply Depth-First Search and Breadth-First Search to the same stored graph. A traversal should visit the structure left by its actual mutations, including isolated vertices when the task asks for complete coverage.
Follow a directed and an undirected edge
Create vertices A, B, and C. In directed mode, adding A → B stores B in A's adjacency list only. In undirected mode, it also stores A in B's list. Removing B deletes its own list and filters B from every remaining list, including incoming directed edges.
This implementation stores adjacency entries in lists, so duplicate edges are preserved. In undirected mode, adding a self-loop appends twice to the same list. Those are consequences of the shown representation, not a claim that every graph API chooses the same policies.
Establish preconditions before mutation
Add each vertex once before adding edges. Calling addVertex again replaces that vertex's existing adjacency list in these teaching versions. Some languages also create or tolerate missing endpoint entries differently, so missing vertices are outside the shared cross-language contract. A product API should choose and enforce one policy explicitly.
With ordinary map assumptions, adding a vertex and appending an edge have expected or amortized constant structural cost. Removing a vertex scans remaining adjacency lists, for O(V + E) work. Storage is O(V + E), counting every stored adjacency entry. Tests include directed edges, reciprocal edges, repeated edges, self-loops, and removal of a vertex with both incoming and outgoing edges. Compare adjacency counts by vertex rather than relying on hash-map iteration order.
Kotlin example and implementation choices
The HashMap stores MutableList<String> adjacency entries. addVertex assigns a new list, so calling it twice discards that vertex's previous outgoing entries. addEdge expects existing endpoints under the shared contract. Removal filters all incoming references. The val map binding prevents rebinding the property, not mutation of its contents, so the teaching class remains structurally mutable through that public map.
Complete implementation
class Graph(val undirected: Boolean = true) {
val adjacencyList = HashMap<String, MutableList<String>>()
fun addVertex(vertex: String) {
adjacencyList[vertex] = mutableListOf()
}
fun addEdge(source: String, destination: String) {
adjacencyList.getValue(source).add(destination)
if (undirected) {
adjacencyList.getValue(destination).add(source)
}
}
fun removeVertex(vertex: String) {
adjacencyList.remove(vertex)
for (edges in adjacencyList.values) {
edges.removeAll { v -> v == vertex }
}
}
}
Continue in Kotlin
Open Implement a Graph for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Kotlin example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Kotlin interview preparation guide connects these language choices with further practice and the cross-language operation reference.