Scribd
Upload
10 views11 pages

Assignment of Dsa Theory

The document is an assignment on data structures and algorithms, specifically focusing on singly linked lists and singly circular linked lists. It includes algorithms and pseudocode for various operations such as traversal, insertion, and deletion at different positions. The assignment is submitted by Ali Hussain Cheema from the Automotive Engineering Centre at the University of Engineering and Technology, Lahore.

Uploaded by

alicheema5219
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views11 pages

Assignment of Dsa Theory

The document is an assignment on data structures and algorithms, specifically focusing on singly linked lists and singly circular linked lists. It includes algorithms and pseudocode for various operations such as traversal, insertion, and deletion at different positions. The assignment is submitted by Ali Hussain Cheema from the Automotive Engineering Centre at the University of Engineering and Technology, Lahore.

Uploaded by

alicheema5219
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 11

2023-AU-17

Assignment No 1
Data
Structure and Algorithms

Assignment # 1

Singly Linked List

Submitted to: Ms. Arooj Arshad

Submitted by: 2023-AU-17

Name: Ali Hussain Cheema

Department: Automotive Engineering Centre


University of Engineering and Technology, Lahore
Course: Data Structures and Algorithms, Theory
Session: 2023
Semester: 3rd
October 12, 2024.

Page 1 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms

 Singly Linked List:


 Traversal:
a) Algorithm:
1. Initialize a variable current to point to the head of the list.
2. While current is not null:
 Print or process the data stored in current.
 Move current to the next node (current = current.next).
3. End when current is null (end of the list).

b) Pseudo code:
function traverse(head):
current = head
while current is not null:
print(current.data)
current = current.next
 Insertion at Beginning:
a) Algorithm:
1. Create a new node and set its data to the value you want to insert.
2. Set the new node's next to the current head.
3. Update the head to point to the new node.
b) Pseudo code:
function insertAtBeginning(head, newData):
newNode = Node(newData)
newNode.next = head
head = newNode
return head
 Insertion at End:
a) Algorithm:
1. Create a new node and set its data to the value you want to insert.
2. If the list is empty (head is null):
 Set head to the new node and return.
3. Initialize a variable current to the head.
4. While current.next is not null:
 Move current to the next node.
5. Set current.next to the new node.

Page 2 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
b) Pseudo code:
function insertAtEnd(head, newData):
newNode = Node(newData)
if head is null:
return newNode
current = head
while current.next is not null:
current = current.next
current.next = newNode
return head
 Insertion at a Specific Point:
a) Algorithm:
1. Create a new node and set its data to the value you want to insert.
2. If the position is 0:
 Call the function to insert at the beginning.
3. Initialize a variable current to the head.
4. For each index from 0 to position - 1:
 If current is null before reaching the position:
 Return (position is out of bounds).
 Move current to the next node.
5. Set the new node’s next to current.next.
6. Set current.next to the new node.
b) Pseudo code:
function insertAtPosition(head, newData, position):
newNode = Node(newData)
if position == 0:
return insertAtBeginning(head, newData)
current = head
for i from 0 to position - 1:
if current is null:
return head # Position is out of bounds

Page 3 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
current = current.next
newNode.next = current.next
current.next = newNode
return head
 Deletion at Beginning:
a) Algorithm:
1. If the list is empty (head is null):
 Return (nothing to delete).
2. Update head to head.next.
b) Pseudo code:
function deleteAtBeginning(head):
if head is null:
return head
head = head.next
return head
 Deletion at End:
a) Algorithm:
1. If the list is empty (head is null):
 Return (nothing to delete).
2. If the list has only one node:
 Return null (head is now empty).
3. Initialize a variable current to head.
4. While current.next.next is not null:
 Move current to the next node.
5. Set current.next to null (removing the last node).
b) Pseudo code:
function deleteAtEnd(head):
if head is null:
return head
if head.next is null:
return null

Page 4 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
current = head
while current.next.next is not null:
current = current.next
current.next = null
return head
 Deletion at Specific Point:
a) Algorithm:
1. If the list is empty (head is null):
 Return (nothing to delete).
2. If the position is 0:
 Call the function to delete at the beginning.
3. Initialize a variable current to head.
4. For each index from 0 to position - 1:
 If current.next is null before reaching the position:
 Return (position is out of bounds).
 Move current to the next node.
5. If current.next is not null:
 Set current.next to current.next.next (bypassing the node to delete).
b) Pseudo code:
function deleteAtPosition(head, position):
if head is null:
return head
if position == 0:
return deleteAtBeginning(head)
current = head
for i from 0 to position - 1:
if current.next is null:
return head #Position is out of bounds
current = current.next
if current.next is not null:

Page 5 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
current.next = current.next.next
return head

 Singly Circular Linked List:


 Traversal:
a) Algorithm:
1. Check if the head is null:
 If it is, return (the list is empty).
2. Initialize a variable current to point to head.
3. Do the following:
 Print or process the data in current.
 Move current to current.next.
