CS115 Lab: C++ Simple Linked Lists


Highlights of this lab:

In this lab,  you will:

Lab Exercise:


Advantage of Linked Lists.

Linked lists are used to store collections of data. But we've already seen a mechanism for doing this. i.e. A collection of data can be stored in array. However, an array is a sequential structure meaning that it is a group of memory elements located in contiguous locations (located next to one another in a group). You need to know how many elements there will be and you need to allocate a block of memory for them.

When you don't know how many elements there will be, and if elements need to be inserted and deleted frequently, it is better to use a linked list. This is because each element for a linked list is created as needed and can be stored anywhere in the free memory space - the elements in the list do not have to be stored in contiguous locations.

Each element in a linked list is referred to as a node. In a simple singly linked list, each element has two fields:

In this lab, a node is defined by the following class (called ListElement):
class ListElement
{
  private:    
   int datum;
   ListElement* next;
    
  public:
   ListElement (int, ListElement*);
   
   int getDatum () const;
   ListElement const* getNext () const;
}

A couple of notes on linked lists are:

The following diagram illustrates a simple singly linked list.

In this lab, we use a class to create a linked list. The following is the our LinkedList.h file that contains:

// LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cstdlib>
#include <iostream>
using namespace std;

class LinkedList;  // needed for friend line below

class ListElement
{
  private:    
   int datum;
   ListElement* next;
    
  public:
   ListElement (int, ListElement*);
   
   int getDatum () const;
   ListElement const* getNext () const;

   friend class LinkedList;  // gives LinkedList access to datum and next
};


class LinkedList
{
  private:
   ListElement* head;

  public:
   LinkedList ();
   
   void insertItem (int);
   void makeList ();
   void appendItem (int);
   void deleteItem (int);
   void printList ();
};
#endif

Operations on Linked Lists.

What follows here, are very rough algorithms on the basic operations that you would perform on a linked list. In actually implementing list operations, you would have to consider conditions such as: Is the list empty? What happens if I get to the null pointer and haven't found a data member that is supposed to be in the list? The algorithms here are just to provide you with an overview of the concepts involved in simple operations.

Lab Exercise:


This page last modified:
Tuesday, 12-Nov-2013 14:59:45 CST

CS Dept Home Page
CS Dept Class Files
CS115 Lab Files

Copyright: Department of Computer Science, University of Regina.