How does a HEAD pointer end up pointing to the first node in a linked list?


Joined
Feb 20, 2022
Messages
5
Reaction score
0
The following code is snippet from a FIFO write/read model. The code works. I am only showing the write procedure. My questions are noted after the code snippet.


type Item; --Incomplete declaration type Ptr is access Item; type Item is record NextItem : Ptr; Data : integer; end record; variable Head : Ptr; procedure FIFO_WRITE(Data : in integer) is variable NewItem : Ptr; variable Node : Ptr; begin NewItem := new Item'(NextItem => Null, Data => Data); --allocate memory - point to where the Item is stored. if Head = null then --if the list is empty Head := NewItem; --claim the memory and initialise Root/Head to the claimed memory. else Node := Head; --start with Root node at the beginning of the list while Node.NextItem /= null loop --Go through linked list and search for --last/tail node. Node := Node.NextItem; end loop; Node.NextItem := NewItem; --store NewItem(Item) at the tail end of the list. end if; end;

I have a fundamental question. I have declared the variable HEAD to be of type Ptr. Then I check to see if HEAD = NULL. So, all I have done is declare the variable HEAD. How does that end up pointing to the first node in the list? How does the HEAD = NULL work? Is it that when you declare HEAD, that the NextItem of 'record' Item end up pointing to NULL by default? I haven't allocated memory to HEAD. Nothing. Just the declaration causes it to point to the first node in the list? Don't understand that.

Thanks.
 
Ad

Advertisements

Joined
Feb 20, 2022
Messages
5
Reaction score
0
Just want to clarify my question:

I understand what assignment to NULL means. My question is how does HEAD pointer work? All we have done is declare HEAD as a variable. How does it end up pointing to the first node in the list? We haven't allocated any memory to HEAD (i.e. we haven't made the assignment HEAD := new item'(Nextitem => NULL, data=data);). So, how does HEAD know where to point to?
 
Joined
Jan 30, 2023
Messages
71
Reaction score
2
The variable "Head" is assigned a value of "NewItem" only in the "if" block when the list is empty, i.e., "if Head = null". In this case, "Head" is assigned the memory address of the newly created "Item" object, which becomes the first node in the linked list. When a new item is added to the linked list, the "NextItem" field of the last node in the list is assigned the memory address of the newly created "Item" object, which becomes the new last node in the linked list. When "Head" is first declared, it is initially assigned a value of "null".
 
Ad

Advertisements

Joined
Feb 20, 2022
Messages
5
Reaction score
0
Great. Thanks very much. I was missing the point that when HEAD is first declared, it is initially assigned a value of NULL.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top