DS Lab 6 - Linked List Implementation
DS Lab 6 - Linked List Implementation
DS Lab 6 - Linked List Implementation
Lab 6
Linked List Implementation
Table of Contents
1. Introduction 70
1.1 Linear Linked Lists 70
1.2Relevant Lecture Readings 70
4. Concept Map 71
4.1 Linear Linked Lists in C++ 71
6. Procedure& Tools 73
6.1 Tools 73
6.2 Walk through Tasks [Expected time = 20mins] 73
7. Practice Tasks 77
7.1 Practice Task 1 [Expected time = 20mins] 78
7.2 Practice Task 2 [Expected time = 20mins] 78
7.3Practice Task 3 [Expected time = 30mins] 78
7.5 Out comes 78
7.6Testing 78
9. Evaluation criteria 80
1. Introduction
This lab will introduce concept of dynamic memory based data structures such as linked
lists. In case of some real world applications we don’t know about the storage requirements of
program before program execution, in that scenario dynamic data storage systems are useful. We
will learn about linear linked list structure and how linked lists are helpful to store data during
program execution.
A linked list is a collection of elements, called nodes. Every node (except the last node)
stores the address of the next node. Therefore, every node in a linked list has two components:
one to store the data and other to store the address, called the link, of the next node in the list.
The address of the first node in the list is stored in a separate location, called the head or first.
Linked list: A list of elements, called nodes, in which the order of the nodes is determinedby the
address, called the link, stored in each node.
We may perform different operations on linked lists such as inserting a node, deleting a node,
traversing a linked list etc.
To understand and implement linear linked lists with their operations in C++.
4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.
Node of a linked list is a self-referential structure which can be represented by following code.
structnodeType
{
int info;
nodeType *link;
};
The basic operations of a linked list are as follows: Search the list to find out whether aparticular
item is in the list, insert an item in the list, and delete an item from the list.These operations
require the list to be traversed. That is, given a pointer to the first nodeof the list, we must step
through the nodes of the list. Following code segment helps in traversal.
current = head;
while (current != NULL)
{
//Process current
current = current->link;
}
This section discusses how to insert an item into, and delete an item from, a linked list.Consider
the following definition of a node. (For simplicity, we assume that the infotype is int.)
structnodeType
{
int info;
nodeType *link;
};
Suppose that p points to the node with info 65, and a new node with info 50 is to becreated and
inserted after p. Consider the following statements:
To delete a node from linked list we can use following code segment.
q = p->link;
p->link = q->link;
delete q;
After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.
5.2Problem description:
Write a program of linear linked list of objects of “person” class. Attributes of “person”
class (privately defined) are per_id (int), per_name (string) and per_age (int). “person”
class contains member functions (publicly defined): constructor, input and output
functions. You are required to define a class for linear linked list. This class should
contain the member functions to insert, delete nodes from linear linked list. This class
should also contain the member functions to display values of all nodes of linear linked
list.
5.3.1 Task-1
Compare linear linked list with circular linked list and provide three differences between
the two structures.
5.3.2 Task-2
List three real world examples in which linked list structures can be used.
6. Procedure& Tools
This section provides information about tools and programming procedures used for the
lab.
6.1 Tools
This linked list program provides different functions like addition of node at start of list,
deletion of node from list, displaying elements of list, addition of node at end of list, add a node
after some specific node in the list.
Figure 10: Implementation of linear linked list class in Visual Studio 2008.
Figure 11: Implementation of linear linked list class in Visual Studio 2008.
Figure 12: Implementation of linear linked list class in Visual Studio 2008.
Figure 13: Implementation of linear linked list class in Visual Studio 2008.
7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and placesolution code in a
folder specified by your lab instructor.
After completing this lab, student will be able to understand and develop programs related to
linear linked lists, circular linked lists and doubly linked listsin C++ using Microsoft Visual
Studio 2008 environment.
7.6Testing
Test Cases for Practice Task-1
Sample Input Sample Output
Enter the values of elements of linked
list:
2
3
4
5
7
8
6
9
11
1
Enter the value after which you want New value inserted after 11
to insert: 11
Enter the value to delete from linked Key value 5 is deleted from linked list.
list: 5
Department of Computer Science Page 78
MAJU, Islamabad
_________________ Lab6: Linked List Implementation
The lab instructor will give you unseen task depending upon the progress of the class.
9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
Department of Computer Science Page 80
MAJU, Islamabad
_________________ Lab6: Linked List Implementation