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.

Extra Resources

In case you are having trouble understanding Linked Lists, these resources may be helpful:


Lab Exercise:


This page last modified:
Monday, 21-Dec-2020 15:39:27 CST

CS Dept Home Page
CS Dept Class Files
CS115 Lab Files

Copyright: Department of Computer Science, University of Regina.