SVKM’s NMIMS

Mukesh Patel School of Technology Management & Engineering

Computer Engineering Department
Program: MCA, Semester - I

Course: Data Structure and Algorithms

List of Experiments

LAB Manual

PART A
(PART A : TO BE REFFERED BY STUDENTS)

Experiment No.05
A.1 Aim:
Implementation of doubly Linked List with following operations:

1. Creation
2. Insertion and
3. Deletion of the nodes

A.2 Prerequisite:
1. Knowledge of different operations performed on linked list data structure.
2. Knowledge of different types of linked list and their applications.
3. Fundamental concepts of C\C++.

A.3 Outcome:
After successful completion of this experiment students will be able to

1. Identify the need of appropriate selection of data structure

2. Identify the steps of linked list data structure selection.
3. Implement different type of Linked list data structure to solve the given problem
4. Enlist the applications of Linked list data structure.
5. Differentiate between singly and doubly Linked list.

A.4 Theory:
A.4.1. Introduction to Linked List
A.5 Procedure/Algorithm:
A.5.1:

 Algorithm to insert a new node in the beginning of the

doubly linked list

Step 1: IF Node_AVAIL = NULL, then

Write OVERFLOW

Go to Step 7

[END OF IF] //Allocate memory id available

Step 2: SET New_Node = Node_AVAIL

Step 3: SET New_Node->DATA = VAL

Step 4: SET New_Node->PREV = NULL

Step 5: SET New_Node->Next = START

Step 6: SET START = New_Node

Step 7: EXIT

 Algorithm to insert a new node at the end of the doubly

linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->Next = NULL

Step 6: SET PTR = START

Step 7: Repeat Step 8 while PTR->NEXT != NULL

Step 8: SET PTR = PTR->NEXT

[END OF LOOP]

Step 9: SET PTR->NEXT = New_Node

Step 10: New_Node->PREV = PTR

Step 11: EXIT

 Algorithm to insert a new node after a node that has value
NUM

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 8 while PTR->DATA != NUM

Step 7: SET PTR = PTR->NEXT

[END OF LOOP]

Step 8: New_Node->NEXT = PTR->NEXT

Step 9: SET New_Node->PREV = PTR

Step 10: SET PTR->NEXT = New_Node

Step 11: EXIT

 Algorithm to delete the first node from the doubly linked list
Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 6

[END OF IF]

Step 2: SET PTR = START

Step 3: SET START = START->NEXT

Step 4: SET START->PREV = NULL

Step 5: FREE PTR

Step 6: EXIT

 Algorithm to delete the last node of the doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 7

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 and 5 while PTR->NEXT != NULL

Step 4: SET PTR = PTR->NEXT

[END OF LOOP]

Step 5: SET PTR->PREV->NEXT = NULL

Step 6: FREE PTR

Step 7: EXIT

 Algorithm to delete the node after a given node from the

doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR->DATA != NUM

Step 4: SET PTR = PTR->NEXT

[END OF LOOP]

Step 5: SET TEMP = PTR->NEXT

Step 6: SET PTR->NEXT = TEMP->NEXT

Step 7: SET TEMP->NEXT->PREV = PTR

Step 8: FREE TEMP

Step 9: EXIT

PART B
 (PART B : TO BE COMPLETED BY STUDENTS)

(Students must submit the soft copy as per following segments within two hours of the
practical. The soft copy must be uploaded on the Blackboard or emailed to the
concerned lab in charge faculties at the end of the practical in case the there is no Black
board access available)

Roll No.A039 Name: Masrita.Mangalarapu

Class :MCA(2023-24) Batch :2
Date of Experiment: 15/09/23 Date of Submission:21/09/23
Grade : Time of Submission:
Date of Grading:

B.1 Software Code written by student: (Task 1)

(Paste your Matlab code completed during the 2 hours of practical in the lab here)

Code:

