Scribd
Upload
8 views3 pages

Chapter1 DataStructures ShortNotes

Chapter 1 covers essential data structures including arrays, self-referential structures, and dynamic memory allocation methods like malloc and calloc. It explains abstract data types (ADTs) such as stacks and queues, and discusses linked lists and their types. Additionally, the chapter addresses time and space complexity, along with Big O and Theta notations for algorithm efficiency.

Uploaded by

gkuntalwad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Chapter1 DataStructures ShortNotes

Chapter 1 covers essential data structures including arrays, self-referential structures, and dynamic memory allocation methods like malloc and calloc. It explains abstract data types (ADTs) such as stacks and queues, and discusses linked lists and their types. Additionally, the chapter addresses time and space complexity, along with Big O and Theta notations for algorithm efficiency.

Uploaded by

gkuntalwad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Chapter 1: Data Structures - Short Notes

What is Array

An array is a collection of elements, all of the same data type, stored at contiguous memory locations. It

allows efficient access using an index, starting from 0. Arrays are static in size and used when the number of

elements is known beforehand.

Self Referential Structure

A self-referential structure is a structure that contains a pointer to a structure of the same type. It is used in

dynamic data structures like linked lists and trees.

malloc and calloc

Both are used for dynamic memory allocation in C. `malloc(size)` allocates a single block of memory and

leaves the content uninitialized. `calloc(n, size)` allocates memory for 'n' elements and initializes all bits to

zero.

ADT

An Abstract Data Type (ADT) is a model for data structures that specifies the data type and the operations

supported without revealing the implementation details. Examples include Stack, Queue, and List.

Stack

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Elements are added

(push) and removed (pop) only from the top.

Queue

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. Elements are added from

the rear (enqueue) and removed from the front (dequeue).

Linked Disk
Chapter 1: Data Structures - Short Notes

A linked disk refers to a method of storing files where each part of a file contains a pointer to the next part.

This method is used in file allocation tables in operating systems.

List

A list is a collection of data elements that can be stored in a linear or non-linear manner. Lists can be

implemented as arrays or linked lists.

Time Complexity

Time complexity describes the amount of time an algorithm takes to complete as a function of the input size

(n). It helps compare algorithm efficiency.

Space Complexity

Space complexity refers to the total memory space required by an algorithm to execute, including input data

storage and auxiliary memory.

Big O (O)

Big O notation describes the **upper bound** of an algorithm's runtime. It defines the worst-case scenario,

ensuring performance won't exceed this limit. Example: O(n^2).

Theta ()

Theta notation defines the **tight bound** of an algorithm. It expresses the average-case complexity, i.e., it

grows at the same rate both in upper and lower bounds.

Linked List and Its Types

A linked list is a linear data structure where elements (nodes) are connected using pointers. Each node

contains data and a reference (link) to the next node. Types:

1. Singly Linked List

2. Doubly Linked List


Chapter 1: Data Structures - Short Notes

3. Circular Linked List

4. Doubly Circular Linked List

You might also like