UNIVERSITY INSTITUTE OF ENGINEERING

DEPARTMENT- ACADEMIC UNITS

FIRST YEAR ENGINEERING PROGRAMMES
Subject Name : Elementary Data Structures using C++
Subject Code: 23CSH-103

LINKED LIST DISCOVER . LEARN . EMPOWER

 Elementary Data
Structure Using C++

Course Objectives

• To enable the students to understand various stages

and constructs of C++ programming language.
• To improve their ability to analyze and address
variety of problems in C++.
• To understand the concept of data structures and
various operations on them.
• To understand the properties of various data
structures and able to identify the strengths and
weaknesses of different data structures.

• To analyze and compare the efficiency of

algorithms and learn to design efficient algorithms
for solving computing problems

2
 Course Outcomes
CO Course Outcome
Number

CO1 Understand the concepts of object-oriented programming including

programming process and compilation process.
CO2 Apply different techniques to decompose a problem and
programmed a solution with various concepts of object-oriented
programming language.
CO3 Analyse and explain the behaviour of linear data structure
operations using the programming addressed in the course.
CO4 Implement and evaluate the programs using the syntax and
semantics of object-oriented programming.
CO5 Design the solution of real-world problems in order to determine
that the program performs as expected.

3
ASSESSMENT PATTERN
The performance of students is evaluated as follows:

Theory Practical
Continuous Internal Semester End Continuous Internal Semester End
Components Assessment (CAE) Examination (SEE) Assessment (CAE) Examination (SEE)

Marks 40 60 60 40
Total Marks 100 100

4
 • A linked list is a linear data structure, in
which the elements are not stored at
contiguous memory locations.
Link List

https://www.geeksforgeeks.org/data-structures/linked-list/

5
Linked lists
• 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.

• Dynamically allocate space for each element as needed.

Node

Data Next

In linked list –
1. Each node of the list contains the data item
and a pointer to the next node.

2. There is a pointer to the list Start which contains address of

Start
first node.
Initially NULL
Linked lists (con…)

Start

node
node
Data Next Data

Linked list with 2 nodes

 Linked lists (con…)
INFO LINK

START 1 START=3, INFO[3]=M

3 2 A 5 LINK[3]=2, INFO[2]=A

2 LINK[2]=5, INFO[5]=N
3 M
LINK[5]=4, INFO[4]=G
4 G 7
LINK[4]=7, INFO[7]=O
5 N 4 LINK[7]=0, NULL value, So the list has ended

6
7 O 0

8
Why linked list?
Advantages of Array –
• Data is stored linearly in memory in continuous memory locations.
• It is easier to compute the address of an element in an array.
Disadvantages of Arrays -
• It is relatively expensive to insert and delete elements in an array.
• Since an 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 said to be
static data structures.
Why linked list?
Advantage of linked list -
• Another way of storing a list in memory is to have each element in the list contain
a field, called a link or pointer, which contains the address of the next element in
the list. Thus, successive elements in the list need not occupy adjacent space in
memory. This will make it easier to insert and delete elements in the list.
• Linked list has dynamic size . Node can be created or deleted whenever required.
Disadvantage of linked list -
• Random access is not allowed. We have to access elements sequentially starting
from the first node. So, we cannot do binary search with linked list.
• Extra memory space for a pointer is required with each element of the list.
• Reverse traversing is difficult.
Linear linked list
• 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 2 parts:
• The first part contains the information(data) of the element &
• The second part called the link field or next pointer field , contains the address of the next node in the list.

• A special case in the list that has no nodes is called NULL list or empty list and is denoted by the NULL pointer
in the variable START .
Representation of Linked Lists in Memory
• START contains the
location of the
beginning of the list.
• A hospital ward
contains 12 beds, of
which 9 are
occupied. Suppose
we want
alphabetical listing
of the patients.
• START contains 5 ,
with Adams as
patient name. Adams
pointer field
contains 3, so next is
Dean and so on.
Representation of Linked Lists in
Memory(contd..)
• START contains the location INFO LINK
of the beginning of the list. START 1
9 2
3 O 6
• NO EXIT is the character
4 T 0 NULL Value
string.
5
Blank Space 6 □ 11
7 X 10
8
9 N 3
10 I 4
11 E 7
12
13
Traversing a linked list
• Let LIST be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element and NULL
indicating the end of the LIST.
• Traversing means to process each node exactly once.
Algorithm: (Traversing a linked list) – Let LIST be a linked list in memory. This algorithm traverses LIST, applying an
operation PROCESS to each element of LIST. The variable PTR points to the node currently being processed.

