Data structures: time complexity and memory allocation

• Data is a basic entity or fact that is used in calculation or manipulation processes.
• A data structure is a way of organizing data items by considering their relationship to each other.
• Selecting the appropriate data structure helps programmers design more efficient programs.
• Program efficiency depends on space complexity and time complexity.

Time Complexity

• Time complexity can be expressed as a function of the number of key operations performed.
• Solutions may require trade-offs between space and time efficiency.

Space Needed By A Program

• Instruction space.
• Data space.
• Environment stack space which includes the return address, lead variables, and formal parameters.

Memory allocation

• Memory allocation is a fundamental concept in programming, especially in languages like C, where memory management is explicitly handled.

• There are two primary types of memory allocation: static (compile-time) and dynamic (run-time).

• Static memory allocation example: float a[5], f;

• Dynamic memory allocation example: int *ptr = (int *) malloc (10 * sizeof (int));

• It's important to free(ptr) memory when it is no longer needed to avoid memory leaks.

• Structure example:

struct Employee {
  int Emp_Code;
  char Emp_Name[50];
  float Emp_Salary;
}

• struct Employee *str_ptr = (struct Employee *) malloc(sizeof (struct Employee));
• When executed, the above statement allocates a contiguous block of memory of size 60 bytes.

Data Structure Types

• Data Structures may be primitive or non-primitive types.
• Primitive types consist of integers, floats, characters and pointers.
• Non-primitive types consist of: arrays, lists, and files.
• Lists can be subdivided into linear and non-linear lists.
• Linear lists consist of stacks and queues.
• Non-linear lists consist of graphs and trees.

Arrays

• An array is a familiar non-primitive linear data structure.
• It is a collection of items of the same type stored contiguously in memory.

C Statement Int A[10]

• Reserving a contiguous space in memory.
• The memory size equals the element size multiplied by the number of elements.
• It assigns the starting address the name A.

C Statement A[3] = 27

• Calculates the location address: Loc address = A + 3 * sizeof(int)
• Stores the value 27 in that location.

Abstraction

• Focuses on essential features while hiding unnecessary implementation details.
• Abstraction enables developers to work at higher levels, improving system design, modularity, and ease of maintenance.

Abstract Data Types (ADT)

• Data abstraction allows the use of data structures without needing to know how they are implemented.

• An ADT is an organized data object and a set of operations for manipulating it.

• ADT = Organized data + Operations

• ADTs are defined by the operations on instances of the type rather than how those operations are implemented.

• An ADT defines the interface of the objects.

• The interface is a contract between the implementers and users of the ADT.

Information Hiding (Encapsulation)

• Hiding the data structure implementation inside the ADT is encapsulation (or information hiding).
• A program using an ADT is a "user" while a program that specifies the ADT is an "implementation."
• Use the structure at the "User Level" without worrying about the details at the "Implementation Level."
• The user level does not change even if the implementation is changed.

Advantages of Using ADTs

• Understanding detailed implementation of set operations is unneeded; only the interface needs to be studied to save time.
• ADTs can be used in many different programs.
• The implementation of a component can be changed without affecting other components.