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 consists of two members.

Here is an example to show you how to use a STRUCT to define a node.
*   FileName: ~ftp/pub/class/170/ftp/cpp/llist.h
*   Purpose:  header file for llist.cpp
typedef int Element_Type;

struct Node;
typedef Node* Pointr;

struct Node
    Element_Type data_member;
    Pointr       link_member;

A doubly linked list would have a third member in each node to point to the previous node. The last node in any linked list contains a null pointer in the link member. This null pointer is used to determine the end of the list. The following diagram illustrates a simple singly linked list.

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:

CS Dept Home Page
CS Dept Class Files
CS115 Lab Files

Copyright: Department of Computer Science, University of Regina.