educative.io

Educative

Confusion about circular linked list and storing linked list in memory

A reader asked us the following question:

The first question asks whether it can be stored in contiguous memory, and it’s not. LLs can be stored at random memory spaces. Also, a circular LL does not have to have the tail pointing to the first node, it can still be circular pointing to the element before it, or any others as long as it does not point to itself

Hi,

This is Maida Ijaz from Educative. The answer of question 1 should be “true”. Since, it is possible by some stroke of luck that the memory manager allocates all nodes in contiguous memory locations, even though all allocations would be done separately. This is very unlikely, but there is no rule that says that linked list nodes will never be allocated contiguously.

About the circular linked list, here is the definition from a popular textbook by Goodrich and Tamassai:

The nodes of a circular linked list are linked into a cycle. Traversing nodes of a circular linked list from any node following next pointers, we will eventually visit all nodes and cycle back to node from where we started.

It is not possible for this definition to be true unless the tail points to the head and not any other node.

Best Regards,

Maida| Developer Advocate

educative.io