DATA STRUCTURES

• Data structure


  a format used to store, organise and manage data in a way that allows efficient access and modification for the needs of the program
• Array


  A data structure for storing a finite, ordered set of data of the same data type within a single identifier
• Multi-Dimensional Array


  each data item is located using multiple indices
• Single-Dimensional Array


  each data item can be located using a single index
• Binary File


  An organised collection of records where data is stored in binary.
• Field


  A single item of data
• Record


  A data structure that stores multiple fields, organised based on attributes, within a single line of a file
• Text file


  An organised collection of records where data is stored in human-readable characters.
• Dictionaries


  A collection of key-value pairs in which the value is accessed via the associated key. When the user supplies the key, the associated value is returned.
• Dynamic Structures


  A data structure whose memory allocation size can change throughout the execution of the program
• Graphs


  A set of vertices or nodes connected by edges or arcs. Often used to represent more complex relationships.
• Hash Tables


  A data structure where a hashing algorithm creates a mapping between keys and values. The data item can then be directly accessed by recalculation, without any search.
• Queues


  A first-in-first-out (FIFO) data structure. The first item added/pushed on to the queue is the first to be removed/popped off
• Stacks


  A last-in-first-out (LIFO) data structure. The last item added/pushed is the first to be removed/popped off.
• Static structures


  A data structure that is allocated a fixed amount of memory space, which does not change throughout the execution of the program.
• Tree


  A connected, undirected graph with no cycles.
• Vectors


  A data structure representing a quantity with both magnitude and direction. It can be represented as a list, function or geometric point.
• Peek/Top


  An operation that allows the user to view the top element of the stack without modifying it.
• Pop


  An operation that removes the most recently added element that was not yet removed from the stack
• Push


  An operation that adds an element to the top of the stack
• Adjacency List


  A representation of a graph by storing a list of connected nodes to each node.

  
• Adjacency matrix


  A matrix representation of a graph that stores the edges connecting all possible nodes

  
• Directed graphs


  A graph where the order of the vertices paired in an edge matter. The edges are one way.
• Edge/Arc


  A connection that represents a relationship between two nodes.
• Undirected graphs


  A graph where the order of the vertices paired in an edge does not matter. The edges are bidirectional.
• Vertex/Node


  The representation of an object on a graph that is capable of being related to other such objects
• Weighted graphs


  A graph where each edge/arc has an associated value (known as its weight).
• Binary tree


  A rooted tree in which each node has at most two children.
• Rooted tree


  a tree in which one of the nodes is designated as the root
• Root node


  The only node in a rooted tree without a parent
• Primitive data type


  can only hold one value. E.g. real, boolean, char
• Composite/compound data type


  built by combining primitive data types. E.g. record, class
• Abstract data type


  a conceptual model that describes how data is organised and which operations can be carried out on the data. They make use of other data structures such as arrays to form a new way of storing data. E.g. list, stack
• Built-in data structures


  pre-defined data structures contained in most programming languages where the implementation detail is abstracted so you don't know how the structure has been built
• Static Data Structures


  reserve memory for a set amount of data

  E.g. static arrays

  Very efficient in terms of being able to access elements directly (by index)

  Can be inefficient in terms of memory use if many declared spaces aren't filled

  If not enough space is allocated, the program won't work properly
• Dynamic Data structures


  The memory capacity of a dynamic data structure is not fixed, and the number of data items that it can hold is constrained only by the overall memory allocation to the program (memory heap).

  E.g. Linked Lists

  More memory efficient as size is not predetermined

  Elements are accessed by memory location rather than index and this process is often sequential rather than direct.
• Uses of queues


  Outputs waiting to be printed.

  Characters typed at a keyboard are held in a queue in a keyboard buffer.
• Queue operations


  enQueue(x) - adds new element x to the rear of the queue

  deQueue() - removes the element from the front of the queue and returns it

  isEmpty() - checks if the queue is empty

  isFull() - checks if the queue is full
• Implementing a linear queue


  Method 1 :As items leave a queue, all the other items move up one space so that the front of the queue is always the first element of the structure.Method 2:Pointer to front and rear of the queue, an integer value of the size of the array is needed and a variable giving the current number of items in the queue.
• Circular queue


  Removes the problem of the second linear method - so that when the rear pointer is on last item of array - it will then move to pointing to the first event of the array

  More memory efficient