oop

• Data structure


  A format that contains a collection/group of data and their relationships which enables for effective ways of using algorithms to organise and manage them
• Common examples of data structures

  • Stack
  • Queues
  • Lists
  • Trees
  • Graphs
  • Vectors
• Data structures form the non-primitive category of data as they are user-defined data types
• Data structures


  • Different data structures are available in Java and they differ in the way data is organised, stored, and processed
  • Data structures have types that they can be identified with based on the data elements they store and the operations that can be applied on them
  • The complexity of algorithmic implementations of the data structures is one of the crucial studies in the field of computer science
  • Time and space complexities are the main concerns specifically, as the dataset size increases significantly
• Exercise


  1. Discuss in your group the differences between an interface and an abstract class

  2. Write down (in your notebook) the differences you have discussed

  3. Share with the class what you have written
• Data type


  Defines a certain domain of values and operations that can be applied on the values
• Abstract Data Type (ADT)


  A user-defined data type (i.e. non-primitive) which defines operations on a dataset using functions without specifying what is there inside the function and how the operations are performed
• With ADT, the user defines both the data type and the operation on the values
• Examples of ADT's


  • Queue
  • LinkedList
  • Stack
  • Trees
  • Graphs
• An interface is what will dictate what operations are necessary to the data type
• Primitive data structures


  Allow storage of only single data type values and are inbuilt in Java and directly operate according to the machine instructions
• Non-primitive data structures


  Derived from the primitive data structures and emphasis on structuring of a group of homogeneous or heterogeneous data items
• Classification of non-primitive data structures

  • Linear
  • Non-linear
• Linear data structures


  Have data elements that are arranged sequentially or linearly
• Types of linear data structures


  • Static (e.g., an array)
  • Dynamic where the memory size is not fixed, and data elements can be randomly updated during the runtime
• Non-linear data structures


  Do not have any sequence but instead data items are connected to several other data items
• Array


  A group of finite number of homogeneous data elements which are referred by a common name, fixed in size and stored in contiguous memory locations
• Common operations with arrays

  • Traversing
  • Searching
  • Insertion
  • Deletion
  • Sorting
  • Merging
• In Java, arrays are treated as objects (of the root class, i.e. object class)
• Dynamic data structures


  Have dynamic sizes and shapes, i.e. their sizes and shapes can grow or shrink during runtime to accommodate different data requirements
• Linked list


  A linear data structure where every data element is connected to its previous and next elements, made up of two parts, the data and pointer (to the next element)
• Types of linked lists

  • Singly linked list
  • Doubly linked list
  • Circular linked list
• Linked lists


  • Flexibility, efficiency in insertion and deletion, as well as its easiness to navigate
  • Direct access to data in a linked list is not possible as every element has a pointer to the next element which complicates traversal process in case a particular element has to be accessed
  • More memory is required in a linked list due to the use of pointers to store addresses of the next elements
• Stack


  A linear data structure that follows a specific order during which the operations are performed, either FILO (First In Last Out) or LIFO (Last In First Out)
• Stack operations


  • Push
  • Pop
  • Top
  • IsEmpty
• Queue


  An interface which as a data structure, implements First In First Out (FIFO) order
• Set


  A data structure that is used as a collection of objects, allowing insertion of elements and to search an element, with no duplicate elements and at most one null value
• Java Set is an interface which extends Collection interface
• Tree


  A collection of nodes arranged in a hierarchical data structure with the nodes having parent/child nodes, acyclic, and having only one path between any two vertices
• Types of trees


  • Binary tree
  • Ternary tree
  • N-ary tree (generic tree)
• Binary Search Tree (BST)


  A type of binary tree where the value of a node to the left must be less than the parent node's value as well as the value of its node to the right
• Challenge Exercise


  1. Arrange the given data set in a BST structure

  2. Determine the insertion process that would have been followed (algorithmically) if number 16 was to be inserted into the data set
• Graph


  A collection of nodes that can be directed or undirected, with no restrictions/rules for connecting the nodes through edges, and can be cyclic or acyclic
• Graphs are more complex when compared to trees because it has cycles and loops
• Some applications of graphs

  • Coloring of maps
  • Job scheduling
  • Used in algorithms of data science and machine learning
• Breadth First Search and Depth First Search are some kind of searching algorithms in graphs to traverse through each element