Data structures and Algorithms

Course Code: CoSc-2083

Chapter 3: Linked Lists Hand-out

1.1 Structures

Structures are aggregate data types built using elements of primitive data types.

Structure is defined using the struct keyword:

E.g. struct Time

{
int hour;
int minute;
int second;
};

The struct keyword creates a new user defined data type that is used to declare
variables of an aggregate data type.

Structure variables are declared like variables of other types.

Syntax: struct <structure tag> <variable name>;

E.g. struct Time timeObject,

struct Time *timeptr;

3.1.1 Accessing Members of Structure Variables

The Dot operator (.): to access data members of structure variables.

The Arrow operator (->): to access data members of pointer variables pointing to the structure.

E.g. Print member hour of timeObject and timeptr.

cout<< timeObject.hour; or

cout<<timeptr->hour;

TIP: timeptr->hour is the same as (*timeptr).hour.

The parentheses is required since (*) has lower precedence than (.).

1
3.1.2. Self-Referential Structures

Structures can hold pointers to instances of themselves.

struct list{
char name[10];
int count;
struct list *next;
};

3.2 Array

An array is a collection of memory locations which allows storing homogeneous elements. It is

an example for linear data structure.

Advantages:

 Reduces memory access time, because all the elements are stored sequentially. By
incrementing the index, it is possible to access all the elements in an array.
 Reduces no. of variables in a program.
 Easy to use for the programmers.

Disadvantages:

 Wastage of memory space is possible. For example: Storing only 10 elements in a 100
size array. Here, remaining 90 elements space is waste because these spaces can’t be
used by other programs till this program completes its execution.
 Storing heterogeneous elements are not possible.

3.3 Linked List

 Some demerits of array, leads us to use linked list to store the list of items. These are,
1. It is relatively expensive to insert and delete elements in an array.
2. Array usually occupies a block of memory space, one cannot simply double or
triple the size of an array when additional space is required. (For this reason,
arrays are called “dense lists” and are said to be “static” data structures.)

 A linked list, or one-way list, is a linear collection of data elements, called nodes, where
the linear order is given by means of pointers. That is, each node is divided into two
parts:
 The first part contains the information of the element i.e. INFO or DATA.
 The second part contains the link field, which contains the address of the next
node in the list.
NODE
INFO LINK
2
  The linked list consists of series of nodes, which are not necessarily adjacent in memory.
 A list is a dynamic data structure i.e. the number of nodes on a list may vary
dramatically as elements are inserted and removed.
 The pointer of the last node contains a special value, called the NULL pointer, which is
any invalid address. This NULL pointer signals the end of list.
 The list with no nodes on it is called the empty list or null list.

Example: The linked list with 4 nodes.

START
OR 7 5 8 9
HEAD

Types of Linked Lists:

a) Singly Linked List

b) Circular Linked List
c) Two-way or doubly linked lists
d) Circular doubly linked lists

Advantages of Linked List

1. Linked List is dynamic data structure; the size of a list can grow or shrink during the program
execution. So, maximum size need not be known in advance.
2. The Linked List does not waste memory
3. It is not necessary to specify the size of the list, as in the case of arrays.
4. Linked List provides the flexibility in allowing the items to be rearranged.

What are the pitfalls encountered in single linked list?

1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose
link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.

3.3.1 Singly-linked list

The simplest kind of linked list is a singly-linked list (or slist for short), which has one link per
node. This link points to the next node in the list, or to a null value or empty list if it is the final
node.

A singly linked list containing three integer values

Basic Operations on Linked Lists

3
 1. Insertion
a. At first
b. At last
c. At a given location (At middle)
2. Deletion
a. First Node
b. Last Node
c. Node in given location or having given data item
3. Find / Search a item in the list
4. Displaying items in the list

3.3.1.1 Creating Linked Lists in C++

A linked list is a data structure that is built from structures and pointers. It forms a chain of
"nodes" with pointers representing the links of the chain and holding the entire thing together.
A linked list can be represented by a diagram like this one:

This linked list has four nodes in it, each with a link to the next node in the series. The last node
has a link to the special value NULL, which any pointer (whatever its type) can point to, to show
that it is the last link in the chain. There is also another special pointer, called Start (also called
head), which points to the first link in the chain so that we can keep track of it.