1. Set PTR = START. [Initializes pointer PTR]

2. Repeat steps 3 & 4 while PTR≠NULL.
3. Apply PROCESS to INFO[PTR].
4. Set PTR = LINK[PTR]. [PTR now points to the next node.]
[End of Step2 loop]
5. Exit
START
200

54 210 90 300 15 420 10 NULL

200 210 300 420
Traversing a linked list(contd..)
Algorithm: (Count number of elements in a linked list)

1. Set NUM=0 [Initializes counter.]

2. Set PTR = START. [Initializes pointer PTR]
3. Repeat steps 4 & 5 while PTR≠NULL.
4. Set NUM=NUM+1 [Increases Num by 1]
5. Set PTR=LINK[PTR] [updates pointer]
[End of step3 loop]
6. Exit

START
200

54 210 90 300 15 420 10 NULL

200 210 300 420
 • Arrays and Linked Lists both are direct
information structures, yet the two of them
have a few points of interest and drawbacks
over one another.
ARRAYS VS LINK
LISTS

https://www.google.com/search?biw=1600&bih=789&tbm=isch
&sa=1&ei=Ujn6XJKvFPLXz7sP6fCQgAk&q=ARRAYS+VS+LINKLISTS
&oq=ARRAYS+VS+LINKLISTS&gs_l=img.12...264094.264094..2666
65...0.0..0.148.148.0j1......0....2j1..gws-wiz-img.A9FVRjK-qiY#imgr
c=t1853XlC8zYF9M:

16
Overflow & Underflow
• Sometimes new data are to be inserted into a data structure but there
is no available space, i.e., the free storage list is empty. This situation
is called OVERFLOW. i.e. AVAIL=NULL.
• The term UNDERFLOW refers to the situation where one wants to
delete data from a data structure that is empty, i.e. START= NULL.
Insertion in a linked list
• Let LIST be a linked list with successive nodes A & B. Suppose a node N is to be inserted into the list between nodes A & B.
INSERTING AT BEGINNING OF THE LIST
Lets START is the pointer having the initial position in linked list.
Let data be the element to be inserted in the new node.
POS is the mark where the new node is to be inserted.
TEMP is a temporary pointer to hold the node address.
1. Input data
2. Develop a New Node
3. New Node → DATA = data
4. New Node → Next = NULL
5. If (START equal to NULL)
then START = New Node.

19
PROGRAM TO INSERT AT BEGINNING
#include <iostream>
int main() {
using namespace std;
Node* head = nullptr; // Initialize an
struct Node { // Define the structure for a node in the linked list empty linked list
int data; // Insert elements at the beginning
Node* next;};
head = insertAtBeginning(head, 5);
head = insertAtBeginning(head, 10);
// Function to insert a new node at the beginning of the linked list head = insertAtBeginning(head, 15);
Node* insertAtBeginning(Node* head, int newData) { // Print the linked list
Node* newNode = new Node(); // Create a new node cout<< "Linked List: ";
printList(head);
newNode->data = newData;
return 0;
newNode->next = head; // Make the new node point to the current head }
head = newNode; // Update the head to point to the new node
return head;}
void printList(Node* head) { // Function to print the linked list
while (head != nullptr) {
std::cout << head->data << " ";
head = head->next; }
20
cout << std::endl; }
 INSERT A NODE AT THE END
Begin
1. Input DATA
2. develop a New Node
3. New Node → DATA = DATA
4. New Node → Next = NULL
5. If (START equal to NULL)
(a) START = New Node
6. Else
(a) TEMP = START
(b) While (TEMP → Next not equal to NULL)
(i) TEMP = TEMP → Next
7. TEMP → Next = New Node
Exit

21
PROGRAM TO INSERT AT END
#include <iostream> void printList(Node* head) { // Function
using namespace std; to print the linked list
struct Node { // Define the structure for a node in the linked list while (head != nullptr) {
cout << head->data << " ";
int data; Node* next;};
head = head->next; }
// Function to insert a new node at the end of the linked list cout << endl;
Node* insertAtEnd(Node* head, int newData) { }
Node* newNode = new Node(); // Create a new node
int main() {
// Initialize an empty linked list
newNode->data = newData; Node* head = nullptr;
newNode->next = nullptr;
if (head == nullptr) { // If the list is empty, make the new node the head // Insert elements at the end
head = insertAtEnd(head, 5);
head = newNode;
head = insertAtEnd(head, 10);
} else { // Traverse to the end of the list head = insertAtEnd(head, 15);
Node* temp = head; // Print the linked list
while (temp->next != nullptr) { cout << "Linked List: ";
printList(head);
temp = temp->next; }
return 0;
temp->next = newNode; } // Insert the new node at the end } 22
return head; }
DELETION
• In order to delete FIRST node from linked list we have to consider three possibilities:

