CODEWITHSUNDEEP
pythongraph
Boyang Zhang
Boyang Zhang

Reputation: 127

Why use a linked list instead of an array of nodes to build a graph

Below is the code I'm using for building a graph. It's pretty much copied from https://www.geeksforgeeks.org/graph-and-its-representations/. I read their code and built it in a way as I understood it and gave each edge a value cause I was planning to do an implementation of Dijkstra's after.

My question is: why implement the graph as an array of linked lists where all connections at a particular node are apart of that linked list vs just using an array of arrays where at each node all connections are objects inside of an array?

class adj_node:
    def __init__(self,vertex,value=None):
        self.vertex = vertex
        self.value = value
        self.next = None

class graph:

    def __init__(self,n):
        self.n = n
        self.graph = [None]*n

    def add_edge(self,src,dest,value=None):
        node = adj_node(dest,value)
        node.next = self.graph[src]
        self.graph[src]=node

        node = adj_node(src,value)
        node.next = self.graph[dest]
        self.graph[dest] = node

def print_graph(graph):
    for i,n in enumerate(graph.graph):
        linked_list = []
        while n!=None:
            linked_list.append(str(n.vertex))
            n = n.next
        print(f'Node {i} -> '+' -> '.join(linked_list))

g = graph(5)
g.add_edge(0,1,4)
g.add_edge(0,4,1)
g.add_edge(1,4,4)
g.add_edge(1,3,1)
g.add_edge(1,2,2)
g.add_edge(3,4,1)
g.add_edge(2,3,3)

print_graph(g)

Node 0 -> 4 -> 1
Node 1 -> 2 -> 3 -> 4 -> 0
Node 2 -> 3 -> 1
Node 3 -> 2 -> 4 -> 1
Node 4 -> 3 -> 1 -> 0

Upvotes: 2

Views: 1634

Answers (2)

CJP
CJP

Reputation: 51

Python is not the same as other languages, you ( programmer ) don't allocate memory for lists/arrays in advance. Python uses dynamic arrays. So the memory usage is very similar, perhaps negligible. With arrays you can use the insert/append or remove/pop functions to modify. As with most things, it depends what you want to do. They performance is the same if you are just appending.But linked lists are faster if you are making changes higher up in a larger number of nodes/list items. For element lookup the list is faster, but for search both perform the same.

Good information is here for more details: https://realpython.com/linked-lists-python/#understanding-linked-lists

Upvotes: 1

hardik24
hardik24

Reputation: 1058

If you will use array instead of linked list, you will have to allocate memory in advance, which definitely will not be memory efficient. So, one of the main reason to use linked list is efficient memory usage, where you add nodes as and when required.

Given that, it also depends on the use case. Suppose, If your primary query from the graph is to determine whether two points are directly connected, linked list will not be a good fit. So, in the end it depends on the use-case you want to fulfill, if you want it to be more memory efficient or if your use-case do not require direct access to edges then, linked list are better data structure to represent graph otherwise, array.

Upvotes: 2

Related Questions