3.3.1.2. Defining the data structure for a linked list

The key part of a linked list is a structure, which holds the data for each node (the name,
address, age or whatever for the items in the list), and, most importantly, a pointer to the next
node. Here we have given the structure of a typical node:
struct node
{ char name[20]; // Name of up to 20 letters
int age
float height; // In metres
node *nxt;// Pointer to next node
};
struct node *start_ptr = NULL;

The important part of the structure is the line before the closing curly brackets. This gives a
pointer to the next node in the list. This is the only case in C++ where you are allowed to refer
to a data type (in this case node) before you have even finished defining it!

4
We have also declared a pointer called start_ptr that will permanently point to the start of the
list. To start with, there are no nodes in the list, which is why start_ptr is set to NULL.

3.3.1.3 Adding a node to the list

The first problem that we face is how to add a node to the list. For simplicity's sake, we will
assume that it has to be added to the end of the list, although it could be added anywhere in
the list (a problem we will deal with later on).

Firstly, we declare the space for a pointer item and assign a temporary pointer to it. This is done
using the new statement as follows:

temp = new node;

We can refer to the new node as *temp, i.e. "the node that temp points to". When the fields of
this structure are referred to, brackets can be put round the *temp part, as otherwise the
compiler will think we are trying to refer to the fields of the pointer. Alternatively, we can use
the arrow pointer notation.

That's what we shall do here.

Having declared the node, we ask the user to fill in the details of the person, i.e. the name, age,
address or whatever:

cout << "Please enter the name of the person: ";

cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;

The last line sets the pointer from this node to the next to NULL, indicating that this node, when
it is inserted in the list, will be the last node. Having set up the information, we have to decide
what to do with the pointers. Of course, if the list is empty to start with, there's no problem -
just set the Start pointer to point to this node (i.e. set it to the same value as temp):
if (start_ptr == NULL)
start_ptr = temp;

The full code for adding a node at the start of the list is shown below, in its own little function:

5
 void add_node_at_first ()
{
node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data

temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
// Set up link to this node
temp->nxt=start;
start=temp;
}
It is harder if there are already nodes in the list and we want to add nodes at the end of the list.
In this case, the secret is to declare a second pointer, temp2, to step through the list until it finds
the last node.

temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{
temp2 = temp2->nxt; // Move to next link in chain
}

The loop will terminate when temp2 points to the last node in the chain, and it knows when this
happened because the nxt pointer in that node will point to NULL. When it has found it, it sets
the pointer from that last node to point to the node we have just declared:

temp2->nxt = temp;

6
The link temp2->nxt in this diagram is the link joining the last two nodes. The full code for adding
a node at the end of the list is shown below, in its own little function:

