Fundamentals of Data Structures

Fundamentals of Data Structures

1. A Data Structure is a collection of elementary data types such as integer, real, Boolean or char.

2. An array is defined as a finite, ordered set of elements of the same type

   • They can have a number of dimensions (i.e: 1-D, 2-D, etc...)
   • In 2-D arrays, elements can be referred to by their row and column number
   • More generally, an n-dimensional array is a set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements

3. A dynamic data structure refers to a collection of data in memory that has the ability to grow or shrink in size

   • It does this with the aid of the heap - which is the portion of memory from which space is automatically allocated or de-allocated as required

4. A static data structure such as static arrays, are fixed in size and cannot increase in size or free up memory while the program is running.

   • An array is suitable for storing fixed number of items such as the months of the year
   • The disadvantage of using an array is that to implement a dynamic data structure such as a queue is that the size of the array has to be decided in advance

5. If you want to store data permanently so that you can read or update it at a future date, the data needs to be stored in a file on disk

   • Generally, a file consists of a number of records. A record contains a number of fields each holding one item of data

6. Programming languages all have built in elementary data types and some built in composite data types

7. Abstract data types such as queues, stacks, trees and graphs can be easily show in graphical form

8. An abstract data type is a logical description of how the data is viewed and the operations that can be performed on it

9. Queues

   • First in First Out data structure
   • New elements may only be added to the end of a queue and elements may only be retrieved from the front of the queue
   • A linear queue can be implemented in two ways: either by moving all the elements one place in the array (this may take a long time if large queue) or by moving the pointers which would leave unusable data
   • A circular queue can over come some limitations of a linear queue
   • A priority queue acts much like a regular queue but is ordered by priority. The highest priority at the front with the lowest priority at the end. This means that items can be added to the front of the queue.

10. Lists

    • A list is an abstract data type consisting of a number of items in which the same item may occur more than once
    • Items can be added in any place in the list and can be removed from any place
    • Linked lists can be used to abstract the detail out from the list by linking an element in a list to another list
      • As new nodes are added, new memory locations can be dynamically pulled from the heap - a poll of memory locations which can be allocated or deallocated as required

11. Stacks

    • A stack is a Last in First Out data structure
    • Stacks are used in calculations, and to hold return addresses when subroutines are called
    • A stack may be implemented as either a static or dynamic data structure
      • A static data structure such as an array can be used with two additional variables, one being the pointer to the top and the other holding the size of the array
    • Stacks will always have a max size and so overflow errors can occur. This is when data is added to a full stack. An underflow error can also occur when the stack is trying to recieve data from an empty stack

12. Hash tables and Dictionaries

    • Large collections of data, need to be accessible very quickly without looking through all the records. This can be done by holding an index of the physical address on the file where the data is held.
      • The index is created by a hashing algorithm which is applied to the value in the key field of each record to transform it into an address
    • When two values hash to the same address, this is called a synonym and is referred to as a collision. A simple solution is to store the item in the next address if possible
    • There are a number of hashing methods
      • Folding method divides the item into equal parts and adds the parts to produce a value.
    • Hashing a string involves converting the string into ascii and then hashing
    • A dictionary is an abstract data type which consists of associating pairs of items - a key and a value

13. Graphs

    • A graph is a set of nodes connected by edges/arcs. The edges may be one way or two way.
    • In an undirected graph, all edges are bidirectional
    • If all the edges in a graph are one way, the graph is said to be directed or digraph
    • There are two ways to implement a graph: an adjacency matrix or an adjacency list
      • In the case of an undirected graph, the adjacency matrix will be symmetric and in an unweighted graph, it may be represented with 1s and 0s
    • Applications of graphs
      • computer networks
      • roads between towns (maps)
      • tasks in a project
      • Finite state machines
      • Web pages and links
    • The Google's PageRank Algorithm

14. Trees

    • A rooted tree has a root, branches and leaves.
    • Typical uses of rooted trees are
      • Manipulating hierarchical data
      • Making information easy to search
      • Manipulating sorted lists of data
    • A tree is a connected, undirected graph with no cycles
    • A binary search tree is a rooted tree in which each node has no more than 2 children
    • Tree traversal
      • Pre-order traversal (left of each node from the top)
      • In-order traversal (middle of each node from the top)
      • Post-order traversal (right of each node from the top)
    • Post-order traversal is used in program complication of Reverse Polish notation

15. Vectors

    • Applications of vectors involve processing spatial information
    • Dot product of two vectors is found by multiplying both the vectors and adding all the values together