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)
• Pros and cons of linked lists

  • Pros: Flexibility, efficiency in insertion and deletion, easiness to navigate

  Cons: Direct access to data is not possible, more memory is required due to the use of pointers
• Types of linked lists

  • Singly linked list
  • Doubly linked list
  • Circular linked list
• 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)
• Basic operations of a stack

  • Push
  • Pop
  • Top
  • IsEmpty
• Queue


  A linear data structure that implements First In First Out (FIFO) order, with insertion (enqueue) and deletion (dequeue) performed at the rear and front ends respectively
• Set


  A data structure that is used as a collection of objects, allowing insertion of elements and searching, with no duplicate elements and at most one null value
• Java Set is an interface which extends Collection interface
• Set provides basic Set operation like union, intersection and difference between sets
• Java Collection Interface Structure
• A List in Java is an interface
• Collection is an interface extended by an interface Queue
• Non-linear data structures


  Have data elements arranged in a non-sequential order, i.e. a hierarchical structure, with data elements having multiple paths connecting to other elements and cannot be traversed in a single run
• Examples of non-linear data structures

  • Tree
  • Graph
• Tree


  A collection of nodes arranged in a hierarchical data structure with the nodes having parent/child nodes, acyclic, and used in sorting, searching, traversing and binary search
• Types of trees


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

  A 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
• Graph


  A collection of nodes (vertices) connected by edges, which can be directed or undirected, cyclic or acyclic, and used in applications like coloring of maps, job scheduling, and algorithms in data science and machine learning
• Searching algorithms in graphs

  • Breadth First Search
  • Depth First Search