DATA STRUCTURE AND ALGORITHM (REVIEWER FOR FINAL EXAM)

Data

It is a piece of information that is gathered and translated for some purpose. It can be available in different forms such as bits and bytes.

Data Structures

It is a systematic way of organizing and storing data in computer memory

Data Item

It refers to a single unit of values.

(Example: name, bday, address, age)

Elementary and Group Item

What are the two types of data items?

Elementary Item

data item, which cannot be divided into sub items.

(Example: first name, last name, gender)

Group Item

data item which can be divided into sub data items.

(Example: home address, full name)

Class

Blueprint of an object

Entity

It represents the class of certain object.

Attribute

It represents a particular property of an entity.

Field

a single characteristic of data that appears in a table as a column.

(Example: IDs of student)

Record

a collection of field values of a given entity.

(Example: profile information of student with ID#12345)

File

a collection of records of the entities in each set.

(Example: Profile information of CoE students)

Primitive and Non-Primitive data structure

What are the two categories of Data Structures?

Primitive data structure

Data structure that consists of numbers and characters which are built in programs. These can be manipulated or operated directly by the machine level instructions.

Non-Primitive data structure

These are derived from primitive data structures.

These data structures cannot be operated or manipulated directly by the machine level

instructions. It is also responsible for organizing the group of homogeneous and heterogeneous data elements.

homogeneous data structure

data structure that contain only similar type of data

Heterogeneous data structure

a data structure wherein data types of elements may vary

Linear data structure

data elements are arranged sequentially or linearly.

(Example: arrays, lists, stacks, queues)

Non-Linear data structure

Data items are not arranged in sequential order and there is a hierarchical relationship between data items.

(Example: trees and graphs)

Static data structure

Data structure where the amount of data stored (and memory used to store it) is fixed

Dynamic data structure

Data structures wherein the memory size is not fixed. It can be changed in size during program execution.

1. Traversing

2. Searching

3. Inserting

4. Deleting

5. Sorting

6. Merging

What are the six operations of data structures?

Traversing

the process of accessing each data item in the data structure exactly once in a systematic manner.

Searching

the process of finding one or more data items in the given data structure.

Deleting

the process of deleting one or more data items from the given data structure.

Inserting

the process of adding a new data item to the given data structure.

Sorting

the process of arranging data items on a particular order like ascending or descending.

Merging

the process of combining data items from two same data structure.

Abstract Data Types

The process of providing only the essentials and hiding the implementation details.

(Example: Lists, stacks, queues, and maps)

Function

It is a reusable sequence of statements designed to do a particular job

main

In C++, every executable program must have a function named _____ where the program starts

small, modular chunks

Functions provide a way for us to split our programs into ___, _____ _______ that are easier to organize, test, maintain, and modify

built-in functions

C++ standard library comes with plenty of ________

Function call

an expression that tells the CPU to interrupt the current function and execute another function.

user-defined functions

Functions that you write yourself are called ______

Return type

It indicates what type of value will be returned.

caller, callee

The function initiating the function call is the ______, and the function being called is the _______

Nested function

function that is not supported by user-defined function

return statement

Inside the body of the function, we use ___________ to indicate the specific value being returned to the caller.

function parameter

a variable used in the header of a function.

return by value

When the return statement is executed, the function exits immediately, and the return value is copied from the function back to the caller. This process is called ___________.

argument

a value that is passed from the caller to the function when a function call is made.

pass by value

When a function is called, all of the parameters of the function are created as variables, and the value of each of the arguments is copied into the matching parameter (using copy initialization). This process is called _______

Container

It makes the collections of objects manageable.

Elements

Container is a class that provides data storage for a collection of unnamed objects called _______.

Array

It is a linear and homogeneous data structure that collects elements of the same data type and stores them in a contiguous and adjacent memory location.

1. One dimensional arrays 2. Two dimensional arrays

2. Multi-dimensional arrays

Array can be classified as:

One-dimensional arrays

it requires only one subscript to specify the number of elements in an array.

Multi-dimensional arrays

it requires more than one subscript to specify the number of elements in an array.

Two dimensional arrays

It is organized in the form of a matrix which can be represented as a collections of rows and columns.

1. Fixed-size

2. Elements are stored in contiguous memory location

3. insertion and deletion of elements can be problematic

What are the limitations of an array?

1. storing list of elements belonging to the same data type

2. auxiliary storage for other data structures

3. matrices

4. underlying data structure for implementing stacks and queues

What are the applications of an array?

1. C-style array

2. std::array

3. std::vector

What are the three primary array types?

c-style array

It is a fixed-size, zero-based indexed collection of elements of the same data type, which inherited from C language.

std::array

It is a fixed-size, static array container introduced in C++11, providing a safer and more feature-rich alternative to traditional C-style arrays.

std::vector

It makes arrays safer and easier to use in c++. Most flexible of the three types. Variable-size can be changed during runtime.

Structure

It is a program-defined data type that allows user to bundle multiple variables together into a single type.

Aggregate initialization

It allows us to directly initialize the members of a struct.

to do this, provide an initializer list(just a braced list with comma-separated value)

Designated initializers

It allows you to explicitly define which initialization values map to which members. These are nice because they provide some level of self-documentation and help ensure you don't inadvertently mix up the order of your initialization values.

Reference

an allias for an existing object

identical

A reference is essentially ____ to the object being referenced

to read or modify the object being referenced

What is the usage of reference?

the ampersand (&)

Operator used to declare a reference is _____.

True

(Note: As a best practice, when defining a reference, place the ampersand next to the type (not the reference variable name) as it makes it clearer that the reference is part of the type information, not the identifier.)

True or False

From the compiler perspective, it doesn't matter whether the ampersand is attached to the type name (int& ref) or the variable's name (int &ref)

False

(Once initialized, reference cannot be changed to reference to another object)

True or False: Once a reference is initialized, it can be changed to reference to another object.

dangling reference

When an object being referenced is destroyed before a reference to it, the reference is left referencing an object that no longer exists. Such a reference is called a _______.

False

(Reference is not an object)

True or False: Reference is an object

pass by reference

It allows us to change the value of an argument without making an expensive copy of an argument when calling a function.

Pass by const reference

It offers the same primary benefit of avoiding making a copy of the argument, while also guaranteeing that the function cannot change the value being referenced.

False

(ONLY allowed to READ the value, NOT to MODIFY it)

True or False: In pass by const reference, we are allowed to read and modify the value of the object being referenced.

Pointer

an object that holds a memory address as its value. It allows us to store the address of some other object to use later.

asterisk(*)

Operator used to declare a pointer

address-of operator (&)

Operator used to obtain the memory address of an object

The Dereference operator (*)

Operator used to obtain the object at a given memory address.

The arrow operator (->)

Operator used to select members from a pointer to an object, especially objects that are compound types (e.g. classes, structs)

Linked list

It is a linear data structure with elements not necessarily stored in a consecutive location in memory.

Nodes

Linked list forms a series of connected elements also known as _____.

pointers

Use to linked nodes.

1. Information Field

2. Pointer Field

What are the two node structure?

Information field

It holds the actual data

Pointer Field

it holds the address of the next node

Head

a pointer that points to the first node in the linked list

Tail

a pointer field of the last node which is usually a null pointer.

1. Singly Linked List

2. Doubly Linked List

3. Circular Linked List

4. Doubly Circular Linked List

What are the 4 types of Linked List?

Singly Linked List

the simplest type of linked list in which every node contains a data and a pointer to the next node

Doubly Linked List

a two-way linked list which holds a data and contains a pointer to the next node and a pointer to the previous node

Circular Linked List

a singly linked list that in which the last node contains the pointer to the first node

Doubly Circular Linked List

a doubly linked list that in which the last node contains the pointer to the first node

• dynamic data structure

• insertion and deletion

• memory efficient

What are the advantages of Linked List?

• traversal and reverse traversal are not easy

• memory usage

• random access is not possible

• searching is slower compared to array

What are the limitations of Linked List?

• implementation of stacks and queues

• dynamic memory allocation

• maintaining a directory

• image viewer

• previous and next page in web browser • music player

• task scheduling in operating systems

• undo/redo functions

• polynomial representations

What are the applications of Linked List?

Doubly Linked List

Which type of linked list is used for undo/redo functions?

Variable Scability Challenge

A lot of typing and very repetitive

Indexing

Allows fast and direct access to any elements. Formally known as subscript n-1

std::array initialization

std::array array_name = {list of elements};

std::vector initialization

std::vector array_name{};

Array length

Total number of elements

Struct members

allows you to perform assignments, arithmetic, comparison operations

Struct Initialization

data members are not initialized by default

need some way to initialize multiple members

always provide default values for your members

can also be initialized using another struct of the same type

Missing initializer in a initializer list

all remaining members will be value-initialized if an aggregate is initialized but the number of initialization is fewer than the number of members

we can use an empty initialization list to value-initialize all the struct members