void add_node_at_end ()
{ node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data

temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;

// Set up link to this node

if (start_ptr == NULL)
start_ptr = temp;
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{
temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
}

3.3.1.4. Displaying the list of nodes

Having added one or more nodes, we need to display the list of nodes on the screen. This is
comparatively easy to do. Here is the method:
1. Set a temporary pointer to point to the same thing as the start pointer.
2. If the pointer points to NULL, display the message "End of list" and stop.
3. Otherwise, display the details of the node pointed to by the start pointer.
4. Make the temporary pointer point to the same thing as the nxt pointer of the node it is
currently indicating.
5. Jump back to step 2.

7
The temporary pointer moves along the list, displaying the details of the nodes it comes across.
At each stage, it can get hold of the next node in the list by using the nxt pointer of the node it is
currently pointing to. Here is the C++ code that does the job:
temp = start_ptr;
do
{ if (temp == NULL)
cout << "End of list" << endl;
else
{ // Display details for what temp points to
cout << "Name : " << temp->name << endl;
cout << "Age : " << temp->age << endl;
cout << "Height : " << temp->height << endl;
cout << endl; // Blank line

// Move to next node (if present)

temp = temp->nxt;
}
} while (temp != NULL);

Check through this code, matching it to the method listed above. It helps if you draw a diagram
on paper of a linked list and work through the code using the diagram.

3.3.1.5. Inserting node at a given position

One thing you may need to do is to navigate through the list, with a pointer that moves
backwards and forwards through the list, like an index pointer in an array. This is certainly
necessary when you want to insert or delete a node from somewhere inside the list, as you will
need to specify the position.

Inserting a node at any position in the list

The full code for adding a node at a given position is shown below, in its own little function:

Void insert_node_at_position()

Node *temp,*temp2;

Temp=new node;

Get_details_of(temp)// should be defined to accept the data of the node.

cout<<"Enter the position to insert the node:\n";

cin>>pos;

temp2=start_ptr;
8
for(int i=1;i<pos-1; i++)

temp2=temp2->next;

temp->next = temp2->next;

temp2->next = temp;

1.3.1.6. Deleting a node from the list

When it comes to deleting nodes, we have three choices: Delete a node from the start of the
list, delete one from the end of the list, or delete one from somewhere in the middle. For
simplicity, we shall just deal with deleting one from the start or from the end.

When a node is deleted, the space that it took up should be reclaimed. Otherwise the computer
will eventually run out of memory space. This is done with the delete instruction:

delete temp; // Release the memory pointed to by temp

However, we can't just delete the nodes willy-nilly as it would break the chain. We need to
reassign the pointers and then delete the node at the last moment. Here is how we go about
deleting the first node in the linked list:

temp = start_ptr; // Make the temporary pointer

// identical to the start pointer

Now that the first node has been safely tagged (so that we can refer to it even when the start
pointer has been reassigned), we can move the start pointer to the next node in the chain:
start_ptr = start_ptr->nxt; // Second node in chain.

9
 delete temp; // Wipe out original start node

Here is the function that deletes a node from the start:

void delete_start_node()
{
node *temp;
temp = start_ptr;
start_ptr = start_ptr->nxt;
delete temp;
}

Deleting a node from the end of the list is harder, as the temporary pointer must find where the
end of the list is by hopping along from the start. This is done using code that is almost identical
to that used to insert a node at the end of the list. It is necessary to maintain two temporary
pointers, temp1 and temp2. The pointer temp1 will point to the last node in the list and temp2 will
point to the previous node. We have to keep track of both as it is necessary to delete the last
node and immediately afterwards, to set the nxt pointer of the previous node to NULL (it is now
the new last node).
1. Look at the start pointer. If it is NULL, then the list is empty, so print out a "No nodes to
delete" message.
2. Make temp1 point to whatever the start pointer is pointing to.
3. If the nxt pointer of what temp1 indicates is NULL, then we've found the last node of the
list, so jump to step 7.
4. Make another pointer, temp2, point to the current node in the list.
5. Make temp1 point to the next item in the list.
6. Go to step 3.
7. If you get this far, then the temporary pointer, temp1, should point to the last item in the
list and the other temporary pointer, temp2, should point to the last-but-one item.
8. Delete the node pointed to by temp1.
9. Mark the nxt pointer of the node pointed to by temp2 as NULL - it is the new last node.

10
 Let's try it with a rough drawing. This is always a good idea when you are trying to understand
an abstract data type. Suppose we want to delete the last node from this list:

Firstly, the start pointer doesn't point to NULL, so we don't have to display a "Empty list, wise
guy!" message. Let's get straight on with step2 - set the pointer temp1 to the same as the start
pointer:

The nxt pointer from this node isn't NULL, so we haven't found the end node. Instead, we set
the pointer temp2 to the same node as temp1

and then move temp1 to the next node in the list:

Going back to step 3, we see that temp1 still doesn't point to the last node in the list, so we
make temp2 point to what temp1 points to

start_ptr

NULL

11

temp 2 temp1
 and temp1 is made to point to the next node along:

Eventually, this goes on until temp1 really is pointing to the last node in the list, with temp2
pointing to the penultimate node:

start_ptr

NULL

temp 2 temp1
Now we have reached step 8. The next thing to do is to delete the node pointed to by temp1

and set the nxt pointer of what temp2 indicates to NULL:

12
We suppose you want some code for all that! All right then ....

void delete_end_node()
{
node *temp1, *temp2;
if (start_ptr == NULL)
cout << "The list is empty!" << endl;
else
{ temp1 = start_ptr;
while (temp1->nxt != NULL)
{ temp2 = temp1;
temp1 = temp1->nxt;
}
delete temp1;
temp2->nxt = NULL;
}
}
The code seems a lot shorter than the explanation!

Now, the sharp-witted amongst you will have spotted a problem. If the list only contains one
node, the code above will malfunction. This is because the function goes as far as the temp1 =
start_ptr statement, but never gets as far as setting up temp2. The code above has to be adapted
so that if the first node is also the last (has a NULL nxt pointer), then it is deleted and the
start_ptr pointer is assigned to NULL. In this case, there is no need for the pointer temp2:

void delete_end_node()
{ node *temp1, *temp2;
if (start_ptr == NULL)
cout << "The list is empty!" << endl;
else
{ temp1 = start_ptr;
if (temp1->nxt == NULL) // This part is new!
{ delete temp1;
start_ptr = NULL;
}
else
{ while (temp1->nxt != NULL)
{ temp2 = temp1;

13
 temp1 = temp1->nxt;
}
delete temp1;
temp2->nxt = NULL;
} } }

Deleting a node at a given position :

The full code for deleting a node at a given position is shown below, in its own little function:
Void delete_at_position()
{
Node *temp,*temp2;
temp2=start_ptr;
cout<<"Enter the position to delete the node:\n";
cin>>pos;
for(int i=1;i<pos; i++)
{
temp = temp2;
temp2=temp2->next;
}
temp->next = temp2->next;
delete temp2;
}

3.3. 2. Doubly Linked Lists

That sounds even harder than a linked list! Well, if you've mastered how to do singly linked
lists, then it shouldn't be much of a leap to doubly linked lists

A doubly linked list is one where there are links from each node in both directions:

14
You will notice that each node in the list has two pointers, one to the next node and one to the
previous one - again, the ends of the list are defined by NULL pointers. Also there is no pointer
to the start of the list. Instead, there is simply a pointer to some position in the list that can be
moved left or right.

The reason we needed a start pointer in the ordinary linked list is because, having moved on
from one node to another, we can't easily move back, so without the start pointer, we would
lose track of all the nodes in the list that we have already passed. With the doubly linked list,
we can move the current pointer backwards and forwards at will.

3.3.2.1. Creating Doubly Linked Lists

The nodes for a doubly linked list would be defined as follows:

struct node{
char name[20];
node *nxt; // Pointer to next node
node *prv; // Pointer to previous node
};
node *current;
current = new node;
current->name = "Fred";
current->nxt = NULL;
current->prv = NULL;
We have also included some code to declare the first node and set its pointers to NULL. It gives
the following situation:

We still need to consider the directions 'forward' and 'backward', so in this case, we will need to
define functions to add a node to the start of the list (left-most position) and the end of the list
(right-most position).

3.3.2.2. Adding a Node to a Doubly Linked List

void add_node_at_leftend (string new_name)

{ // Declare a temporary pointer and move it to the start
node *temp = current;
while (temp->prv != NULL)
temp = temp->prv;
// Declare a new node and link it in

15
 node *temp2;
temp2 = new node;
temp2->name = new_name; // Store the new name in the node
temp2->prv = NULL; // This is the new start of the list
temp2->nxt = temp; // Links to current list
temp->prv = temp2;
}

void add_node_at_rightend ()
{ // Declare a temporary pointer and move it to the end
node *temp = current;
while (temp->nxt != NULL)
temp = temp->nxt;
// Declare a new node and link it in
node *temp2;
temp2 = new node;
temp2->name = new_name; // Store the new name in the node
temp2->nxt = NULL; // This is the new start of the list
temp2->prv = temp; // Links to current list
temp->nxt = temp2;
}

Here, the new name is passed to the appropriate function as a parameter. We'll go through the
function for adding a node to the right-most end of the list. The method is similar for adding a
node at the other end. Firstly, a temporary pointer is set up and is made to march along the list
until it points to last node in the list.

After that, a new node is declared, and the name is copied into it. The nxt pointer of this new
node is set to NULL to indicate that this node will be the new end of the list.
The prv pointer of the new node is linked into the last node of the existing list.
The nxt pointer of the current end of the list is set to the new node.

3.3.2.3. Deleting a Node from a Doubly Linked List

-
-
-

16