Data Structures and Algorithms

• Data Structure

  • A way of organizing all data items that considers not only the elements stored but also their relationship to each other
  • Representation of the logical relationship existing between individual elements of data
  • affects the design of both structural & functional aspects of a program
• Program

  Algorithm + Data Structure

  
• Algorithm


  A step by step procedure to solve a particular function
• To develop a program of an algorithm, we should select an appropriate data structure for that algorithm
• Categories of Data Structures

  • Primitive Data Structure
  • Non-Primitive Data Structure
• Primitive Data Structures

  • Basic structures and directly operated upon by the machine instructions
  • Different representation on different computers
  • Examples: Integer, Floating-point number, Character constants, string constants, pointers
• Types of Non-Primitive Data Structures

  • Linear List
  • Non-Linear List
• Linear Data Structures

  • Values are arranged in linear fashion
  • Examples: Array, Linked-list, Stack, Queue, Priority queue
• Non-Linear Data Structures


  • Data values are not arranged in order
  • Examples: Hash tables, Tree, Graph
• Types of Data Structures

  • Homogenous
  • Non-Homogenous
• Homogenous Data Structures


  Values of the same types of data are stored
• Non-Homogenous Data Structures

  Data values of different types are grouped and stored
• Abstraction


  • Separating design details from usage
  • Separating the logical properties from the implementation details
• Abstract Data Type (ADT)


  • Data type that separates the logical properties from the implementation details
  • Stores data and allow various operations on the data to access and change it
  • A mathematical model, together with various operations defined on the model
  • A collection of data and associated operations for manipulating that data
  • Supports abstraction, encapsulation, and information hiding
• Operations an ADT should provide

  • Add an item
  • Remove an item
  • Find, retrieve, or access an item
  • Check if the collection is empty
  • Make the collection empty
  • Give a sub set of the collection
• Linus Torvalds: 'Bad programmers worry about the code. Good programmers worry about data structures and their relationships.'
• Non Primitive data structure

  • More sophisticated data structures
  • Derived from the primitive data structures
  • Emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items
  • The design must take operations to be performed on the data structure

  
• Pointer


  The memory address of a variable
• Pointer variable


  The content is a memory address
• There is no name associated with the pointer data type in C++
• Dynamic variables


  Variables that are created and destroyed during program execution
• Using the new and delete operators

  1. Create dynamic variables

  2. Destroy dynamic variables
• The statements int *p, q; and int *p, *q; are not equivalent
• Address of operator (&)


  Returns the address of its operand
• Dereferencing operator (*)


  Refers to the object to which its operand points
• Pointer operations

  • *p = 10;

  p = p2;

  *p2 = 20;
• Pointer operations

  • *pointer = 250;

  pointer = #
• The heap


  A special area of memory reserved for dynamically allocated variables
• The delete operator


  Eliminates a dynamic variable and returns the memory to the freestore
• Dangling pointers are pointer variables that point to dynamic variables that have been destroyed
• Dynamic arrays


  Arrays whose size is not specified when the program is written, but is determined at runtime
• The expression d + 1 evaluates to the address of d[1]
• Pointers can be used to access members of a class
• The -> operator is used to access class members through a pointer
• Linked List


  A series of connected nodes, where each node is a data structure
• Linked List


  • Can grow or shrink in size as the program runs
  • Insertion and deletion of nodes is quicker than with vectors
• Node


  A data structure that contains one or more members representing data, and a pointer to another node
• Creating a Linked List


  1. Declare a data structure for the nodes

  2. Declare a pointer to serve as the list head

  3. Create an empty linked list
• Appending a Node


  1. Create a new node

  2. Store data in the new node

  3. If no nodes in list, make new node the first node

  4. Else, traverse list to find last node and add new node
• Traversing the List


  1. Assign list head to node pointer

  2. While node pointer is not NULL, display value and move to next node