Data Types, Data Structures and Algorithms

• Computers can store whole numbers using binary. A single binary digit is called a bit, and eight binary digits can be combined to form a byte. Entertainingly, half a byte (four bits) is called a nybble.
• The least significant bit of a binary number is the one furthest to the right, while the most significant bit is furthest to the left
• An array is an ordered, finite set of elements of a single type. Unless stated in the question, arrays are always taken to be zero-indexed
• two-dimensional array can be visualised as a table or spreadsheet. searching through a 2D array, you first go down the rows and then across the columns
• three-dimensional array can be visualised as a multi-page spreadsheet and can be thought of as multiple 2D arrays. Selecting an element in a 3D array requires the following syntax to be used: threeDimensionalArray[z,y,x], where z is the array number, y is the row number and x is the column number
• A record is more commonly referred to as a row in a file and is made up of fields
• A list is a data structure consisting of a number of ordered items where the items can occur more than once. Lists are similar to 1D arrays and elements can be accessed in the same way. The difference is that list values are stored non-contiguously. This means they do not have to be stored next to each other in memory, as data in arrays is stored. Lists can also contain elements of more than one data type, unlike arrays.
• An ordered set of values of any type is called a tuple. A tuple is immutable, which means it cannot be changed: elements cannot be added or removed once it has been created. Tuples are initialised using regular brackets instead of square brackets.
• Elements in a tuple are accessed in a similar way to elements in an array, with the exception that values in a tuple cannot be changed or removed. Attempting to do so will result in a syntax error
• A stack is a last in first out (LIFO) data structure. Items can only be added to or removed from the top of the stack. Stacks are key data structures in computer science; they are used to reverse an action, such as to go back a page in web browsers
• A stack can be implemented as either a static structure or a dynamic structure. Where the maximum size required is known in advance, static stacks are preferred, as they are easier to implement and make more efficient use of memory
• Stacks are implemented using a pointer which points to the top of the stack, where the next piece of data will be inserted
• A queue is a first in first out (FIFO) data structure; items are added to the end of the queue and are removed from the front of the queue.
• A linear queue is a data structure consisting of an array. Items are added into the next available space in the queue, starting from the front. Items are removed from the front of the queue
• . Queues make use of two pointers: one pointing to the front of the queue and one pointing to the back of the queue, where the next item can be added.
• As the queue removes items, there are addresses in the array which cannot be used again, making a linear queue an ineffective implementation of a queue.
• Circular queues try to solve this. A circular queue operates in a similar way to a linear queue in that it is a FIFO structure. However, it is coded in a way that once the queue’s rear pointer is equal to the maximum size of the queue, it can loop back to the front of the array and store values here, provided that it is empty. Therefore, circular queues can use space in an array more effectively, although they are harder to implement.