Mada za sehemu hiiDemonstrate mastery of basic principles of Algorithms and Data structuresMada 7
- Describe the concept of data structure and algorithms
- Explore and utilise basic data structure (linked lists, stacks, queues and trees.)
- Describe the design and performance of various classic searching and sorting algorithms
- Write a program that implements various sorting algorithms and create a report for performance
- Create a program that implements array and a linked list data structure using object-oriented programming language
- Implement stack and queue, binary search tree, balanced tree (such as an AVL tree), graph, hash table data structures in object-oriented programming language
- Describe the techniques of algorithm analysis
Exploring and Utilising Basic Data Structures
A data structure is a method of storing and organising data in a computer so that it can be used efficiently. While static data structures like arrays have a fixed size, many real-world applications require data structures that can grow and shrink during program execution. This leads us to dynamic data structures: linked lists, stacks, queues, and trees. These structures provide flexibility in managing data whose size is not known in advance.
Meaning and Structure
A linked list is a linear data structure in which elements (called nodes) are stored in non-contiguous memory locations. Each node contains two parts: the data (the actual information) and the pointer (the link to the next node). The pointer in each node allows the program to move from one node to the next, forming a chain. The last node contains a null pointer, indicating the end of the list.
The key terms used in linked lists are:
- Link: Each element of a linked list that stores data
- Next: A pointer that contains the address of the following link
- First: A pointer to the first node (also called Head)
- Tail: The last node in the list
Data | Pointer | Data | Pointer | Data | Pointer
10 | ----→ | 20 | ----→ | 30 | NULL
Types of Linked Lists
There are three main types of linked lists:
- Singly Linked List: Traversed in one direction from head to tail
- Doubly Linked List: Traversed in both directions (forward and backward)
- Circular Linked List: The last node points back to the first node
Operations on Linked Lists
Creation: Creates a linked list with one node. Once created, insertion operations can add more elements.
Insertion: A new node can be inserted:
- At the beginning of the linked list
- At the end of the linked list
- At any specified position in between
When inserting at the beginning, the new node's pointer links to the current head, and the new node becomes the new head. No elements need to be shifted—only pointers are updated.
Deletion: A node can be deleted from:
- The beginning of the linked list
- The end of the linked list
- A specified location
Traversal: Going through all nodes from one end to another. In a singly linked list, you can only traverse forward. In a doubly linked list, forward and backward traversing is possible.
Concatenation: Appending the second list to the end of the first list.
Advantages and Disadvantages
Advantages:
- Easy insertion and deletion (takes constant time, no need to shift elements)
- No memory wastage—size increases and decreases during runtime
- Can expand constantly without copying and reallocating
- Easy to implement stacks and queues
Disadvantages:
- Uses more memory than arrays (each node stores data plus a pointer)
- Traversal is not easy—you cannot randomly access elements like in arrays
- Reverse traversing is difficult
Real-world Application
A real example of a linked list is the "forward" and "backward" buttons in a web browser. A doubly linked list keeps track of visited pages, allowing you to move back to previous pages and forward again.
Meaning and Structure
A stack is an Abstract Data Type (ADT) and is a linear data structure that can be accessed only at the top for storing and retrieving data. It follows the Last-In-First-Out (LIFO) principle—the last element placed on the stack is the first one removed. This is like a stack of plates in a cafeteria: new trays are placed on top and taken from the top.
Stack Operations
The main operations are:
- push(): Put an element on the top of the stack
- pop(): Take the topmost element from the stack
- topEl(): Return the topmost element without removing it
- isEmpty(): Check if the stack is empty
- size(): Return the number of elements
- clear(): Clear the stack
How Push Works
Before inserting an element, check if the stack is full (overflow condition). When pushing, the top pointer is incremented by 1, and the element is placed at the new top position.
How Pop Works
Before removing an element, check if the stack is empty (underflow condition). If not empty, access the element at the top, then decrement the top pointer.
Applications of Stacks
- Undo/Redo operations in text editors
- Matching delimiters in compilers (parentheses, brackets, braces)
- Navigation history in browsers
- Function call management in programming
Meaning and Structure
A queue is an abstract data structure open at both ends. It follows the First-In-First-Out (FIFO) methodology—the data item stored first will be accessed first. Elements can enter a queue only at the rear and leave only at the front.
Real-world examples include:
- People waiting in line at a bank
- Print jobs waiting in a printer queue
- Processes waiting for CPU time in an operating system
Queue Operations
- Enqueue (Insert): Add an element at the rear end
- Dequeue (Delete): Remove an element from the front end
- size(): Get the number of elements
- clear(): Remove all elements
Types of Queues
- Linear Queue: Standard queue where insertion and deletion happen at opposite ends
- Circular Queue: The last position connects back to the first, forming a circle
- Priority Queue: Elements are removed based on priority rather than order
Meaning and Structure
A tree is a non-linear data structure that represents data in a hierarchical manner with parent-child relationships. Unlike linear structures, trees do not store data in a sequential order. Each tree has nodes connected by edges, with one special node called the root (the topmost node with no parent).
Key terms in trees:
- Root: The topmost node
- Parent: A node with children
- Child: A node connected below a parent
- Leaf: A node with no children
- Height: The length of the longest path from root to leaf
- Depth: The length of the path from root to a node
Binary Trees
A binary tree is a tree in which each internal node is allowed to have at most two child nodes. The children are called the left child and the right child.
Binary Tree Traversals
Traversal means visiting all nodes in a systematic order. There are three main types:
- Preorder (Root → Left → Right): Visit root first, then left subtree, then right subtree
- Inorder (Left → Root → Right): Visit left subtree, then root, then right subtree
- Postorder (Left → Right → Root): Visit left subtree, then right subtree, then root
Example: For a binary tree with root 10, left child 20, and right child 30:
- Preorder: 10, 20, 30
- Inorder: 20, 10, 30
- Postorder: 20, 30, 10
Applications of Binary Trees
- Binary Search Trees (BST): Efficient searching, insertion, and deletion
- Expression Trees: Evaluating arithmetic expressions
- Decision Trees: Used in machine learning and game AI
- File Systems: Organising folders and files hierarchically
- Heap Sort: Using binary heaps for sorting
| Feature | Linked List | Stack | Queue | Tree |
|---|---|---|---|---|
| Type | Linear | Linear | Linear | Non-linear |
| Access | Sequential | Top only | Front/Rear | Hierarchical |
| Order | By links | LIFO | FIFO | Parent-child |
| Insertion/Deletion | Easy | Easy (top) | Easy (ends) | Complex |
Choosing the appropriate data structure depends on the nature of your data and the operations you need to perform. Use linked lists when the size changes frequently. Use stacks for reverse-order processing. Use queues for fair sequential processing. Use trees for hierarchical relationships.
In Tanzania, a queue data structure is used in mobile money agents' shops (such as M-Pesa or Tigo Pesa) where customers form a line and the first person to arrive is served first. Similarly, a tree data structure is used in organisational apps like M-Farm or market price apps that arrange products or prices in a hierarchical manner, allowing farmers to quickly find market prices at different levels (region → district → market).
Swali
What is the correct order of node visitation for preorder traversal in a binary tree?
Ingia ili kuwasilisha jibu lako na lihesabiwe katika umahiri wako.
Ingia ili kufanya mazoeziMwalimu
Umekwama? Niulize chochote kuhusu mada hii.
Ingia ili kumuuliza Mwalimu wa AI wa Sonza kuhusu swali hili.
Ingia ili kuuliza