GraphLinkedList 🌐
Description:
A GraphLinkedList represents a directed graph using linked lists for each node. Each linked list contains all the nodes connected by edges to the head node. This structure is efficient for sparse graphs and reduces memory usage compared to an adjacency matrix.
Pros & Cons:
Using this data structure has several benefits:
Memory Efficient: Only stores edges that exist, making it suitable for sparse graphs.
Dynamic Structure: Adding and removing nodes or edges can be done efficiently with linked lists.
It also has some drawbacks:
Slower Edge Lookup: Checking if an edge exists can take linear time O(n) due to traversal of the linked list.
Complexity: Managing linked lists can be more complex than using a matrix for certain operations.
1. Adding Nodes:
The add function inserts a new node into the graph by creating a linked list for the node, which will hold its connected nodes as edges.
0
1
2
3
4
5
6
7
8
9
10
11
add(node: T) {
// Add the node to the list of nodes.
this.nodes.push(node);
// Create a new linked list with the new node as head.
const newList = new LinkedList({content: node} as LinkedListNode<T>);
// Push that to the array of linked lists.
this.list.push(newList);
}
2. Adding Edges:
The addEdge function creates a directed edge from one node to another by adding the destination node to the linked list of the source node.
0
1
2
3
4
5
6
7
8
9
10
11
addEdge(from: T, to: T) {
for (let index = 0; index < this.list.length; index++) {
// Find the node that I want to add an edge from.
if(this.list[index].head?.content === from) {
// Add the node to that array list.
this.list[index].prepend({content: to} as LinkedListNode<T>);
return;
}
}
}
3. Removing Edges:
The removeEdge function removes an edge between two nodes by deleting the destination node from the linked list of the source node.
0
1
2
3
4
5
6
7
8
9
removeEdge(from: T, to: T) {
for (let index = 0; index < this.list.length; index++) {
// Find the node that I want to add an edge from.
if(this.list[index].head?.content === from) {
this.list[index].delete(to);
}
}
}
4. Showing All Edges:
The showEdges function displays the graph by printing each node and the nodes it is connected to, represented by their linked lists.
0
1
2
3
4
5
6
7
showEdges() {
for (let index = 0; index < this.list.length; index++) {
const linkedList = this.list[index];
console.log(linkedList.toArray().map(node => node.content).join(' --> '));
}
}
5. Removing Nodes:
The remove function removes a node and all its edges from the graph, as well as any references to it in other nodes' linked lists.
0
1
2
3
4
5
6
7
8
9
10
remove(nodeToRemove: T) {
// Filter from the nodes and from the array of Linked list the one that we want to remove.
this.nodes = this.nodes.filter(node => node !== nodeToRemove);
this.list = this.list.filter((node) => node.head?.content !== nodeToRemove);
for (let index = 0; index < this.list.length; index++) {
if(this.list[index].contains(nodeToRemove))
this.list[index].delete(nodeToRemove);
}
}
6. Checking for an Edge:
The checkEdge function checks if a directed edge exists between two nodes by searching the linked list of the source node.
0
1
2
3
4
5
6
7
8
9
10
11
12
checkEdge(from: T, to: T): boolean {
for (let index = 0; index < this.list.length; index++) {
// Find the node that I want to add an edge from.
if(this.list[index].head?.content === from) {
// Add the node to that array list.
this.list[index].contains(to);
}
}
return false;
}
7. Removing All Edges from a Node:
The removeAllEdges function clears all edges from the specified node by clearing its linked list.
0
1
2
3
4
5
6
7
removeAllEdges(from: T) {
for (let index = 0; index < this.list.length; index++) {
if(this.list[index].head?.content === from)
this.list[index].clear();
}
}
Testing the Implementation
Let's see how this graph with linked lists works with some example operations:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const matrix = new GraphLinkedList<string>();
matrix.add("A");
matrix.add("B");
matrix.add("C");
matrix.add("D");
matrix.add("E");
matrix.add("F");
matrix.addEdge("A", "B");
matrix.addEdge("A", "C");
matrix.addEdge("B", "D");
matrix.addEdge("C", "D");
matrix.addEdge("D", "C");
matrix.addEdge("D", "E");
matrix.addEdge("E", "F");
matrix.showEdges();
matrix.removeAllEdges("A");
matrix.showEdges();
matrix.addEdge("A", "B");
matrix.addEdge("A", "C");
matrix.showEdges();
matrix.removeEdge("A", "B");
matrix.showEdges();
matrix.remove("D");
matrix.showEdges();
Console Output Example
This is an example of what you should see in the console:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
** Adds nodes: A,B,C,D,E,F.
** Add edge A --> B.
** Add edge A --> C.
** Add edge B --> D.
** Add edge C --> D.
** Add edge D --> C.
** Add edge D --> E.
** Add edge E --> F.
** Show all added edges matrix.
A --> B --> C
B --> D
C --> D
D --> C --> E
E --> F
F
** Remove all edges of A and show the edges matrix.
A
B --> D
C --> D
D --> C --> E
E --> F
F
** Add edge A --> B.
** Add edge A --> C.
A --> B --> C
B --> D
C --> D
D --> C --> E
E --> F
F
** remove edge A --> B.
A --> C
B --> D
C --> D
D --> C --> E
E --> F
F
** Remove node D.
A --> C
B
C
E --> F
F
Complete GraphLinkedList Implementation
Here’s the complete implementation for the GraphLinkedList class, using the LinkedList.ts:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import { LinkedList, LinkedListNode } from "./linkedList";
export class GraphLinkedList<T> {
nodes: T[];
list: LinkedList<T>[];
constructor() {
this.nodes = [];
this.list = [];
}
add(node: T) {
// Add the node to the list of nodes.
this.nodes.push(node);
// Create a new linked list with the new node as head.
const newList = new LinkedList({content: node} as LinkedListNode<T>);
// Push that to the array of linked lists.
this.list.push(newList);
};
remove(nodeToRemove: T) {
// Filter from the nodes and from the array of Linked list the one that we want to remove.
this.nodes = this.nodes.filter(node => node !== nodeToRemove);
this.list = this.list.filter((node) => node.head?.content !== nodeToRemove);
for (let index = 0; index < this.list.length; index++) {
if(this.list[index].contains(nodeToRemove))
this.list[index].delete(nodeToRemove);
}
}
addEdge(from: T, to: T) {
for (let index = 0; index < this.list.length; index++) {
// Find the node that I want to add an edge from.
if(this.list[index].head?.content === from) {
// Add the node to that array list.
this.list[index].prepend({content: to} as LinkedListNode<T>);
return;
}
}
}
checkEdge(from: T, to: T): boolean {
for (let index = 0; index < this.list.length; index++) {
// Find the node that I want to add an edge from.
if(this.list[index].head?.content === from) {
// Add the node to that array list.
this.list[index].contains(to);
}
}
return false;
}
removeAllEdges(from: T) {
for (let index = 0; index < this.list.length; index++) {
if(this.list[index].head?.content === from)
this.list[index].clear();
}
}
removeEdge(from: T, to: T) {
for (let index = 0; index < this.list.length; index++) {
// Find the node that I want to add an edge from.
if(this.list[index].head?.content === from) {
this.list[index].delete(to);
}
}
}
showEdges() {
for (let index = 0; index < this.list.length; index++) {
const linkedList = this.list[index];
console.log(linkedList.toArray().map(node => node.content).join(' --> '));
}
};
}