Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
Faculty of Computer Science and Engineering
CS221L: Data Structures and Algorithms Lab
Lab Task – 3
Lab Instructor: Mr. Junaid Ahmed
Deadline: Sep-27th-2024 – 11:59 am
The year is 2075. Humanity’s transportation systems are governed by advanced AI
networks, with the backbone of the system being the Digital Memory Core,
responsible for managing transportation routes across the globe. The core uses a
Doubly Linked List to keep track of these routes, ensuring seamless travel between
major cities. Recently, several issues have been detected, and you, a cyber engineer at
QuantumTech, are tasked with fixing them.
Level 1: Memory Node Insertion
A system update requires adding new transport routes between two major cities. The
memory nodes representing these cities must be inserted into the correct position in
the Doubly Linked List, so the system can recognize and use the route for efficient
travel.
• Task: Write a function to insert a new memory node between two existing nodes,
ensuring both forward and backward connections are updated properly.
• Example: Insert a route between New York and London into the list of existing
cities.
Level 2: Memory Node Deletion
Some outdated transportation routes have been flagged for removal to make space for
newer ones. However, care must be taken to maintain the integrity of the linked list
when removing a node, or the system may fail.
• Task: Write a function that removes a specific memory node from the system
without breaking the forward or backward connections between the remaining
nodes.
• Example: Remove the route between Tokyo and Paris from the list.
Level 3: Reversing Data Flow
A cyberattack has disrupted several transportation routes, reversing the flow of certain
data, which in turn has confused the system. To fix this, you must reverse a segment of
nodes in the list, restoring the correct flow of traffic between cities.
• Task: Write a function to reverse the connections between a specific set of
memory nodes, flipping both forward and backward links in that range.
• Example: Reverse the routes between Berlin, Dubai, and Sydney in the memory
core.
Level 4: Memory Node Optimization
Over time, the system has accumulated duplicate transport routes, leading to
inefficiencies in data processing. To optimize performance, you must identify and
remove these duplicate memory nodes from the system.
• Task: Create a function that scans the doubly linked list, identifies duplicate
memory nodes, and removes them without disrupting the forward and backward
connections.
• Example: Remove any duplicate entries of the route between New York and
London.
Level 5: Inserting New Sections Dynamically
A major expansion in global transportation is taking place, requiring the addition of
multiple new cities and routes to the network. The memory core must be updated in
real-time, ensuring these new memory nodes are integrated without halting the
system.
• Task: Write a function to insert multiple consecutive memory nodes representing
new routes into the doubly linked list, ensuring all connections are properly
updated.
• Example: Insert new routes between Mumbai, Johannesburg, and São Paulo into
the system.
You can also use these routes as an example, but be sure to add some duplicates: