LINKED LISTS NOTES

A STATIC data structure is one that is "allocated" or "reserved" when it is declared. This is fine when dealing with small numbers, but it is better practice to use a DYNAMIC data structure. An example of a dynamic data structure is a linked list.. Imagine a STRUCTURE of names. Instead of SIZING the structure at the start and reserving memory, we simply add records to the list as we need them.. This means that our list "grows" as we need it and does not use any more memory than it needs

Now take each "record" of that structure and locate it at a memory address somewhere.. This is our list.. To LINK it, we use an additional field in our structure that holds a POINTER.. This pointer gives us the location of the next record thus linking the list together.

To use a LINKED LIST, we use a POINTER variable that "points" to the first record of our linked list. This variable is usually called the head pointer.

In our example, Head Pointer = 011

To print the linked list, we start at the Head address. We print the first record then we "follow the links" to the next record…

To add records to our linked list, we simply "attach" a new record to the end of the list.

The linked list must have an end to it. To accomplish this, we fill the pointer field of the last record with NULL. This denotes that we are at the end of the list.