ACTIVITY NO.
3
LINKED LISTS
Course Code: CPE010 Program: Computer Engineering
Course Title: Data Structures and Algorithms Date Performed:
Section: Date Submitted:
Name: Instructor: Engr. Roman M. Richard
1. Objective(s)
Implement the list ADT using singly and doubly linked lists
Define operations based on list ADT from the module discussion
2. Intended Learning Outcomes (ILOs)
After this activity, the student should be able to:
a. Construct C++ code for a singly and doubly linked list in C++
b. Solve given problems utilizing linked lists in C++
3. Discussion
PART A: What is a linked list?
Linked Lists are a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous
location; the elements are linked using pointers.
Image Source: Hackearth.com
Why Linked List?
Arrays are useful but have the following limitations:
Fixed size.
Allocated memory remains to be the upper limit.
Expensive operations (such as insertion) which requires movement of all existing elements and
creation of room for new elements.
Advantages over Arrays
Dynamic size
Ease of insertion/deletion
Drawbacks
Random access is not allowed. We have to access elements sequentially starting from the first node
Extra memory space for a pointer is required with each element of the list.
Not cache friendly. No locality reference.
Representation:
17
A linked list is represented by a pointer to the first node of the linked list. The first node is called the
head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
o Data
o Pointer (Or Reference) to the next node
PART B: Doubly Linked Lists
Doubly Linked Lists are traversed in either direction. It is a linked list in which every node has a next pointer
and a backpointer.
Image Source: AlphaCodingSkills
Every node contains address of next node (except the last node). Every node contains address of previous
node (except the first node).
PART C: Common Operations on Linked Lists
Typical operations:
• Initialize the list
• Destroy the list
• Determine if list empty
• Search list for a given item
• Insert an item
• Delete an item, and so on
4. Materials and Equipment
Personal Computer with C++ IDE
Recommended IDE:
CLion (must use TIP email to download)
DevC++ (use the embarcadero fork or configure to C++17)
5. Procedure
18
ILO A: Construct C++ code for a singly and doubly linked list in C++
A.1. Singly Linked List
To start, we will do a simple implementation of a linked list. We must keep in mind the visual representation of
the individual nodes that will make up our linked list:
Data Next
28
Contains the Contains the
data of the address of
node the next
node
Every node in a singly linked list will have 2 compartments, the data and the pointer to the next. The data
contains the element of a single type that we want it to contain. The link will point to the next node in our list.
In C++, the node is defined as:
class Node{
public:
char data;
Node *next;
};
We will implement a list to represent the string “CPE010” that looks like the figure below:
C → P → E → 0 → 1 → 0 → NULL
Implementation will follow the given steps:
1. Create the node pointers and initialize as NULL
2. Create new instances of the node class and allocate them in the heap
3. Define every node in the list
4. Point the last node to null
Simple implementation:
#include<iostream>
#include<utility>
class Node{
public:
char data;
Node *next;
};
int main(){
//step 1
Node *head = NULL;
19
Node *second = NULL;
Node *third = NULL;
Node *fourth = NULL;
Node *fifth = NULL;
Node *last = NULL;
//step 2
head = new Node;
second = new Node;
third = new Node;
fourth = new Node;
fifth = new Node;
last = new Node;
//step 3
head->data = 'C';
head->next = second;
second->data = 'P';
second->next = third;
third->data = 'E';
third->next = fourth;
fourth->data = '0';
fourth->next = fifth;
fifth->data = '1';
fifth->next = last;
//step 4
last->data = '0';
last->next = nullptr;
}
Although we have created the linked list, this is an implementation that is useless and meant only to show
what we want to happen for the given output. Run your code and screenshot the output, then briefly discuss
how the output came to be and how could it be improved (table 3-1)?
Imagine if we had to make multiple items in the list in the hundreds or thousands! This would be too tedious,
ineffective, and inefficient. So, we must implement certain methods. These methods/operations associated
with the linked lists are:
Traversal
Insertion at head
Insertion at any part of the list
Insertion at the end
Deletion of a node
Linked List Traversal
Algorithm: ListTraversal (parameter: pointer to node n)
WHILE n IS NOT EQUAL TO null
PRINT data OF n
GO TO NEXT NODE n := next
ENDWHILE
20
PRINT next line
END
Sometimes we have a linked list, and we need to insert a node somewhere other than at the end of the list.
We will look at a couple of different ways to insert a node into an existing list.
To insert a node at the head:
1. Allocate memory for the new node
2. Put our data into the new node
3. Set Next of the new node to point to the previous Head
4. Reset Head to point to the new node
To insert a node at any location between the head and tail:
1. Check if it is the head node (previous node is null)
2. If null, print "Previous node cannot be null."
3. Allocate a new node
4. Store data in the new node
5. Point new node to the node previous node was pointing to
6. Point previous node to the new node
To insert a node at the end:
1. Allocate new node
2. Dereference to the head node
3. Store data in new node
4. Point next of new node to NULL
5. Traverse the list until next of the node is null
6. Point the next of the current node to the new node
To delete a node from linked list:
1. Find previous node of the node to be deleted.
2. Change the next of previous node.
3. Free memory for the node to be deleted.
Create code for each of the pseudocode given for all list operations above.
Provide screenshots in table 3-2.
In your driver function, show the use of each list operation and show the output in table 3-3 found in
section 6 with a descriptive caption for each. The tasks you have to perform are as follows:
a. Traverse the list by passing the head of the created list into the function
b. Insert the element ‘G’ at the start of the list to replace the current node. Output should now show
“GCPE101”
c. Insert an element “E” with the previous node element being “P”. Output should now show
“GCPEE101”.
d. Delete the node containing the element C.
21
e. Delete the node containing the element P.
f. Show the elements in the list. Output should be “GEE101”.
A.2. Doubly Linked List
The singly linked list allows for direct access from a list node only to the next node in the list. A doubly linked
list allows convenient access from a list node to the next node and also to the preceding node on the list.
The doubly linked list node accomplishes this in the obvious way by storing two pointers: one to the node
following it (as in the singly linked list), and a second pointer to the node preceding it.
Prev Data Next
← 28 →
Contains the Contains the Contains the
address of the data of the address of
previous node node the next
node
This means that in addition to our implementation of the singly linked list, we’ll have addition compartment.
class Node{
public:
char data;
Node *next;
Node *prev;
};
Modify the given operations used in the singly linked lists to work on the new construct of a doubly linked
list. Provide a screenshot of your code and analysis in table 3-4.
6. Output
Screenshot
Discussion
Table 3-1. Output of Initial/Simple Implementation
Operation Screenshot
Traversal
Insertion at head
Insertion at any part of the list
Insertion at the end
22
Deletion of a node
Table 3-2. Code for the List Operations
Source Code
a.
Console
Source Code
b.
Console
Source Code
c.
Console
Source Code
d.
Console
Source Code
e.
Console
Source Code
f.
Console
Table 3-3. Code and Analysis for Singly Linked Lists
Screenshots(s) Analysis
Table 3-4. Modified Operations for Doubly Linked Lists
7. Supplementary Activity
ILO B: Solve given problems utilizing linked lists in C++
Problem Title: Implementing a Song Playlist using Linked List
Source: Packt Publishing
Problem Description:
In this activity, we'll look at some applications for which a singly linked list is not enough or not convenient.
We will build a tweaked version that fits the application. We often encounter cases where we have to
customize default implementations, such as when looping songs in a music player or in games where multiple
players take a turn one by one in a circle.
These applications have one common property – we traverse the elements of the sequence in a circular
fashion. Thus, the node after the last node will be the first node while traversing the list. This is called a
circular linked list.
We'll take the use case of a music player. It should have following functions supported:
Create a playlist using multiple songs.
23
Add songs to the playlist.
Remove a song from the playlist.
Play songs in a loop (for this activity, we will print all the songs once).
Here are the steps to solve the problem:
Design the basic structure that supports circular data representation.
After that, implement the insert and delete functions in the structure.
Implement a function for traversing the playlist.
The driver function should allow for common operations on a playlist such as: next, previous, play all songs,
insert and remove.
8. Conclusion
Provide the following:
Summary of lessons learned
Analysis of the procedure
Analysis of the supplementary activity
Concluding statement / Feedback: How well did you think you did in this activity? What are your areas
for improvement?
9. Assessment Rubric
24
