Expert: Joseph Moore - 9/5/2009

Question
Create a structure that has one variable called value and one pointer to the list (making it a linked list). Prompt for 5 values from the keyboard as input and store them in the linked list. Print out the current contents of the list. Allow the user to add one more value to the linked list, and print the contents of the list again.

I have messed with this for about a day and a half now, read a whole lot of source material, but it's for an online class and I dont even know where to start. I am most definitely not cut out for c programming, itleast not the self taught variety.

Answer
Hi, Jeff.

Don't give up just yet.  I firmly believe that anyone can learn to program, some people just figure it out faster/more easily than others.  It doesn't matter if it takes you a bit longer to understand the way programming works, you can still figure it out.

Linked lists are a fundamental data structure in programming.  They are easy to implement and handy for storing an unknown number of items.

The basic concept behind a linked list is simple.  A basic linked list consists of a head (the starting node), and some number of nodes.  Each node can link to one (or two, if it's a doubly-linked list, but I'll get to that in a minute) other node.  You traverse the list by starting at the head, and simply moving down the list of nodes until you run out of nodes.  Typically, all nodes in a linked list are dynamically allocated (including the head node).  This is how you can tell if the list has anything in it at all (head node will be NULL), and this is how you can find the end of the list (next node will be NULL).

The basic structure of a node looks something like this (in pseudo-code):

   Node
   {
       data
       Node* nextNode
   }

The data can be whatever it needs to be.  In your case, it will be a simple integer (most often the case when teaching linked lists, actually).  The most important part of the linked list is the Node pointer that points to the next node.  It is always initialized to NULL, indicating that this is the last node in the list.  So, when creating a new node, you'd do something like this (in pseudo-code):

   Node newNode
   newNode.data = myData
   newNode.nextNode = NULL

To iterate through the list, you simply start at the head and move until you find a node who's nextNode data is NULL.  To print the whole list, you'd do something like this (in pseudo-code):

   Node* currentNode = headNode
   while (currentNode)
   {
       print(currentNode.data)
       currentNode = currentNode.nextNode
   }

Notice how the end-of-list case is actually the terminating condition for the loop, because once a NULL pointer is reached (NULL being 0), the while conditional will evaluate to false.  This even covers cases where the list is completely empty, so the headNode value would be NULL.

This type of list is called a singly-linked list, which means that you have a pointer to one side of the list, either the head or tail (tail being the end of the list), and each node points to one other node, either the next or previous node (depending if you start at the head of the list or the tail).  You can see that, whether you start at the tail and move through all previous nodes or start at the head and move through all next nodes, the structure is really identical.

There is another kind of list called a doubly-linked list.  Often times, doubly-linked lists are easier to deal with, actually.  The doubly-linked list is a list in which the nodes contain pointers to both the next and the previous nodes.  Often times you will store both the head and the tail of the list so that you can iterate through the list in either direction, from either side.  Insertion and removal operations are much easier to write in doubly-linked lists, and often times, if you use a list, it will be a doubly-linked list.  When first learning lists, though, you start with the singly-linked list and try to understand its principles.

OK, I think I have given you enough information to give this a try.  Please write the program in question and send me what you come up with as a followup.  I will look it over and help you with anything that isn't working properly.  If you have any further questions, don't hesitate to ask, also.  I'm here to help. :)