CIS3355: Business Data Structures
Fall, 2008
 

Topic 10.20: Declaring a Linked List and How it is Stored in RAM

    Lets begin by defining liked lists: a linked list is a structured data object which contains a pointer and is a programmer's solution to static (having to be declared ahead of time) variables in C++.  Below is a representation of what a linked list may look like:

    The most important component of declaring a linked list is the structure because it holds the all of the data and even more importantly, the pointer.  Below is an example of a structured data object (struct):

                struct pet

            { char name[20];  // Pet name up to 20 characters

               char type[10];  // Pet type up to 10 characters

               char owner[20];  // Pet owner up to 20 characters

                struct pet *next;  // Pointer to the next node

            };

            int main ()

        { struct pet pet[2] =   // enters values into the list

            {{"Spot", "Dog", "Sue"},

             {"Prince","Cat","Bob"}

             {"Bert", "Fish", "Tom"}},

            *First  // place where the link begins

Struct pet would require char(2)+char(2)+char(2)+*next(4) = 10 contiguous bytes of storage in ram for each record as shown below:

To link the list by name we would have to store the address of the first record in the location *first

Now we can link the rest of the list.  The way we would do this would be to set the *next value to the corresponding values that would be next on the list, but to instruct the system of when the list ends we would have to set *next to null for the last record in the list.  The following illustrates how that would work for our sample struct sorted by name as well as how it would be stored in RAM.

There are several ways to manipulate the records or nodes in the linked list.  We can add records/nodes, display the list of records/nodes, and delete the records/nodes, but that is beyond simply declaring the link. 

For more details on linked lists please visit the following sites:

http://www.pkirs.utep.edu/cis3355/

Creating Linked Lists in C++

HFT Online Forums - C++ Linked List

Linked List Tutorial

For a little more help use the following:

1.    Which of the following can be applied to the records/nodes in a linked list:

                a) deletion

                b) insertion

                c) display

                d) all of the above

                (answer: d) all of the above)

2.    What is the most important component of declaring a linked list and why?

            The structure data object because it contains the pointer.

3.    What must the last record/node pointer be set to:

            a) last

            b) done

            c) null

            d) finish     

            e) zero

                (answer: c) null)