Linked-List Basics

• Sometimes we would like store like-type things in a container (like arrrays).  However, we'd like the container to be "just as big" as it needs to be (no space wasted), so that the container grows/shrinks as we add/remove items from the container.

• The data structure which implements this behavior is the list.  Often lists are implemented as linked structures.  Hence the term linked-list.

• The fundamental element of the list is a node.  Nodes are defined as classes.  For example:

class myNode {

      int            i;

      myNode *next;

};

 

 

• According to the definition above, a myNode above has two fields (or attributes), an i field and a next field.  The next field is a pointer to a myNode, so we can chain several myNodes together to create a linked-list (see below).  Incidentally, the little box to the left is another myNodePtr object (usually called head) that keeps track of the first myNode in the chain.

• Because each myNode in the list keeps track of the next myNode, we can "walk" the list using a pointer to myNodes.  Suppose we have the type definition:  typedef myNode* myNodePtr;.  Then (given the linked-list illustrated above) we can declare a pointer, p, to "walk" the list and print each element as follows:

myNodePtr p;

p = head;

 

// walk the list until we get to the end

while (p != NULL) {

      cout << p->i << " ";

      p = p->next;

}

• Of course, we'd like to do a lot more with the list than just print it.  To work with these types of data structures we need a whole bunch of functions to manipulate them, including functions to:

  • Create lists

  • Insert elements into lists

  • Remove elements from lists

  • Compare two lists

  • Check to see if the list has elements in it, or not

  • Copy a list

  • Merge two lists together into a new one

  • Get rid of a list altogether

  • And perhaps more ....

• Under the software tab to this web site, you can find several examples for manipulating linked lists, including some of the functions listed above.