4. Repeat the above step until current equals head again.
5. End the traversal when you circle back to the head.
b) Pseudo Code:
function traverse(head):
if head is null:
return
current = head
do:
print(current.data)
current = current.next
while current != head
 Insertion at Beginning:
a) Algorithm:
1. Create a new node and set its data.
2. If the list is empty (head is null):
 Set newNode.next to point to itself (the only node).
 Return newNode as the new head.
3. Initialize a variable current to point to head.
4. While current.next is not head (find the last node):
 Move current to current.next.
5. Set current.next to newNode (link the last node to the new node).

Page 6 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
6. Set newNode.next to head (link the new node to the head).
7. Return newNode as the new head of the list.

b) Pseudo Code:
function insertAtBeginning(head, newData):
newNode = Node(newData)
if head is null:
newNode.next = newNode # Point to itself (only node in list)
return newNode
current = head
while current.next != head: # Find the last node
current = current.next
current.next = newNode #Link last node to new node
newNode.next = head #New node points to head
return newNode # New node becomes new head
 Insertion at End:
a) Algorithm:
1. Create a new node and set its data.
2. If the list is empty (head is null):
 Set newNode.next to point to itself (the only node).
 Return newNode as the new head.
3. Initialize a variable current to point to head.
4. While current.next is not head (traverse to the last node):
 Move current to current.next.
5. Set current.next to newNode (link the last node to the new node).
6. Set newNode.next to head (link the new node to the head).
7. Return head (the head remains unchanged).
b) Pseudo Code:
function insertAtEnd(head, newData):
newNode = Node(newData)
if head is null:
newNode.next = newNode # Point to itself (only node in list)

Page 7 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
return newNode
current = head
while current.next != head: #Traverse to last node
current = current.next
current.next = newNode // Link last node to new node
newNode.next = head // New node points to head
return head // Head remains unchanged
 Insertion at any Specific Point:
a) Algorithm:
1. Create a new node and set its data.
2. If the position is 0:
 Call the function to insert at the beginning.
3. Initialize a variable current to point to head.
4. For each index from 0 to position - 1:
 If current.next is head before reaching the position:
 Return (position is out of bounds).
 Move current to current.next.
5. Set newNode.next to current.next (link the new node to the next node).
6. Set current.next to newNode (link the previous node to the new node).
7. Return head.
b) Pseudo Code:
function insertAtPosition(head, newData, position):
newNode = Node(newData)
if position == 0:
return insertAtBeginning(head, newData)
current = head
for i from 0 to position - 1:
if current.next == head: // Position is out of bounds
return head
current = current.next
newNode.next = current.next

Page 8 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
current.next = newNode
return head
 Deletion at Beginning:
a) Algorithm:
1. Check if the list is empty (head is null):
 Return (nothing to delete).
2. If the list has only one node (head.next == head):
 Return null (the list is now empty).
3. Initialize a variable current to point to head.
4. While current.next is not head (find the last node):
 Move current to current.next.
5. Set current.next to head.next (link the last node to the second node).
6. Update head to head.next (move head to the next node).
7. Return the new head.
b) Pseudo Code:
function deleteAtBeginning(head):
if head is null:
return head
if head.next == head: #Only one node
return null
current = head
while current.next != head: #Find the last node
current = current.next
current.next = head.next # Link last node to second node
head = head.next #Move head to the next node
return head
 Deletion at End:
a) Algorithm:
1. Check if the list is empty (head is null):
 Return (nothing to delete).
2. If the list has only one node (head.next == head):

Page 9 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
 Return null (the list is now empty).
3. Initialize a variable current to point to head.
4. While current.next.next is not head (find the second to last node):
 Move current to current.next.
5. Set current.next to head (remove the last node).
6. Return head.

b) Pseudo Code:
function deleteAtEnd(head):
if head is null:
return head
if head.next == head: #Only one node
return null
current = head
while current.next.next != head: # Find the second to last node
current = current.next
current.next = head #Remove the last node
return head
 Deletion at any Specific Point:
a) Algorithm:
1. Check if the list is empty (head is null):
 Return (nothing to delete).
2. If the position is 0:
 Call the function to delete at the beginning.
3. Initialize a variable current to point to head.
4. For each index from 0 to position - 1:
 If current.next is head before reaching the position:
o Return (position is out of bounds).
 Set a variable previous to current and move current to current.next.
5. If current is head (the node to delete is the head):
 Call the function to delete at the beginning.

Page 10 of 11
2023-AU-17

Assignment No 1
Data
Structure and Algorithms
6. Set previous.next to current.next (bypass the node to delete).
7. Return head.
b) Pseudo Code:
function deleteAtPosition(head, position):
if head is null:
return head
if position == 0:
return deleteAtBeginning(head)
current = head
for i from 0 to position - 1:
if current.next == head: # Position is out of bounds
return head
previous = current
current = current.next
if current == head: #Node to delete is the head
return deleteAtBeginning(head)
previous.next = current.next #Bypass the node to delete
return head

Page 11 of 11

You might also like