Click Here!
home account info subscribe login search FAQ/help site map contact us


 
Brief Full
 Advanced
      Search
 Search Tips
[an error occurred while processing this directive]
Previous Table of Contents Next


Steps

1.  Determining the linked list class
A linked list is an aggregated data type. Elements of a linked list can be of any type. In this example, we’ll consider only integer elements. A linked list starts with a pointer to the first element. If the linked list is empty, the first element is NULL as shown in Figure 4.6.


Figure 4.6  An empty linked list.


Elements of a linked list consist of data and a pointer to the next element in the list. The last element consists of its data and NULL pointer. An example of a linked list is shown in Figure 4.7.


Figure 4.7  A linked list.


A linked list as a data type needs the following operations: add, remove, and insert. In this example, we are going to implement only the add operation. The operation allows you to add a new element to the beginning of the list.
The following is the class declaration:
// file linkedli.h

#include <iostream.h>

// list elements
struct llink
{
  int elem;
  llink* nextelem;

};

// linked list
class linkedlist
{
private:

  llink* firstelem;
public:
    linkedlist(void);
    ~linkedlist(void);
    void AddElement (int elem1);
    void DisplayList(void);
};
2.  Defining and testing the class
The implementation of the class needs a constructor, an operation to add new elements, and an operation to display the list.
// file linkedli.cpp

#include "linkedli.h"
// constructor
linkedlist::linkedlist()
{
   firstelem=NULL;
}

// destructor
linkedlist::~linkedlist(void)
{
  // here should be a code
  // to free memory
}

// add new element
void linkedlist::AddElement(int elem1)
{
   llink* newlink= new llink;
   newlink->elem= elem1;  newlink->nextelem= firstelem;
   firstelem= newlink;
}

// Display list elements one by one
void linkedlist::DisplayList()
{
   llink* currentelem= firstelem;
   while (currentelem!= NULL)
   {
     cout << currentelem->elem << " - ";
     currentelem= currentelem->nextelem;
   }
   cout << "END" << endl;
}

To test the implementation, let’s write a program that adds a few elements to the list and then displays the list on the screen:
// file listtest.cpp

#include “linkedli.h”

int main()
{
  linkedlist TestList;

  TestList.AddElement(5);
  TestList.AddElement(54);
  TestList.AddElement(3);
  TestList.AddElement(25);

  TestList.DisplayList();

  return 0;
}

The program will display
25 - 3 - 54 - 5 - END

Comments

Now we can discuss details of the linked list implementation and the difference in using classes and structures.

We used a C++ structure to create a single element:

struct llink
{
  int elem;
  llink* nextelem;

};

The linked list element consists of two parts of different data types. Therefore, it was very convenient to combine them using the struct keyword. Remember that we can’t use arrays for creating a data aggregate of pieces of different data types. The first structure member handles the data (sometimes called satellite data). In our example, the data has an integer value but linked lists can maintain any type of data, for instance, pointer to image structures.

The second structure member provides a pointer to the next list element. Note that we use a kind of recursion because the pointer points to an element of the llink type that is defined by the structure. This is an important feature that makes C++ structures really powerful.

So far we have dealt with data and the data describes a linked list element. Do we need to extend it to a class? The answer is no; there is no need to add operations. Elements don’t need operations on themselves. There is no such thing as incrementing a list element or the addition of two elements. Even display functions should display the whole list rather than a separate element.

Because we want to use a common approach, we will leave the structure without moving it to a class. This is mostly a question of programming style. For historical reasons, we deal with structures if we deal with pure data and if there is no need of operations on this data.

Now we can consider the linked list itself. No doubt, it should be a class for several reasons.

First, we can encapsulate all data members. Fortunately we don’t need many of those. The important thing is that we have to define operations with this linked list. There are list elements involved in the operations; however, the elements are hidden from external objects.

Creating a linked list involves quite a bit of logic. In our design we decided that an empty list was just a NULL. It means that we reserve the space for the list on-the-fly while adding the elements. Therefore (if we were writing a real program), we have to destroy the memory items when we don’t need the elements.

These operations need a constructor and a destructor that are class member functions.

The last class elements we have to specify are the functions AddElement and DisplayList. The functions provide a necessary interface for the encapsulated data. We definitely need more functions and their creation is left as a good assignment for the reader.


Previous Table of Contents Next


Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.