Data Structure and Algorithms

QUIZ 1

Data

“raw facts” - in a form of numbers, text, images, figures, or any other format, structure or unstructured

Structure

(noun) -  something arranged in a definite pattern of organization

Linear

Data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements.

Non-Linear

Data elements are not placed sequentially or linearly

Static

Has a fixed memory size. It is easier to access the elements in a static data structure.

Dynamic

The size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code.

Homogenous

Consist of the same data element type, like element collections found in an array.

Non-Homogenous

The data don’t have to be the same type, such as Linked List.

Data

Information optimized for processing and movement, facts and figures stored on computers.

Data Type

Is a classification, or attribute of data which tells the compiler or interpreter how the programmer intends to use the data.

Data Structure

A collection of different kinds of data. That entire data can be represented using an object and can be used throughout the program.

Data Type

This type is the form of a variable to which a value can be assigned.

Data Type

It can hold value but not data. Therefore, it is dataless.

Data Structure

It can hold multiple types of data within a single object.

Abstract Implementation

Implementation of Data Type

Concrete Implementation

Data Structure Implementation

Efficiency

Data structures can help to improve the efficiency of software by reducing the time and space required to perform operations on data.

Flexibility

Data structures can make software more flexible and adaptable to change.

Scalability

Data structures can help to make software more scalable, meaning that it can handle larger amounts of data and more users without becoming slower or less responsive.

Array

It is a collection of items of same data type stored at contiguous

memory locations.

Array Index

In an array, elements are identified by their indexes. Array index

Array Element

These are items stored in an array and can be accessed by their index.

Array Length

This part of an array is determined by the number of elements it can contain.

One-dimensional Array

Array as a row, where elements are stored one after another.

Two-dimensional Array

Arrays that can be considered as an array of arrays or as a matrix consisting of rows and columns.

Three-dimensional Array

Array that contains three dimensions, so it can be considered an array of two-dimensional arrays.

Traversal

Transverse through the elements of an array.

Insertion

Inserting new elements in array.

Deletion

Deleting element from the array.

Searching

Search for an element in the array.

Sorting

Maintaining the order of elements in the array.

Linked List

It is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers.

Linked List

Forms a series of connected nodes, where each node stores the data and the address of the next node.

Data

It holds the actual value or data associated with the node.

Next Pointer

It stores the memory address (reference) of the next node in the sequence.

Head

It points to the first node in the list.

Tail

It points to NULL or nullpointer, indicating the end of the list.

Singly Linked List

Each node contains a reference to the next node in the

sequence. Traversing a singly linked list is done in a forward direction.

Doubly Linked List

Each node contains references to both the next and previous nodes. This allows for traversal in both forward and backward directions, but it requires additional memory for the backward reference.

Circular Linked List

The last node points back to the head node, creating a

circular structure. It can be either singly or doubly linked.

Circular Doubly Linked List

An advanced data structure that combines the properties of a doubly linked list and a circular linked list

Insertion

Adding a new node to a linked list involves adjusting the pointers of the existing nodes to maintain the proper sequence.

Deletion

Removing a node from a linked list requires adjusting the pointers of the neighboring nodes to bridge the gap left by the deleted node.

Searching and Transversing

Searching for a specific value in a linked list involves traversing the list from the head node until the value is found or the end of the list is reached.

Dynamic Size (Linked List Advantage)

Linked lists do not have a fixed size, so you can add or remove elements as needed, without having to worry about the size of the list.

Efficient Insertion and Deletion (Linked List Advantage)

Inserting or deleting elements in a linked list is fast and efficient, as you only need to modify the reference of the next node.

Easy to Implement (Linked List Advantage)

Linked lists are relatively simple to implement and understand compared to other data structures like trees and graphs

Memory Efficiency (Linked List Advantage)

Linked lists use only as much memory as they need, so they are more efficient with memory compared to arrays, which have a fixed size and can waste memory if not all elements are used.

Flexibility (Linked List Advantage)

Linked lists can be used to implement various abstract data types, such as stacks, queues, and associative arrays.

Easy to navigate (Linked List Advantage)

Linked lists can be easily traversed, making it easier to find specific elements or perform operations on the list.

Slow Access Time (Linked List Disadvantage)

Accessing elements in a linked list can be slow, as you need to traverse the linked list to find the element you are looking for.

Pointers (Linked List Disadvantage)

Linked List use these to reference the next node, which can make them more complex to understand and use compared to arrays. This complexity can make linked lists more difficult to debug and maintain.

Higher overhead (Linked List Disadvantage)

Linked lists have a higher overhead compared to arrays, as each node in a linked list requires extra memory to store the reference to the next node.

Cache Inefficiency (Linked List Disadvantage)

Linked lists have this because the memory is not contiguous. This means that when you traverse a linked list, you are not likely to get the data you need in the cache, leading to cache misses and slow performance.

Extra memory required (Linked List Disadvantage)

Linked lists require an extra pointer for each node, which takes up extra memory. This can be a problem when you are working with large data sets, as the extra memory required for the pointers can quickly add up.