MODULE 3

Linked List
• Learn about linked lists
• Become aware of the basic properties of linked lists
• Explore the append, insertion, traversal and deletion
operations on linked lists
• Learn and understand how to create a link list
template
• Know the existing list container in C++ STL
• Linked List ADT • Linked List Template
• Linked List Operations • Variations of Linked List
• Appending a Node • STL List Container
• Traversing the List
• Inserting a Node
• Deleting a Node
• Destroying the List
• A linked list is a series of connected
nodes, where each node is a data
structure.
• A linked list can grow or shrink in
size as the program runs
• A linked list can easily grow or
shrink in size.
• Insertion and deletion of nodes is
quicker with linked lists than with
vectors.
• Each node in a linked list contains one or more
members that represent data.
• In addition to the data, each node contains a
pointer, which can point to another node.
• A linked list is called "linked" because each
node in the series has a pointer that points to
the next node in the list.
• First you must declare a data structure that will be
used for the nodes. For example, the following struct
could be used to create a list where each node holds a
float:
struct ListNode
{
float value;
struct ListNode *next;
};
• The next step is to declare a pointer to serve as the
list head, as shown below.
ListNode *head;

• Once you have declared a node data structure and

have created a NULL head pointer, you have an empty
linked list.
• The next step is to implement operations with the list.
floatlist.h
class FloatList
Linked List Operations
{
private:
// Declare a structure for the list
struct ListNode
{
float value;
struct ListNode *next;
};

ListNode *head; // List head pointer

public:
FloatList() // Constructor
{ head = NULL; }
~FloatList(); // Destructor
void appendNode(float num);
void insertNode(float num);
void deleteNode(float num);
void displayList();
};
• To append a node to a linked list means to add the
node to the end of the list.
• The pseudocode is shown below. The C++ code
follows.
Algorithm:
Create a new node.
Store data in the new node.
If there are no nodes in the list
Make the new node the first node.
Else
Traverse the List to Find the last node.
Add the new node to the end of the list.
End If.
void FloatList::appendNode(float num)
{
ListNode *newNode, *nodePtr;
Append a Node
// Allocate a new node & store num
newNode = new ListNode;
newNode->value = num;
newNode->next = NULL;
// If there are no nodes in the list
// make newNode the first node
if (!head)
head = newNode;
else // Otherwise, insert newNode at end
{
// Initialize nodePtr to head of list
nodePtr = head;
// Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;
// Insert newNode as the last node
nodePtr->next = newNode;
} cout << “Input has been APPENDED!” << endl;
}
 Sample Program 1
// This program demonstrates a simple append
// operation on a linked list.
#include <iostream.h>
#include "FloatList.h”

void main(void)
{
FloatList List;

list.appendNode(2.5);
list.appendNode(7.9);
list.appendNode(12.6);
}
(This program displays no output.)
• The head pointer is declared as a global variable. head
is automatically initialized to 0 (NULL), which
indicates that the list is empty.
• The first call to appendNode passes 2.5 as the
argument. In the following statements, a new node is
allocated in memory, 2.5 is copied into its value
member, and NULL is assigned to the node's next
pointer.
newNode = new ListNode;
newNode->value = num;
newNode->next = nULL;
The next statement to execute is the following if statement.
if (!head)
head = newNode;

There are no more statements to execute, so control

returns to function main.
In the second call to appendNode, 7.9 is passed as the
argument. Once again, the first three statements in the function
create a new node, store the argument in the node's value
member, and assign its next pointer to NULL.
Since head no longer points to NULL, the else part of the if statement executes:
else // Otherwise, insert newNode at end
{
// Initialize nodePtr to head of list
nodePtr = head;
// Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;
// Insert newNode as the last node
nodePtr->next = newNode;
}
nodePtr is already at the end of the list, so the while loop
immediately terminates. The last statement, nodePtr-
>next = newNode; causes nodePtr->next to point
to the new node. This inserts newNode at the end of the list.
The third time appendNode is called, 12.6 is passed
as the argument. Once again, the first three statements
create a node with the argument stored in the value
member.
next, the else part of the if statement executes. As
before, nodePtr is made to point to the same node as
head.
Since nodePtr->next is not NULL, the while
loop will execute. After its first iteration, nodePtr will
point to the second node in the list.
The while loop's conditional test will fail after the first iteration
because nodePtr->next now points to NULL. The last
statement, nodePtr->next = newNode; causes
nodePtr->next to point to the new node. This inserts
newNode at the end of the list

The figure above depicts the final state of the linked list.
• The displayList member function traverses the list,
displaying the value member of each node. The following
pseudocode represents the algorithm. The C++ code for
the member function follows on the next slide.
Algorithm
Assign List head to node pointer.
While node pointer is not NULL
Display the value member of the node pointed to by node pointer.
Assign node pointer to its own next member.
End While.
 Traversing a List
