Data Structures: Linked Lists and Stacks Lab

A data structure that stores data in a linear, ordered manner, but unlike arrays, linked lists allocate memory dynamically for each element. These elements are called "nodes" and contain data and a pointer pointing to the next node in the sequence.

A type of linked list where each node points to the subsequent node, ending with a null pointer, signifying the end of the list.

Similar to a singly linked list, but the last node points back to the first node, forming a cycle.

A data structure that is a collection of nodes, where the order of the nodes is maintained by means of links or pointers.

An array is a contiguous block of memory where all elements are stored next to each other. Linked lists elements are stored in separate blocks, connected via pointers.

A linked list that enables traversal in both directions, requiring a pointer to the previous and the next node.

A special type of linked list where each node has a priority level, and the node with the highest priority is at the head of the list.

A data structure that operates on a Last-In-First-Out (LIFO) principle, where the last element added is the first to be removed. Think of a stack of plates where you remove the top one first.

In a circular linked list, the head pointer acts as a starting reference point for operations, but there is no true 'first' element since the list forms a cycle.

To create a circular linked list, you follow the same steps as creating a regular linked list, but instead of setting the last node's pointer to NULL, you make it point to the head, completing the circle.

Traversing a circular linked list involves iterating through each node until the current node's next pointer points back to the head, indicating that the cycle has been completed.

The do-while loop is used to traverse a circular linked list, as it executes at least once and continues until the condition (ptr == head) is met, ensuring all nodes are visited.

A function that inserts a new node at the end of a circular linked list, maintaining the circular structure.

A function that efficiently searches for a specific data item within a circular linked list, leveraging the circular nature.

A linear data structure that allows insertion and deletion of elements only at one end, called the top. The last element added is the first one to be removed, making it a LIFO (Last-In-First-Out) structure.

The operation to add an element to the top of a stack.

The operation to remove an element from the top of a stack.

A variable that points to the top element of the stack.

A stack is considered empty when it contains no elements.

A stack is considered full when it can't hold any more elements. The maximum size of a stack is determined by its implementation.

Stacks can be implemented using either arrays or linked lists.

Stacks are an abstract data type, meaning their internal implementation is hidden, and they are defined by their operations.

A fixed-size character array that holds the expression being checked for balanced parentheses.

An integer variable used to track the current position within 'expression[]' during iteration.

A variable to count the number of opening parentheses encountered in the expression.

The loop reads each character of the expression one by one until encountering the end of the string ("\0").

Checks if the current character (expression[i]) is a left parenthesis '('. If true, it increments the 'x' variable.

Checks if the current character (expression[i]) is a right parenthesis ')'. If true, it decrements the 'x' variable.

Indicates that a balanced parenthesis condition is met when the number of opening parentheses ('x') is zero after processing the entire expression.

Indicates that a parenthesis is not balanced. This can be due to a situation where the expression ends with an unmatched opening parenthesis. It also occurs when there is a mismatch in the order of parentheses, like attempting to close a parenthesis before encountering its opening counterpart.

A priority queue where only the element with the smallest priority can be removed.

A priority queue where only the element with the highest priority can be removed.

A data structure that fulfills the heap property, ensuring a complete binary tree where each parent node is greater than its child nodes (max heap) or smaller than its child nodes (min heap).

A binary tree where all levels are completely filled except possibly the lowest one, which is filled from the left.

The process of adding a new element to a priority queue.

The process of removing the highest priority element from a priority queue.

A complete binary tree where the parent node is always greater than or equal to its child nodes, and the root node is the largest value in the tree.

A search algorithm that examines each element of a list sequentially, starting from the beginning, until the target element is found or the end of the list is reached.

The algorithm for linear search involves comparing each element in the list to the target value, returning the index if a match is found or indicating that the element is not present.

A C implementation of linear search takes an array of elements and a target value, returning the index of the target if found, or -1 if the target is not present.

A more efficient search algorithm that works on sorted lists by repeatedly dividing the search interval in half. It compares the middle element to the target value, then searches either the left or right half based on the comparison.

The algorithm starts with an interval, identifies the middle element, compares it to the target, and adjusts the search interval accordingly (lower half or upper half) until the target is found or the interval is empty.

A C implementation of binary search efficiently locates the target value in a sorted array by repeatedly halving the search interval.

The most common searching algorithms are linear search and binary search.

Linear search is generally slower than binary search because it examines each element, while binary search efficiently narrows down the search space.