[FIXED] Why are the nodes in my linked list graph going in reverse numerical order?

Issue

I am trying to create an adjacency list with linked list operations and my graph edges are showing reverse numerical order and not in order. For example, my output is Node 0: 3 2 1 instead of Node 0: 1 2 3

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

class AdjGraph:
    def __init__(self, data):
        self.data = data
        self.graph = [None] * self.data

    # Add edges
    def addEdge(self, vertice, edge):
        node = Node(edge)
        node.next = self.graph[vertice]
        self.graph[vertice] = node

    # Print the graph
    def printGraph(self):
        adj_list = "Adjacency List"
        for i in range(self.data):
            adj_list += "\n\nNode " + str(i) + ": "
            temp = self.graph[i]
            while temp:
                adj_list += str(temp.vertex) + " "
                temp = temp.next
        return adj_list

Solution

You'd need to make a small change to the addEdge function. Your current function basically grabs the existing node and attaches it to the new node, i.e the exact opposite of what we are looking for.

Before looking at the solution, take a look at what your code does. Let's Insert 0.

## graph[0] = None (since there are no nodes)
node = Node(edge) # Node { vertex: 0 }
node.next = self.graph[vertice] ## Node {vertex:0, next: None} since graph[0] is null right now
self.graph[vertice] = node ## graph[0] = Node {vertex: 0, next: None}

Now let's insert 1 -

node = Node(edge) ## Node { vertex: 1 }
node.next = self.graph[vertice]  ## Node { vertex: 1, next: { vertex: 0, next: None} } 
## Remember what we got in the previous insertion, graph[0] has the first node
## i.e -> 0
self.graph[vertice] = node

So, at every insertion, you get the newest element in the first place, hence your result is the exact opposite of what you are looking for.

Here's my solution to this (might not be perfect) -

class AdjGraph:
    def addEdge(self, vertice, edge):
        
        currNode = self.graph[vertice] # The existing node at specified index
        newNode = Node(edge)  # Creating a new node
        if currNode == None:  # If there are no elements in this node
            self.graph[vertice] = newNode 
            return
        
        while currNode != None: # Traversing
            if currNode.next == None:
                currNode.next = newNode # Attaching the New Node to the tail of the existing node
                break
            currNode = currNode.next

ag = AdjGraph(1)
ag.addEdge(0,0)
ag.addEdge(0,1)
ag.addEdge(0,2)
ag.addEdge(0,3)
print(ag.printGraph())
## Result
## Adjacency List
## Node 0: 0 1 2 3 

Answered By - Sreekesh Iyer

Answer Checked By - Willingham (PHPFixing Volunteer)