(1) List is Empty (START = NULL). In this case we can not delete node from linked list.

(2) There is only one node in the linked list

(START->LINK=NULL). In this case we can delete the first node and then linked list becomes empty (START=NULL).

(3) There are more then one nodes in the linked list. In this case we can delete the first node.
After deleting the first node we have to move FIRST pointer to next node so that it can points to the newly first node in
the linked list.

23
PROGRAM TO DELETE A NODE
#include <iostream> // Function to delete a node with given value
using namespace std; Node* deleteNode(Node* head, int key) {
struct Node { // Define the structure for a node in the linked list Node* temp = head;
Node* prev = nullptr;
int data;
// If the node to be deleted is the head
Node* next; if (temp != nullptr && temp->data == key) {
// Constructor to initialize node with data and next pointer head = temp->next; // Change head
Node(int d) : data(d), next(nullptr) {} };
delete temp; // Free memory
return head; }
// Function to insert a new node at the end of the linked list // Search for the node to be deleted
Node* insertAtEnd(Node* head, int newData) { while (temp != nullptr && temp->data != key) {
Node* newNode = new Node(newData); prev = temp;
temp = temp->next; }
if (head == nullptr) {
// If the node with the given key is not
return newNode; } present
Node* temp = head; if (temp == nullptr) {
while (temp->next != nullptr) { return head; }
// Unlink the node from linked list
temp = temp->next; }
prev->next = temp->next;
temp->next = newNode; delete temp; // Free memory 24
return head; } return head; }
PROGRAM TO DELETE A NODE Contd.
// Function to print the linked list int main() {
void printList(Node* head) { Node* head = nullptr;
while (head != nullptr) { // Insert elements at the end
std::cout << head->data << " "; head = insertAtEnd(head, 1);
head = head->next; head = insertAtEnd(head, 2);
head = insertAtEnd(head, 3);
} head = insertAtEnd(head, 4);
std::cout << std::endl; head = insertAtEnd(head, 5);
std::cout << "Linked List before deletion: ";
}
printList(head);
// Delete a node
head = deleteNode(head, 3);

std::cout << "Linked List after deletion: ";

printList(head);

return 0;
}
25
Searching in a linked list
• Here we will discuss 2 searching algorithms for finding the location LOC of the
node where ITEM first appears in LIST.
LIST is a linked list in memory. This algorithm finds the location LOC of the node
where ITEM first appears in LIST, or sets LOC=NULL.
Algorithm: Search_list()
1. Set PTR = START, LOC = NULL. [Initializes pointer PTR]
2. Repeat steps 3 while PTR≠NULL.
3. If ITEM=INFO[PTR], then:
Set LOC=PTR & Exit [Search is successful]
Else:
Set PTR=LINK[PTR] [PTR now points to the next node.]
[End of If-else structure]
[End of step 2 loop]
4. [Search is unsuccessful] if LOC=NULL, Item is not in the list.
5. Exit
Application of linked lists
• Linked list is used as a building block for many other data structures
such as stack, queue, tree, graph, hash table.
• It allows to represent the polynomials and to perform the polynomials
calculations.
• It allows to manage memory by keeping track of the free available
memory(memory management).
• It allows to store a large sized file on disk. When the file is stored in
parts that are scattered all over the disk, then linked list provides a
mechanism to link these scattered parts of the file together.
 REFERENCES
• https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html
• https://www.geeksforgeeks.org/data-structures/linked-list/
• https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
• https://www.geeksforgeeks.org/merge-two-sorted-lists-place/
• https://www.geeksforgeeks.org/reverse-a-linked-list/

28
THANK YOU