How do the different types of linked lists compare?

By Definition:  A linked list is a structured data object (struct) which relies on pointers between elements. In essence, a linked list creates a chain of "nodes" which utilize pointers/elements to identify where the next link in the chain is located.
 

There are several reason to learn the advantage and disadvantages of linked list, which will be discuss in detail later?  But for now lets learn how to crawl before we start running!!

Below is a simplistic representation of a linked list.

Note: Before analyzing this representation keep a few things in Mind.

1. Elem = Element (An address that pertains directly to that node/record )

2. Node = Each node contains two fields to store whatever element type the user wants and an additional field, which is not visible in this illustration, but points to the next node in the chain linking one node to the next.

But haven't we covered this in the Searching and Sorting Chapter; as well as, the Array Chapter. Furthermore, why is this technique any better than those.

Well yes, we can utilize Searching/Sorting and Arrays to do basically the same things but they are some major draw backs to those techniques. 

1. One problem we encounter with arrays is that we have to know exactly how much storage in Ram we need, what happens if you don't?

2. Arrays require us to allocate contiguous bytes of storage, what happens when we don't have it?

3. Searching/sorting will require us to sort (and resort) every time we wish to display by a different key, this will take a tremendous amount of effort.

Tables will resolve all of these problems for US, but they to have drawbacks...

Now that we have a basic understanding of linked list and some of the problems with using Arrays and Searching/Sorting let take a look at the different types of liked lists and how they compare and contrast.

Scenario: We often find ourselves in a situation that requires us to sort and resort a table of information.  Lets further assume that this information consisted of five individual employees (Employee ID, Name, Hourly Pay, and Department). 

Note: At this current time our table is sorted by employee ID. What if your boss told you to provide a report which list the employee's above by Name (alphabetically of course otherwise there is no use for this example).

Before we move on lets keep a few thinks in mind..

The variables in our program that would be associated with the above table would look as follows:       

Now since we have decided, or our boss has decided for us, to provide a report of the employees sorted by name we could simply add an additional field which would be the pointer to the next record in the table. Our table would know look like this...

Keep in mind what is actually happening, our objective is to display the list alphabetically by name, so we go to the first name in the list ("Andrew, John"), display the record information, and then look at the name in the nextname field ("Hemmingway, Joseph"), go to that record and display the information which will point us to the next record ("Lewis, Foster").  This will continue to display the names in alphabetical order until it reaches ("**No one**" or the null value).

Well this is interesting but how much storage will be need for a case like this? What additional steps do I need to consider when using a singly linked list? 

Well, each record would require 31 + 31 + 2 + 4 = 68-bytes of storage. We also need to include an additional 4 byte for the pointer field ("nextname" field in the example above)  which brings the grand total to 72.  Since we wish to store 5 records, we would require a total of 72 * 5 = 360 contiguous bytes of storage. We would also have to edit our structure template to look like this..

All told, like anything else, their are advantages and disadvantages to using a singly linked list...

Let me take this opportunity to expound on a few of the advantages above. Specifically, "Can order on any field" and "Need not search until list end if an element is not on the list".

Example: Suppose we decide to search for a particular name ("Lewis, Foster") in our linked list.  We could simply add some additional code that will take the following form.

Before beginning I should note that a Doubly Linked List implies that the list is linked in both direction, ergo this would allow us to search from bottom up or top down, one thing we were unable to perform with the singly linked list (without a little manipulation off course).

Not much, but how often do you really only have 5 records to maintain.  Realistically speaking, we would never go through all this trouble for five records.  The real world dictates that we maintains hundreds of thousands of records and in this case if we were to use the singly linked list it would be very time consuming to sort through them all to identify just one.

Note: For simplistic purpose we will continue to use the example provided above.

To accomplish this feet, we would also have to edit our structure template, it should appear as so...

Additionally, our record would require 31 + 31 + 2 + 4 + 4 + 4= 76-bytes of storage. Keep in mind 8 bytes will be allocated to the pointers ("nextname", "previousname" field in the example above). Since we wish to store 5 records, we would require a total of 76 * 5 = 380 contiguous bytes of storage.

In addition to the advantages and disadvantages of singly liked lists we will also add the following for Doubly Linked Lists.

References for Further Clarification

1. How to think like a computer scientist
2. Web Encyclopedia
3. Fortune City
4. http://encyclopedia.laborlawtalk.com/Linked_list#Doubly-linked_list

Helpful Questions

1. List Advantages and Disadvantages of Linked List (Singly and Doubly)?

     2.  I have five automobiles which I have listed in a spreadsheet as follows, set up the needed structure template (call it   struct automobilesemplate) to link the list alphabetically by author (make up string lengths as you see fit).

  struct automobilestemplate { char Make[30], Model[25];

  int year;

  float value;
  struct automobiletemplate * next; };
 

The manner in which I have set up the template requires:
30 + 25 + 2 + 4 + 4 = 65 bytes of storage per record, or 5 * 65 = 325 bytes of contiguous RAM allocation.

True and False

1. When using Linked list we need to allocate an additional 2 bytes for storage per pointer.

False, an additional 4 bytes of storage is needed for each pointer.

    2.  When utilized a singly linked list we can not specifically search for a particular name without having to search the entire table.

          False, using a singly linked list we can specific which record we are looking for and end the program without     searching any further.