Sunday, November 01, 2009 6:43 PM,

A student writes:



	 Prof Patt,
	 
	 I am having trouble understand where the names are going to be stored 
	 in the program and I just do not understand the linked-list at all.
	 I understand how I am going to print the name and the room number, but 
	 finding it I just don't understand. Apologize for the inconvenience I 
	 think I am just missing something.
	 <<name withheld to protect the student who wonders where the data is>>



I am not sure where the student is having difficulty, which is why once again 
I ask students to please see a TA (or me) during office hours where a few 
questions by the TA (or me) can better pin point the problem.  Email does have 
that disadvantage.

Nonetheless, I will try.  I think there are two separate problems going on
here: (a) what is a linked list, and (b) where is it in memory.

A linked list is what computer scientists call an example of "an abstact data 
type." "Abstract" because it provides the information in a form that allows 
that information to be accessed without even knowing (or caring) exactly where 
each piece of data is stored.

There are many other abstract data types that you will encounter in your 
studies.  A family tree, for example, where each person has a mother and a 
father, and so one can find out things like how many grandchildren a person 
has without knowing exactly where the individual pieces of information is 
stored.

In the case of a linked list, what is relevant is that all the elements are 
connected so that one can access all the elements by following the pointers 
even if one does not know exactly where in memory the elements are stored.

For example, in the statement of program 3, we show an example of a linked 
list wherein x3300 contains the address of the first element, in this case 
x4000.  So, the first element consists of locations x4000, x4001, x4002.
Suppose the first element was stored at location x4807.  Then the contents of 
x3300 would be x4807, and the contents of x4807 would be x4100, because the 
first element must "point" to the second element.  x4808 would contain
x4025 and x4809 would contain x4050.

The point is a program can allow access to all the elements without the 
programmer knowing where those elements are when he/she writes the program.
The program finds the elements by following the pointers!

In the example shown in the problem, there are two elements in the linked 
list, each consisting of 3 words.  The first word points to the next element, 
the second word points to the sequentially stored name, and the third points 
to the sequentially stored room number.  These items can be stored anywhere 
without presenting any problem because the pointers contain the necessary 
addresses.

More on this in class tomorrow.
 
Second is the matter of where in memory the linked list is.  Answer, which I 
hope is clear from the discussion above: wherever it happens to be.  AND the 
programmer need not be concerned about that when he/she writes the program.
The linked list is NOT part of the program.  It is the data that program 
operates on.  The only thing the programmer has to know is that x3300 contains 
the starting address of the first element.  From this, the program can find 
the first element, and from the first element the program can find the second 
element, ...  The program has reached the end of the linked list when the 
pointer contains x0000.

Question for you: How many elements in the linked list if x3300 contains 
x0000?

Hope this helps.

Yale Patt