public class DoublyLinkedList {

private Node head;

private Node tail;

private class Node {

int data;

Node prev;

Node next;

Node(int value) {

data = value;

prev = null;

next = null;

}
}

public DoublyLinkedList() {

head = null;

tail = null;

// Adding a value at the end of the list

public void append(int value) {

Node newNode = new Node(value);

// Check if it's the first node in the list.

if (head == null) {

head = newNode;

tail = newNode;

} else {

tail.next = newNode;

newNode.prev = tail;

tail = newNode;

// Adding a value at the beginning of the list

public void prepend(int value) {

Node newNode = new Node(value);

if (head == null) {

head = newNode;

tail = newNode;
 } else {

newNode.next = head;

head.prev = newNode;

head = newNode;

public void deleteNode(int value) {

Node current = head;

while (current != null) {

if (current.data == value) {

if (current == head && current == tail) {

head = null;

tail = null;

} else if (current == head) {

head = current.next;

head.prev = null;

} else if (current == tail) {

tail = current.prev;

tail.next = null;

} else {

current.prev.next = current.next;

current.next.prev = current.prev;

return;

current = current.next;
 }

System.out.println("Node with value as '" + value + "' was not found :(");

public void display() {

Node current = head;

while (current != null) {

System.out.print(current.data + " ");

current = current.next;

System.out.println();

public static void main(String[] args) {

DoublyLinkedList dll = new DoublyLinkedList();

boolean j = true;

int value;

int n;

java.util.Scanner scanner = new java.util.Scanner(System.in);

while (j) {

System.out.println("Which operation do you wish to perform?");

System.out.println("1. Add at the beginning of the list");

System.out.println("2. Add at the end of the list");

System.out.println("3. Delete a node based on its value");

System.out.println("4. Display all the nodes in the list");

System.out.println("5. Exit");

n = scanner.nextInt();
switch (n) {

case 1:

System.out.println("Which value do you want to enter?");

value = scanner.nextInt();

dll.append(value);

break;

case 2:

System.out.println("Which value do you want to enter?");

value = scanner.nextInt();

dll.prepend(value);

break;

case 3:

System.out.println("Which value do you want to delete?");

value = scanner.nextInt();

dll.deleteNode(value);

break;

case 4:

System.out.println("The values in the node are:");

dll.display();

break;

case 5:

System.out.println("Exiting...");

j = false;

break;

default:

System.out.println("Wrong Input Detected, Please add a valid input");

break;
 }

scanner.close();

B.2 Input and Output: (Task 1)

(Paste your program input and output in following format, If there is error then paste the specific
error in the output part. In case of error with due permission of the faculty extension can be given to
submit the error free code with output in due course of time. Students will be graded accordingly.)

Which operation do you wish to perform?

1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

Which value do you want to enter?

Which operation do you wish to perform?

1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

Which value do you want to enter?

Which operation do you wish to perform?

1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

Which value do you want to enter?

Which operation do you wish to perform?

1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

The values in the node are:

864

Which operation do you wish to perform?

1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

Which value do you want to delete?

Which operation do you wish to perform?

 1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

The values in the node are:

84

Which operation do you wish to perform?

1. Add at the beginning of the list

2. Add at the end of the list

3. Delete a node based on its value

4. Display all the nodes in the list

5. Exit

B.3 Observations and learning [w.r.t. all tasks]:

(Students are expected to comment on the output obtained with clear observations and learning for
each task/ sub part assigned)

I have identified the need of appropriate selection of data structures, identified the steps of linked
list data structure selection and implemented different types of linked list data structures to solve
the problems in this practical. I have also learnt to differentiate between singly and doubly linked
lists.

B.4 Conclusion:
(Students must write the conclusion as per the attainment of individual outcome listed above and
learning/observation noted in section B.3)

The practical has been successfully performed, and I have obtained all necessary
outputs. In summary, the C++ code that is supplied implements a doubly linked list
with the fundamental operations of adding, removing, and moving nodes. The code
makes sure that nodes are linked correctly, deals with unusual deletion situations, and
accurately shows the list. It provides as a basic illustration of how to use doubly linked
lists in java code.
************************