Data Structures

• A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle
• Static data structures have a set size at the beginning of the program and cannot be changed
• Static data structures require knowing the size in advance, which can be limiting and inefficient
• Dynamic data structures do not have a limited size and can expand or shrink during the program run
• Dynamic data structures tend to be more complex to implement
• An array stores elements of the same type and is accessed through indexes with a predetermined number of elements
• A 2D array is a two-dimensional array with only one data type required
• A record can store more than one data type related to a single entity, like a customer record with fields such as Surname, age, DOB, phone number
• A queue operates on the first in first out (FIFO) or last in last out (LILO) principle
• Data items are added at the end of the queue and removed from the front
• Examples of queues include printer queue, undo & back, keyboard buffer, and CPU scheduling queue
• Pointers can be used instead of refilling memory locations with blanks (front and rear)
• Cannot add to a full queue or remove an item from an empty queue
• When initializing a queue, specify the maximum number it can hold (e.g., maxSize)
• Functions for a queue include enQueue(item), deQueue, isEmpty, isFull
• To remove from a queue, check if frontPointer is not equal to backPointer, then remove the item at frontPointer and increment frontPointer
• Linked lists are dynamic data structures that can grow to any required size
• Each element in a linked list is a node containing data and a pointer to the next node
• New items can be inserted into a linked list without rearranging all other elements
• Linked lists are more complex to program than arrays
• Each record in a linked list is called a node, with a pointer to the next node and the last node having a null pointer
• Linked lists use more memory than arrays as they store the address/reference of the next node in addition to the data
• Traversal methods for linked lists include in-order, post-order, and pre-order
• Binary trees consist of nodes and links between them, with each node having up to two others coming off it
• Access to data in binary trees is generally faster, and data can be retrieved/searched in different orders like in-order or post-order
• Binary trees have the overhead of two pointers and a more complicated access algorithm
• A stack is a data structure with items added and removed according to the last-in first-out (LIFO) or first in last-out (FILO) principle
• Items are added and removed from the top of the stack using push and pop operations
• Stacks can be used as recursive data structures
• Underflow occurs when trying to pop from an empty stack, and overflow when trying to add to a full stack
• Pointers are used to keep track of the top of the stack
• Hash tables store data in an associative array and use a hash technique to generate an index for inserting data
• Hash tables provide direct access to data via its index and are not affected by the number of items stored
• Hashing is used in associative arrays, database indexing, caches, and sets
• Hashing involves a hashing algorithm to calculate the physical location of a record based on the key field
• Data collisions occur when two data items hash to the same location, requiring an overflow area
• A suitable hashing algorithm maps component numbers onto a smaller range of addresses
• For a hash algorithm generating an address already in use, progressive overflow or moving data to an overflow area can be used
• Hashing methods can be applied to store daily sales records in a random-access file using key fields