# Do we generally store the degree of each vertex in the linked list implementation? if not, why?

So generally speaking, when we implement the graph using linked list, do we store the degree of each edge too?

I'm asking this because if a question in my exam stated that we implemented this graph using linked list, do i assume we can access the degree of each edge in o(1) or not? this matters because it effects the time complexity of algorithms like finding if the graph has euler cycle which i should check the degree of each edge

and the exams are SAT type of questions so i can't write down anything i should just choose one of the 4 answers which for example says the time complexity of finding if the graph has euler path in linked list implementation

• It's up to you. Usually the degree isn't stored explicitly, but you can deduce the out-degree by comparing the "next" pointer to NULL. As for the convention used in your course, it's up to your professor, so you'll have to ask them. – Yuval Filmus Apr 3 '18 at 11:06
• @YuvalFilmus but is there any advantage in not storing the degree? for example why don't all the implementations store the degree in linked list and only some of them do? why not just store the degree as well? i mean the overhead is almost non existence because even if you delete an edge you only need to reduce the number of degree so its not a lot of overhead. – John P Apr 3 '18 at 11:41
• You just explained the advantage - the degree takes up space, and you also have to maintain it. In order to maintain it, you actually need a doubly linked list, which takes up even more space. You could store a lot of things at every node, such as a pointer to the first and the last node of the list. This might be helpful in some cases, but if it isn't, there is no need to. – Yuval Filmus Apr 3 '18 at 11:44
• @JohnP, right. Yup, $O(n)$. Doesn't affect the asymptotic space usage; might or might not be noticeable in practice. – D.W. Apr 3 '18 at 17:36