John F. Bergin               

Bellevue, WA

(425) 242-1394

John.F.Bergin@Comcast.net                            Resume

Word Formatted Resume (Right Click and "Save Target As")

Cover Letter                                                    White Papers                                            Code Examples

Senior Software Engineer                                                                                                                                                                                                          

Code Examples by John F. Bergin

    Linked Lists

    The following code samples demonstrate the use of Linked Lists.  For these examples, an array of integers is used as input for creating different linked lists.

    Linked Lists will be created using the C++ "list<>" class, a user defined C++ class, and a user defined C structure.

  // Use this array of integers as input for creating linked lists.

  int IntegerArray[] = {1,2,3,4,5,6,7,8,9,10};

    Linked List using the C++ list<> Class:

  // Create a C++ list<> class doubly linked list from the array of integers.

  list<int> IntegerList( IntegerArray, IntegerArray+ sizeof(IntegerArray) / sizeof(int) );

  // Find fifth integer from end using the "iterator" member type.

  list<int>::iterator FifthFromEnd = IntegerList.end();

  for ( int i=0; i<5; i++)

  {

      // Make sure list is big enough

      if ( FifthFromEnd == IntegerList.begin() )

          break;

      FifthFromEnd--;

  }

  // Print the Value.

  printf("5th integer from end = %i\n", *FifthFromEnd);

    Linked List using a User Defined C++ Class:

  // User Defined C++ Integer List Class - Singly Linked List of Integers

  class IntList

  {

      int ID;

      int Value;

      IntList* Head; // Pointer to Head of List

      IntList* Next; // Pointer to Next Record

    public:

      // Constructors

      IntList();

      IntList( int, int);

      // Member functions

      IntList* AddRecord(int, int);

      void print();

  };

  //

  // Comstructors

  //

  // Create list with default values.

  // Id = 1, Value = 1

  IntList::IntList()

  {

      ID = 1;

      Value = 1;

      Head = this;

      Next = NULL;

  }

  // Create list and specify the values.

  IntList::IntList(int id, int val)

  {

      ID = id;

      Value = val;

      Head = this;

      Next = NULL;

  }

  //

  // Member Functions

  //

  // Append a record to the end of the list.

  IntList* IntList::AddRecord(int id, int val)

  {

      IntList* newRec = new IntList[];

      newRec->ID = id;

      newRec->Value = val;

      newRec->Next = NULL;

      IntList* tempList = Head;

      while ( tempList->Next != NULL )

      {

          tempList = tempList->Next;

      }

      tempList->Next = newRec;

      return newRec;

  }

  // Print the entire list of integers,

  // separated by commas.

  void IntList::print()

  {

      IntList* newRec = Head;

      while( 1 )

      {

          printf("%i", newRec->Value);

          if ( newRec->Next == NULL)

              break;

          else

          {

              newRec = newRec->Next;

              printf(", ");

          }

      }

      printf("\n");

  }

    Code from Main Program:

  //

  // Build a list of integers.

  //

  // Initialize the list and create the first record

  // with default values Id=1 and Value=1.

  IntList MyIntegerList;

  // Add Records

  for ( int i=2; i<=10; i++ )

  {

      MyIntegerList.AddRecord( i, IntegerArray[i-1] );

  }

  //Print the list

  MyIntegerList.print();

  //

  // Build another list of integers but reverse the array.

  //

  // Initialize the list and create the first record,

  // but this time specify the values Id=1 and Value=10.

  IntList ReverseIntegerList(1,10);

  // Add Records

  int recID = 1;

  for ( int i=9; i<=1; i-- )

  {

      ReverseIntegerList.AddRecord( recID, IntegerArray[i-1] );

      recID++;

  }

  //Print the list

  ReverseIntegerList.print();

    Linked List using a User Defined C Structure:

  // C Structure for Singly Linked List of Integers

  struct IntList {

      int ID;

      int Value;

      IntList *Next;

  } typedef IntList;

  // Build a list of integers.

  IntList *IntegerList = new IntList[];  // Allocate memory on heap

  IntegerList->ID = 1;

  IntegerList->Value = IntegerArray[0];

  for (int i=2;i<=10;i++)

  {

      IntegerList->Next = new IntList[];

      IntegerList = IntegerList->Next;

      IntegerList->ID = i;

      IntegerList->Value = IntegerArray[i-1];

  }

  // Terminate the list.

  IntegerList->Next = NULL;

  // Function to return the nth element from the end of an integer list.

  IntList *ReturnNthElementFromEnd(IntList *IntegerList, int count)

  {

      // Make sure count is valid

      if ( count < 0 )

      {

          printf("ERROR - Invalid count - Less than zero...\n\n");

          return NULL;

      }

      IntList *DesiredElement = NULL;

      IntList *CurrentElement = IntegerList;

      int rec=0;

      //Increment Integer List until you get to 'count - 1'

      while ( rec < count - 1 )

      {

          // If list is smaller than 'count' elements, return NULL

          if ( CurrentElement->Next == NULL )

          {

              printf("ERROR - Invalid count - List not big enough...\n\n");

              return NULL;

          }

          CurrentElement = CurrentElement->Next;

          rec++;

      }

      DesiredElement = IntegerList;

      // Traverse to end of list

      while (CurrentElement->Next != NULL )

      {

          CurrentElement = CurrentElement->Next;

          DesiredElement = DesiredElement->Next;

      }

      return DesiredElement;

  }

____________________________

Copyright © 2010 by John F. Bergin.

Home