Highlights of this lab:

In this lab,  you will:

Lab Exercise:

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.

• Data member - contains the data
• Link member - contains the pointer to the next node
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;
};

```
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.
• Creating a List
```                  First create a new empty node.
Assign a data value to the data member of that node.
Set up a current-pointer to the first node.
Get a data value for the next node.
While more nodes to add
Create a new node.
Assign a data value to the new data member.
Set the current-pointer link member to this new node.
Bump the current-pointer to this new node.
Set the link member of the last node to NULL.
```
• Adding a Node
```                  Find the end of the list.
i.e. Set current-pointer to the head.
While current-pointer link member not NULL
bump the current-pointer.
Create a new empty node.
Assign a data value to the data member of that node.
Set the link member of the new node to NULL. (New tail.)
Set the current-pointer link member to this new node.
```
• Printing Nodes
```                  Set the current-pointer to the head node.
Until you hit a null pointer:
print the data member of the current node
bump the pointer to the next node.
```
• Inserting Nodes
This algorithm assumes that you want to insert a node into a list of ordered values. Let's say you have two values, 12 and 24. A new value of 14 should be inserted between these existing values so that the final list will contain the values 12, 14, and 24.
```
Get the value to insert.
Create a new node.
Assign a data value to the data member of that node.
Set a previous-pointer to NULL.
Set a current-pointer to the Head.
While the new data member > current-pointer value
Bump both pointers along to the next nodes.
i.e.
make the previous-pointer point to the current-node
change the current-pointer to point to the next node
Set the link member in the previous_pointer to the new node.
Set the link member of the new node to the node pointed
to by the current-pointer.
```
This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.
• Deleting Nodes.

This routine assumes that the item you are searching for is, in fact, in the list.

```          Get the data value to delete.
If the item is in the first node
Set a pointer to the node to be deleted.
Change the head pointer to the second node.
Else
Set the current-pointer to the Head.
Until the link in the current-pointer points to the item
bump the current-pointer to the next node
Set a pointer to the node to be deleted.
Change the link of the current-pointer
to the link of the item to be deleted.
Delete the node.
```
This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.

Lab Exercise:

 CS Dept Home Page CS Dept Class Files CS115 Lab Files

Copyright: Department of Computer Science, University of Regina.