void FloatList::displayList(void)
{
ListNode *nodePtr;
if (head==NULL)
cout << “The List is empty!” << endl;
else {
nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}}
}
 Sample Program 2
// This program calls the displayList member function.
// The funcion traverses the linked list displaying
// the value stored in each node.
#include <iostream.h>
#include "FloatList.h"

void main(void)
{
Output:
FloatList List; 2.5
list.appendNode(2.5); 7.9
list.appendNode(7.9);
list.appendNode(12.6); 12.6
list.displayList();
}
• Using the listNode structure again, the
pseudocode on the next slide shows an
algorithm for finding a new node’s proper
position in the list and inserting there.
• The algorithm assumes the nodes in the list
are already in order.
Algorithm:
Create a new node.
Store data in the new node.
If there are no nodes in the list
Make the new node the first node.
Else
Find the first node whose value is greater than or equal
the new value, or the end of the list (whichever is first).
Insert the new node before the found node, or at the end of
the list if no node was found.
End If.
The code for the traversal algorithm is shown below. (As before, num holds
the value being inserted into the list.)

// Initialize nodePtr to head of list

nodePtr = head;

// Skip all nodes whose value member is less

// than num.
while (nodePtr != NULL && nodePtr->value < num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

The entire insertNode function begins on the next slide.

void FloatList::insertNode(float num)
{
ListNode *newNode, *nodePtr, *previousNode;
Inserting a Node
// Allocate a new node & store Num
newNode = new ListNode;
newNode->value = num;

// If there are no nodes in the list

// make newNode the first node
if (!head)
{
head = newNode;
newNode->next = NULL;
}
else // Otherwise, insert newNode.
{
// Initialize nodePtr to head of list
nodePtr = head;
previousNode = NULL;
// Skip all nodes whose value member is less
// than num.
while (nodePtr != NULL && nodePtr->value < num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next; Continued on next slide…
}
Continued from previous slide. Inserting a Node

// If the new mode is to be the 1st in the list,

// insert it before all other nodes.
if (previousNode == NULL)
{
head = newNode;
newNode->next = nodePtr;
}
else
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
cout << “Input has been INSERTED!” << endl;
}
// This program calls the displayList member function.
// The function traverses the linked list displaying
// the value stored in each node.
#include <iostream.h>
#include "FloatList.h”

void main(void)
{
Output:
FloatList list; 2.5
// Build the list
list.appendNode(2.5);
7.9
list.appendNode(7.9);
list.appendNode(12.6);
10.5
// Insert a node in the middle
12.6
// of the list.
list.insertNode(10.5);

}
// Dispay the list
list.displayList(); Sample Program 3
In insertNode, a new node is created and the function argument is
copied to its value member. Since the list already has nodes stored
in it, the else part of the if statement will execute. It begins by
assigning nodePtr to head.
Since nodePtr is not NULL and nodePtr->value is less than
num, the while loop will iterate. During the iteration,
previousNode will be made to point to the node that nodePtr is
pointing to. nodePtr will then be advanced to point to the next
node.
Once again, the loop performs its test. Since nodePtr is not NULL
and nodePtr->value is less than num, the loop will iterate a
second time. During the second iteration, both previousNode and
nodePtr are advanced by one node in the list.
This time, the loop's test will fail because nodePtr is not less than
num. The statements after the loop will execute, which cause
previousNode->next to point to newNode, and
newNode->next to point to nodePtr.

If you follow the links, from the head pointer to the NULL, you will
see that the nodes are stored in the order of their value members.
• Deleting a node from a linked list requires
two steps:
• Remove the node from the list without breaking
the links created by the next pointers
• Deleting the node from memory
• The deleteNode function begins on the next
slide.
void FloatList::deleteNode(float num)
{ Deleting a Node
ListNode *nodePtr, *previousNode;
int found = 0;
// If the list is empty, do nothing.
if (!head){cout << “The list is empty!” << endl;
return; }

// Determine if the first node is the one.

if (head->value == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
found = 1;
}

Continued on next slide…

 Deleting a Node
Continued from previous slide.
else
{
// Initialize nodePtr to head of list
nodePtr = head;
previousNode = NULL;
// Skip all nodes whose value member is
// not equal to num.
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
// Link the previous node to the node after
// nodePtr, then delete nodePtr.
If (nodePtr !=NULL){
previousNode->next = nodePtr->next;
delete nodePtr;
cout << “Input has been DELETED!” << endl;
found = 1;}
}
if (found==0) cout << “Input not in the list!” << endl;
}
 Sample Program 4
// This program demonstrates the deleteNode member function
#include <iostream.h>
#include "FloatList.h“

void main()
{
FloatList list;

// Build the list

list.appendNode(2.5);
list.appendNode(7.9);
list.appendNode(12.6);
cout << "Here are the initial values:\n";
list.displayList();
cout << endl;

cout << "Now deleting the node in the middle.\n";

cout << "Here are the nodes left.\n";
list.deleteNode(7.9);
list.displayList();
cout << endl;
Continued on next slide…
 Sample Program 4
Continued from previous slide.

cout << "Now deleting the last node.\n";

cout << "Here are the nodes left.\n";
list.deleteNode(12.6);
list.displayList();
cout << endl;

cout << "Now deleting the only remaining node.\n";

cout << "Here are the nodes left.\n";
list.deleteNode(2.5);
list.displayList();
}
 Sample Program 4
Program Output

Here are the initial values:

2.5
7.9
12.6

Now deleting the node in the middle.

Here are the nodes left.
2.5
12.6

Now deleting the last node.

Here are the nodes left.
2.5

Now deleting the only remaining node.

Here are the nodes left.
Look at the else part of the second if statement. This is where the
function will perform its action since the list is not empty, and the first node
does not contain the value 7.9. Just like insertNode, this function uses
nodePtr and previousNode to traverse the list. The while loop
terminates when the value 7.9 is located. At this point, the list and the other
pointers will be in the state depicted in the figure below.
next, the following statement executes.
previousNode->next = nodePtr->next;
The statement above causes the links in the list to bypass the node that nodePtr
points to. Although the node still exists in memory, this removes it from the list.

The last statement uses the delete operator to complete the total
deletion of the node.
• The class's destructor should release all
the memory used by the list.
• It does so by stepping through the list,
deleting each node one-by-one. The
code is shown on the next slide.
FloatList::~FloatList() Destroying the List
{
ListNode *nodePtr, *nextNode;

nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
cout << "Linked List has been destroyed!" << endl;
}

Notice the use of nextNode instead of previousNode.

The nextNode pointer is used to hold the position of the
next node in the list, so it will be available after the node
pointed to by nodePtr is deleted.
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <class T>

class LinkedList
{
private:
// Declare a structure for the list
struct ListNode
{
T value;
struct ListNode *next;
};

ListNode *head; // List head pointer

Continued on next slide…
public:
LinkedList(void) // Constructor Appending a Node
{ head = NULL; }
~LinkedList(void); // Destructor
void appendNode(T);
void insertNode(T);
void deleteNode(T);
void displayList(void);
};
// appendNode appends a node containing the
// value pased into num, to the end of the list.

template <class T>

void LinkedList<T>::AppendNode(T num)
{
ListNode *newNode, *nodePtr;

// Allocate a new node & store num

newNode = new ListNode;
newNode->value = num; Continued on next slide…
newNode->next = NULL;
 Appending a Node
// If there are no nodes in the list
// make newNode the first node
if (!head)
head = newNode;
else // Otherwise, insert newNode at end
{
// Initialize nodePtr to head of list
nodePtr = head;

// Find the last node in the list

while (nodePtr->next)
nodePtr = nodePtr->next;

// Insert newNode as the last node

nodePtr->next = newNode;
}
} Continued on next slide…
 Traversing the List
// DisplayList shows the value
// stored in each node of the linked list
// pointed to by head.

template <class T>

void LinkedList<T>::DisplayList(void)
{
ListNode *nodePtr;

nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
Continued on next slide…
// The insertNode function inserts a node with
Inserting a Node
// num copied to its value member.
template <class T>
void LinkedList<T>::insertNode(T num)
{
ListNode *newNode, *nodePtr, *previousNode;

// Allocate a new node & store Num

newNode = new ListNode;
newNode->value = num;

// If there are no nodes in the list

// make newNode the first node
if (!head)
{
head = newNode;
newNode->next = NULL;
} Continued on next slide…
 Inserting a Node
else // Otherwise, insert newNode at end
{
// Initialize nodePtr to head of list
nodePtr = head;

// Skip all nodes whose value member is less

// than num.
while (nodePtr != NULL && nodePtr->value < num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

// Insert the node after the one pointed to

// by previousNode and before the one pointed to
// by nodePtr.
previousNode->next = newNode;
newNode->next = nodePtr;
}
} Continued on next slide…
// The deleteNode function searches for a node
Deleting a Node
// with Num as its value. The node, if found, is
// deleted from the list and from memory.

template <class T>

void LinkedList<T>::deleteNode(T num)
{

ListNode *nodePtr, *previousNode;

// If the list is empty, do nothing.
if (!head)
return;

// Determine if the first node is the one.

if (head->value == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
} Continued on next slide…
 Deleting a Node
else
{
// Initialize nodePtr to head of list
nodePtr = head;

// Skip all nodes whose value member is

// not equal to num.
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
// Link the previous node to the node after
// nodePtr, then delete nodePtr.
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
Continued on next slide…
 Destructor
// Destructor
// This function deletes every node in the list.

template <class T>

LinkedList<T>::~LinkedList(void)
{
ListNode *nodePtr, *nextNode;

nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
}
#endif
 Sample Program 5
// This program demonstrates the linked list template.
#include <iostream.h>
#include "LinkedList.h“

void main(void)
{
LinkedList<int> list;

// Build the list

list.appendNode(2);
list.appendNode(4);
list.appendNode(6);
cout << "Here are the initial values:\n";
list.displayList();
cout << endl;

Continued on next slide…

 Sample Program 5
cout << "Now inserting the value 5.\n";
list.insertNode(5);
cout << "Here are the nodes now.\n";
list.displayList();
cout << endl;

cout << "Now deleting the last node.\n";

list.deleteNode(6);
cout << "Here are the nodes left.\n";
list.displayList();
}

Continued on next slide…

 Sample Program 5
Program Output
Here are the initial values:
2
4
6

Now inserting the value 5.

Here are the nodes now.
2
4
5
6

Now deleting the last node.

Here are the nodes left.
2
4
5
The Doubly-Linked List
The Circular Linked List
• The list container, found in the Standard Template
Library, is a template version of a doubly linked list.
• STL lists can insert elements, or add elements to
their front quicker than vectors can, because lists
do not have to shift the other elements.
• lists are also efficient at adding elements at their
back because they have a built-in pointer to the last
element in the list (no traversal required).
Member Function Examples & Description

back cout << list.back() << endl;

The back member function returns a reference to the
last element in the list.

erase list.erase(iter);
list.erase(firstIter, lastIter)
The first example causes the list element pointed to by the iterator
iter to be removed. The second example causes all of the list
elements from firstIter to lastIter to be removed.

empty if (list.empty())
The empty member function returns true if the list is empty. If
the list has elements, it returns false.
Member Function Examples & Description

end iter = list.end();

end returns a bi-directional iterator to the end of the list.

front cout << list.front() << endl;

front returns a reference to the first element of the list.

insert list.insert(iter, x)
The insert member function inserts an element into the list. The
example shown above inserts an element with the value x, just before
the element pointed to by iter.

merge list1.merge(list2);
merge inserts all the items in list2 into list1. list1 is
expanded to accommodate the new elements plus any elements
already stored in list1. merge expects both lists to be sorted.
When list2 is inserted into list1, the elements are inserted into
their correct position, so the resulting list is also sorted.
Member Function Examples & Description

pop_back list.pop_back();
pop_back removes the last element of the list.

pop_front list.pop_front();
pop_front removes the first element of the list.

push_back list.push_back(x);
push_back inserts an element with value x at the end of
the list.

push_front list.push_front(x);
push_front inserts an element with value x at the beginning of the
list.

reverse list.reverse();
reverse reverses the order in which the elements appear in the list.
Member Function Examples & Description

size() Returns the number of elements in the list.

swap list1.swap(List2)
The swap member function swaps the elements stored in two
lists. For example, assuming list1 and list2 are lists, the
statement shown above will exchange the values in the two.

unique list.unique();
unique removes any element that has the same value as the
element
before it.
 Sample Program 6
// This program demonstrates the STL list container.
#include <iostream.h>
#include <list> // Include the list header
using namespace std; // Required by some compilers

void main(void)
{
list<int> myList;
list<int>::iterator iter;

// Add values to the list

for (int x = 0; x < 100; x += 10)
myList.push_back(x);

// Display the values

for (iter = myList.begin(); iter != myList.end(); iter++)
cout << *iter << " ";
cout << endl;
Continued on next slide…
 Sample Program 6
// Now reverse the order of the elements
myList.reverse();

// Display the values again

for (iter = myList.begin(); iter != myList.end(); iter++)
cout << *iter << " ";
cout << endl;

Program Output
0 10 20 30 40 50 60 70 80 90
90 80 70 60 50 40 30 20 10 0
• Wittenberg, Lee.(2018). Data structures and algorithms in C++. s.l.: Mercury
Learning
• Baka, Benjamin(2017). Python data structures and algorithms : improve the
performance and speed of your applications. Birmingham, U.K : Packt
Publishing
• Downey, Allen.(2017). Think data structures : algorithms and information
retrieval in Java. Sebastopol, CA: O'Reilly
• Chang, Kung-Hua(2017). Data Structures Practice Problems for C++
Beginners. S.l : Simple and Example
• Hemant Jain(2017). Problem Solving in Data Structures & Algorithms Using
C++: Programming Interview Guide. USA: CreateSpace Independent
Publishing Platform
• Malik, D.S. (2018). C++ Programming: Program Design Including Data
Structures. USA: Cengage Learning