Chapter 7 Flashcards
What is an array?
An array is defined as a finite, ordered set of elements of the same type, such as an integer, real or char.
How to write an array?
my Array = [51, 72, 35, 37, 0, 100]
X = myArray [2]
2D array?
A two dimensional array can be visualised as a table rather than a spreadsheet.
Records
A record is more commonly referred to as a row in a file and is made up of fields. Records are used in databases.
Lists
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.
Empty
List.isEmpty()
» False
Add
List.append(15)
Remove
List.remove(23)
»
Search
List.search(38)
» False
Length
List.length()
» 7
Index
List.index(23)
» 0
Returns the position of the item
Insert
insert(position, value)
Pop
pop()
pop(position)
Returns and removes the last value in the list
Tuples
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.
Linked Lists
A linked list is a dynamic data structure used to hold an ordered sequence. The items which form the sequence do not have to be in contiguous data locations. Each item is called a node, and contains a data field alongside another address called a link or pointer field
Graphs
A graph is a set of vertices/nodes connected by edges/arcs. Graphs can be placed into the following categories:
- Directed Graph: The edges can only be traversed in one direction.
- Undirected Graph: The edges can be traversed in both directions.
- Weighted Graph: A cost is attached to each edge.
Static
Structure size cannot change at runtime
Dynamic
Structure size can change at runtime
Immutable
Structure/data cannot be changed at runtime
Mutable
Structure/data can be changed at runtime
Adjacency Matrix Advantages
Easy to add nodes
Convenient to work with due to quicker access times
Adjacency List Advantages
More space efficient for large, sparse network
Stacks
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. The ‘undo’ buttons that applications widely make use of also utilise stacks. 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.
Stack operations
isEmpty()
push(value)
peek()
pop()
size()
isFull()
Queues
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. Queues are commonly used in printers, keyboards and simulators. There are a few different ways in which a queue can be implemented, but they all follow the same basic principles.
linear 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.
Circular queues
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.
Queue operations
enQueue(value)
deQueue()
isEmpty()
isFull()
Trees
A tree is a connected form of a graph. Trees have a root node which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.
Trees
A tree is a connected form of a graph. Trees have a root node which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.
Binary Tree
A binary tree is a type of tree in which each node has a maximum of two children. These are used to represent information for binary searches, as information in these trees is easy to search through. The most common way to represent a binary tree is storing each node with a left pointer and a right pointer. This information is usually implemented using two-dimensional arrays.
Traversing a binary tree
There are three methods of traversing a binary tree: Pre-order, In-order and Post-order.
A simple way of remembering these is using the outline method, which is described below.
Pre-order Traversal
Pre-order traversal follows the order: root node, left subtree, then right subtree.
Using the outline method, nodes are traversed in the order in which you pass them on the left, beginning at the left-hand side of the root node.
In-order Traversal
In-order traversal follows the order: left subtree, root node, right subtree.
Using the outline method, nodes are traversed in the order in which you pass under them, beginning at the first node from the left which does not have two child nodes.
This is useful for traversing the nodes in sequential order.
Post-order Traversal
Post order traversal follows the order: left subtree, right subtree, root node.
Using the outline method, nodes are traversed in the order in which you pass them on the right.
Hash Tables
A hash table is an array which is coupled with a hash function. The hash function takes in data (a key) and releases an output (the hash). The role of the hash function is to map the key to an index in the hash table.
Each piece of data is mapped to a unique value using the hash function. However, it is sometimes possible for two inputs to result in the same hashed value. This is known as a
collision. A good hashing algorithm should have a low probability of collisions occurring but in the event that it does occur, the item is typically placed in the next available location. This is called collision resolution.
Hash tables are normally used for indexing, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored.
Overflow
Attempting to push onto a stack that is full
Underflow
Attempting to pop from a stack that is empty
Elementary data type
integer, real, Boolean, char
Composite data type
string, array
[list may also be in this section, depending on programming language]
Abstract data type
list, stack, queue
