Module 5: Data Structures and Algorithms

Lesson 14: Implementing Linked Lists

Objective: Teach learners how to implement and manipulate linked lists in Pascal, which are essential for managing collections of data that change dynamically.

Understanding Linked Lists:

A linked list is a dynamic data structure where each element (node) contains a value and a pointer to the next node in the sequence. Linked lists are useful for scenarios where the size of the data collection is not fixed, such as managing albums and photos in our app.

Creating a Basic Linked List:

Here’s how you can define a node and create a simple linked list in Pascal:

type
  PNode = ^TNode;
  TNode = record
    Data: Integer;
    Next: PNode;
  end;

var
  Head, Temp: PNode;
begin
  New(Head);  // Allocate memory for the first node
  Head^.Data := 10;
  New(Head^.Next);  // Allocate memory for the second node
  Head^.Next^.Data := 20;
  Head^.Next^.Next := nil;  // Terminate the list
end;

Explanation:

PNode: is a pointer to a node.
TNode: represents a node in the linked list, containing an integer data field and a pointer to the next node.
New(Head); allocates memory for the first node in the list.
Head^.Data := 10; assigns the value 10 to the data field of the first node.
New(Head^.Next); allocates memory for the second node in the list.
Head^.Next^.Data := 20; assigns the value 20 to the data field of the second node.
Head^.Next^.Next := nil; sets the pointer of the second node to nil, indicating the end of the list.

Traversing and Manipulating a Linked List:

Once a linked list is created, you can traverse it to access or modify its elements. Here’s how you can traverse and print all elements in the list:

Temp := Head;
while Temp <> nil do
begin
  writeln('Node Data: ', Temp^.Data);
  Temp := Temp^.Next;
end;

Explanation:

Temp := Head; initializes the traversal by setting Temp to point to the first node in the list.
while Temp <> nil do: loops through the list until Temp is nil, indicating the end of the list.
writeln('Node Data: ', Temp^.Data); prints the data of the current node.
Temp := Temp^.Next; moves to the next node in the list.

Inserting and Deleting Nodes:

Inserting and deleting nodes in a linked list is straightforward with pointers:

Inserting a Node:

procedure InsertAtBeginning(var Head: PNode; Value: Integer);
var
  NewNode: PNode;
begin
  New(NewNode);
  NewNode^.Data := Value;
  NewNode^.Next := Head;
  Head := NewNode;
end;

Explanation:

New(NewNode); allocates memory for the new node.
NewNode^.Data := Value; assigns the provided value to the new node.
NewNode^.Next := Head; links the new node to the current head of the list.
Head := NewNode; updates the head of the list to the new node.

Deleting a Node:

procedure DeleteNode(var Head: PNode; Value: Integer);
var
  Temp, Prev: PNode;
begin
  Temp := Head;
  Prev := nil;

  while (Temp <> nil) and (Temp^.Data <> Value) do
  begin
    Prev := Temp;
    Temp := Temp^.Next;
  end;

  if Temp = nil then
    Exit;  // Value not found

  if Prev = nil then
    Head := Temp^.Next  // The head needs to be deleted
  else
    Prev^.Next := Temp^.Next;

  Dispose(Temp);  // Free the memory of the deleted node
end;

Explanation:

while (Temp <> nil) and (Temp^.Data <> Value) do: searches for the node with the specified value.
if Prev = nil then Head := Temp^.Next; checks if the node to be deleted is the head of the list.
Prev^.Next := Temp^.Next; links the previous node to the next node, bypassing the node to be deleted.
Dispose(Temp); deallocates the memory of the deleted node.

Exercises:

Create a linked list with 5 nodes containing integer values. Traverse the list and print each node's data.
Write a procedure to insert a node at the end of a linked list. Test the procedure by adding a new node to the list and printing all nodes.
Implement a procedure to delete a node from a linked list by value. Test it by deleting a node and printing the remaining nodes.

Lesson 15: Sorting and Searching Algorithms

Objective: Introduce basic sorting and searching algorithms in Pascal, which will be useful for organizing and retrieving photos in the app.

Sorting Algorithms:

