Data Structures: Heaps and Linked Lists

Lab Manuals

• Covering data structures and algorithms
• Prepared by Prof. Noureldien A. Noureldien
• Dated October 2024

Table of Contents

• Lists various lab topics and associated pages
• Includes topics such as Linked Lists (singly and circular), Stacks, Queues, Priority Queues, Searching, Sorting (Bubble, Insertion, Selection), Hashing, and Programming Problems.

Lab (1): Linked Lists - Singly Linked List

• Definition: A linked list is a linear collection of finite homogeneous data elements called nodes. The order is maintained by links or pointers.
• Each element is stored separately called 'node' in memory.
• List structure created by pointers that connect all nodes together.
• Unlike arrays, linked list memory allocation is dynamic.
• Applications include: representing polynomials and sparse matrices; implementing various data structures like stacks, queues, trees, etc; implementing dynamic memory allocation at runtime.

Lab (1): Linked Lists – Circular Linked Lists

• Linked list where the last element points to the first element forming a circular chain.
• No node points to NULL (no end node).
• Operations similar to singly linked lists, but maintain an extra pointer.

Lab (1): Description

• Demonstrate linked lists to solve problems.
• Define linked lists, compare them to arrays, differentiate between different types, and write C codes to manipulate them.
• Instructors' tasks include demonstrating C implementation, explaining concepts, and guiding students during coding and execution.

Lab (1): Representation of a Linked List

• Visual representation of how linked list nodes (data and pointers) are interconnected for a given set of data.

Lab (1): Why use Linked Lists Over Arrays?

• Addresses limitations of arrays regarding fixed size and time-consuming resizing.
• Lists allow dynamic memory allocation for nodes, avoiding the need to shift data for insertions and deletions.

Lab (1.4): Applications of Linked Lists

• Can represent polynomials
• Represent sparse matrices
• Implement stacks, queues, trees, and other data structures
• Implemented for dynamic memory allocation

Lab (1.5): Operations Performed on Linked Lists

• Described as insertion, deletion, display, search.

Lab (2): Linked Lists - Circular Linked Lists

• Definition: A circular linked list is a linked list where the last element points to the first (head), creating a circular chain.
• There's a head pointer, but no starting or ending pointer.
• Traversal, insertion, deletion, and other operations similar to singly linked lists.

Lab (2.1): Circular Linked List

• Definition: A circular linked list is a linked list where the last node points to the first.
• This creates a circular chain, eliminating a NULL pointer at the end.

Lab (2.2): Operations on Circular Linked Lists

• Traversal (starting from the head and traversing until the head is reached).
• Other operations similar to the singly linked list logic.

Lab (2.3): Creating a Circular Linked List

• Steps to create a circular list involve creating nodes and connecting the last node to the first.

Lab (2.1.1): Traversing

• Pointer starts at the head, visits each node, and returns to the head.

Lab (2.4/Exercise 1): Searching a Circular Linked List

• Basic steps to search a circular linked list for an element.

Lab (3): Stacks

• A stack data structure follows the LIFO (Last-In, First-Out) principle.
• Operations involve pushing (adding) elements to the top of the stack and popping (removing) elements from the top.

Lab (3.1): Introduction

• Stack is a sequential data structure.
• Insertion and deletion at the same end.
• Useful in real life (e.g. a stack of books).
• LIFO (Last-In, First-Out) order.
• Top is the most frequently accessed element

Lab (3.2): Operations

• Described as creation, is-empty, is-full, insertion(push), deletion (pop), and peek (not removing element)

Lab (3.3): Stack Implementation with Arrays

• Uses arrays with a defined fixed size to store stack elements.
• Efficient due to contiguous allocation.

Lab (3.4): Stack Insertion (push)

• Algorithm for adding to the stack.
• Checks if stack is full, exiting if true.
• Increments top pointer, inserting data where needed.
• Returns success.

Lab (3.5): Stack Deletion (pop)

• Data retrieved from top location of the stack, when stack is not empty.
• Decrements top pointer.
• Returns the data.

Lab (3.6): Peek

• Data retrieval from the stack's top without removal.

Lab (4): Queues

• Definition: A queue follows the FIFO (First-In, First-Out) principle.
• Elements enter at the rear and exit from the front.

Lab (4.1): Linear/FIFO Queues

• Queue operations are insert at the rear (enqueue), delete from the front (dequeue), check emptiness, and check fullness.

Lab (4.2): Queue-Array Operations

• Algorithm operations such as, creation, isEmpty, isFull, insertAtRear, deleteFromFront, peek.

Lab (4.3): Queue-Array Implementation

• Uses arrays for queue implementation,
• Rear & front indices keep track of last insert & last delete position.

Lab (4.4): Circular Queue

• Circular queue is a queue that has elements linked in a circular manner which follow the FIFO (First in, First Out) principle.
• Different operations for a circular queue.

Lab (4.5): Dequeue Operation

• Algorithm to remove an element from the front of the circular queue.

Lab (4.6): Enqueue Operation

• Steps for inserting an element at rear of a circular queue.

Lab (5): Priority Queues

• Priority queue elements are arranged by priority and deleted according to priority.

Lab (5.1): Introduction

• Priority queue is a data structure
• Elements are inserted arbitrarily but only the element with the highest priority can be removed (descending priority queue).

Lab (5.2): Priority Queue Operations

• Operations on priority queues include insert, peek, and extract maximum

Lab (5.3): Implementation of Priority Queue as a Heap

• Priority queue can be implemented using different data structures.
• A Heap is a complete binary tree where the value of each node is greater than or equal to the values of its children.
• A Heap data structure is an efficient implementation for priority queues.

Lab (5.4): Heap Data Structure

• Complete binary tree satisfies the heap property.

Lab (5.5): Complete Binary Tree

• A binary tree where all levels are completely filled except possibly the lowest one, which is filled from left to right.
• Complete binary trees can also be used to implement priority queues.

Lab (6): Searching

• Discusses linear and binary search algorithms.
• Searching algorithm steps and methods.

Lab (7): Bubble Sort

• Describes algorithms for arranging data in an ascending or descending order
• Implementation steps for bubble sort

Lab (8): Insertion and Selection Sort

• Sorting algorithms for arranging numbers in ascending or descending order.

Lab (8.1): Insertion Sort

• Description of the algorithm steps.
• How the algorithm works via an example (shows the step by step process of sorting an array of integers using insertion sort).

Lab (8.2): Selection Sort

• Explanation of the algorithm logic
• Step-by-step demonstration using an Example (how it works)

Lab (9): Hashing

• Discusses hashing, including its operations (insertion, deletion, and searching), algorithms, and their advantages/disadvantages.

Lab (9.1): Hash functions

• Hash functions map keys to addresses within a structure like arrays (hash table).
• Criteria for a suitable hash function: easy to compute and uniform distribution of hash addresses to minimize collisions.

Lab (12): Programming Problems

• Contains programming problems related to linked lists, like deleting a middle node.