Sorting is a common operation in programming. Here, we'll cover two basic sorting algorithms: Bubble Sort and Selection Sort.

Bubble Sort:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order:

procedure BubbleSort(var Arr: array of Integer; N: Integer);
var
  i, j, Temp: Integer;
begin
  for i := 0 to N - 2 do
    for j := 0 to N - 2 - i do
      if Arr[j] > Arr[j + 1] then
      begin
        Temp := Arr[j];
        Arr[j] := Arr[j + 1];
        Arr[j + 1] := Temp;
      end;
end;

Explanation:

for i := 0 to N - 2 do: outer loop that passes through the array.
for j := 0 to N - 2 - i do: inner loop that compares and swaps adjacent elements.
if Arr[j] > Arr[j + 1] then: checks if the current element is greater than the next element.
Temp := Arr[j]; swaps the elements if they are in the wrong order.

Selection Sort:

Selection Sort is another simple algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the array and swaps it with the first unsorted element:

procedure SelectionSort(var Arr: array of Integer; N: Integer);
var
  i, j, MinIndex, Temp: Integer;
begin
  for i := 0 to N - 2 do
  begin
    MinIndex := i;
    for j := i + 1 to N - 1 do
      if Arr[j] < Arr[MinIndex] then
        MinIndex := j;
    Temp := Arr[MinIndex];
    Arr[MinIndex] := Arr[i];
    Arr[i] := Temp;
  end;
end;

Explanation:

for i := 0 to N - 2 do: outer loop that moves the boundary of the unsorted part of the array.
MinIndex := i; assumes the first unsorted element is the minimum.
for j := i + 1 to N - 1 do: inner loop that finds the minimum element in the unsorted part.
if Arr[j] < Arr[MinIndex] then MinIndex := j; updates the minimum index if a smaller element is found.
Temp := Arr[MinIndex]; swaps the smallest element with the first unsorted element.

Exercises:

Implement Bubble Sort and test it on an array of integers.
Implement Selection Sort and test it on an array of integers.
Create a function that uses either sorting algorithm to sort an array of photos by date.

Searching Algorithms:

Searching is another common operation. Here, we’ll cover linear search and binary search.

Linear Search:

Linear Search is the simplest searching algorithm that checks each element of the array sequentially until the desired element is found:

function LinearSearch(Arr: array of Integer; N, Target: Integer): Integer;
var
  i: Integer;
begin
  for i := 0 to N - 1 do
    if Arr[i] = Target then
    begin
      LinearSearch := i;
      Exit;
    end;
  LinearSearch := -1;  // Target not found
end;

Explanation:

for i := 0 to N - 1 do: loops through each element of the array.
if Arr[i] = Target then LinearSearch := i; returns the index of the target if found.
LinearSearch := -1; returns -1 if the target is not found in the array.

Binary Search:

Binary Search is a more efficient searching algorithm that works on sorted arrays. It repeatedly divides the search interval in half:

function BinarySearch(Arr: array of Integer; Low, High, Target: Integer): Integer;
var
  Mid: Integer;
begin
  while Low <= High do
  begin
    Mid := (Low + High) div 2;
    if Arr[Mid] = Target then
      Exit(Mid)
    else if Arr[Mid] < Target then
      Low := Mid + 1
    else
      High := Mid - 1;
  end;
  BinarySearch := -1;  // Target not found
end;

Explanation:

Mid := (Low + High) div 2; calculates the middle index of the current search interval.
if Arr[Mid] = Target then Exit(Mid); returns the index of the target if found.
else if Arr[Mid] < Target then Low := Mid + 1; narrows the search to the upper half if the target is greater than the middle element.
else High := Mid - 1; narrows the search to the lower half if the target is less than the middle element.
BinarySearch := -1; returns -1 if the target is not found in the array.

Exercises:

Implement Linear Search and test it on an array of integers. Search for both existing and non-existing elements.
Implement Binary Search on a sorted array of integers. Test it with different target values.
Create a function that uses Binary Search to find a photo by its name in a sorted array of photo metadata.

Secure Your Spot Now – Be First in Line for a License!

Module 5: Data Structures and Algorithms