UNIT II

LINEAR DATA
STRUCTURES
Presented by Group 2
 OVERVIEW

Array Tuple

Queue Time and Space Complexities

Stack of Linear Data Structures

Linked-list
 INTRODUCTION
Linear data structures organize data in a sequential manner, where
elements are arranged in a linear order, facilitating straightforward
access and manipulation. Common linear data structures include
arrays, stacks, queues, linked lists, and tuples. Each data structure
serves specific purposes, offering unique advantages and facing
particular limitations. The choice of structure depends on the
application's requirements, including the need for access speed,
memory efficiency, and the frequency of updates.
 ARRAYS
An array is a collection of elements stored in contiguous memory locations,
allowing for constant-time access to any element via its index.

Arrays are commonly used in applications requiring quick lookups and efficient
data storage, such as sorting and searching algorithms, matrix operations,
and managing collections of data like lists of student grades or inventory
items.

Arrays are commonly used in applications requiring quick lookups and efficient
data storage, such as sorting and searching algorithms, matrix operations,
and managing collections of data like lists of student grades or inventory
items.
 One-Dimensional Array Two-Dimensional Array
A linear structure that stores elements in a Extends the concept to a matrix format,
single row, allowing for efficient access and organizing elements in rows and columns.
manipulation of data through indexing. It is This structure is ideal for representing grids,
commonly used for storing simple lists, such tables, and matrices, making it useful in
as a series of test scores, a sequence of applications such as image processing,
numbers, or a collection of strings. game development (for board games or
maps), and solving mathematical problems
involving matrices.
Two-Dimensional Array
 QUEUE
A linear data structure that follows the First-In-
First-Out (FIFO) principle. In a queue, elements are
added from one end called the "rear" and removed
from the other end called the "front". This behavior
is similar to a real-life queue, such as a line of
people waiting for a service where the person who
comes first is served first.
 TWO TYPES OF QUEUE
Enqueue Operation Dequeue Operation
The process of adding an
element to the end of the The process of removing an
queue. In this operation, element from the front of
the element is inserted at the queue.
the position pointed to by
the rear of the queue.
 STACK
A linear data structure that follows the Last-In-First-Out (LIFO) principle. In a
stack, the last element added (pushed) to the stack is the first one to be
removed (popped). This can be visualized as a stack of plates where the last
plate placed on top is the first one to be removed.
In programming languages, stacks are used to manage function calls and
recursion. Stacks are used to implement undo functionality, just like in MS
Word, where the last change made is the first one to be undone. The back
button functionality in web browsers uses stacks to keep track of visited
websites.
 PUSH OPERATION
A stack is used to add an element to the top of the stack.
When an element is pushed onto the stack, it becomes the
new top element, and all previous elements are shifted down
one position. This operation is fundamental in maintaining the
Last-In-First-Out (LIFO) order of the stack, ensuring that the
most recently added element is always the first to be
accessed.
 POP OPERATION
Removes the top element from the stack. This operation
decreases the stack's size by one and adjusts the top pointer
to the next element in the stack. If the stack is empty,
attempting to pop an element typically results in an error, as
there are no elements to remove.
 PEEK OR TOP OPERATION
Returns the current top element of the stack without
removing it. This allows access to the most recently added
element without modifying the stack's contents, making it
useful for inspection purposes when the element needs to be
checked or used without being deleted.
 ISEMPTY OPERATION
Checks whether the stack contains any elements. It returns
true if the stack is empty (i.e., contains no elements) and false
otherwise. This operation is crucial for preventing errors when
performing pop or peek operations, as it ensures that these
operations are only attempted when the stack is not empty.
 LINKED-LIST
A fundamental data structure in computer science, consisting of a
sequence of elements called nodes. Each node contains two main
components: data and a reference (or link) to the next node in the
sequence. This structure allows for efficient insertion and deletion of
elements, as these operations do not require shifting elements as in
an array. Instead, they only involve changing the references in the
nodes.
 TYPES OF LINKED-LIST

Singly linked lists (where each node points to the next node)

Doubly linked lists (where nodes have references to both the next and
previous nodes)

Circular linked lists (where the last node points back to the first node)
Singly linked lists
Doubly linked lists
Circular linked lists
Head: The head is the first node in a linked list. It serves as the entry point
to the list. Without the head, the list would not be accessible. Another term
for the linked-list head is root. The head contains a pointer that directs to
the first node, and if the list is empty, this pointer is null.

Node: A node is a fundamental building block of a linked list. Each node

contains two main elements: data and a pointer. The data element holds
the value or information that the node is intended to store. The pointer (or
reference) element points to the next node in the sequence. This linking
mechanism allows for the creation of a chain of nodes, forming the linked
list structure.
Data: This element holds the value or information that the node is intended
to store. The type of data can vary and may include integers, strings, or
more complex data structures.
Pointer: This element points to the next node in the sequence. This linking
mechanism allows for the creation of a chain of nodes, forming the linked
list structure
Tail / Null Pointer: The tail is the last node in a linked list. Unlike other
nodes, the pointer element in the tail node points to null, indicating the end
of the list. This null pointer signifies that there are no further nodes to
traverse beyond this point. In some implementations, the tail node may also
be explicitly referenced for quick access to the end of the list.
Index: An index is a numerical representation of a node's position within
the linked list. Indexing typically starts from 0 for the head node and
increases sequentially by 1 for each subsequent node. The last node's index
is one less than the length of the list, calculated as length – 1. Indexing is
useful for locating and accessing nodes at specific positions within the list.
 In C++ Programming, you need to create a structure for Node
using struct keyword with data and next attribute. Attributes
are the variables declared within the struct. They are used to
store different pieces of data relevant to the structure. You can
access these attributes using the dot operator (.) if you have an
instance of the structure, or the arrow operator (->) if you are
working with a pointer to an instance of the structure.

struct Node: This line defines a string data: This member of the structure
structure named Node. A structure in is named data and is of type string. It holds
C++ is a user defined data type that the actual value or information that the
groups different data types together. node will store. In this case, data is a string,
In this case, the structure represents meaning it can contain text data (Alphabet,
a node in a linked list. Numeric and Special Characters).
Node next*: This member of the structure is named next and is a
pointer to another Node. The next pointer is used to link the current
node to the next node in the linked list. If the current node is the last
node in the list, next will be set to nullptr (or NULL in older C++
standards), indicating the end of the list.
Operations on linked lists typically include insertion, deletion,
searching, and traversal. Insertion can occur at the beginning, end, or
any specified position in the list. Deletion involves removing a node
from a specified position. Searching involves finding a node with a
specific value, and traversal means accessing each node in sequence to
process the data stored in the list.
 LINKED-LIST TO HOLD DIFFERENT
DATA TYPES
Union: Allows storage of different types of data in a single memory
location.

DataType Enum: Keeps track of the type of data currently stored.

Next Pointer: Links nodes together in a linked list.

Constructors: Initialize the union with different data types and set the
type accordingly.

Destructor: Ensures proper cleanup of resources, particularly for

string.
The enum DataType in the provided example is an
enumeration, which is a user-defined data type in C++
that consists of a set of named integral constants.
Enumerations are used to defiane variables that can only
take one out of a small set of possible values, which
makes the code more readable and maintainable.
 TUPLE
A tuple in C++ is a fixed-size collection of heterogeneous
values, meaning it can store multiple values of different types.
Unlike array that can only handle data of the same type, tuple
can handle and store data with different data type. This makes
tuples extremely useful for various programming scenarios
where you need to group different types of data together.
TIME AND SPACE COMPLEXITIES
IN LINEAR DATA STRUCTURES

Time Complexity Space complexity

Refers to how long it takes for your algorithm It is about how much memory your program uses
to run as the size of its input grows. Instead of while it runs. This includes storage for variables,
measuring exact seconds, you focus on data structures, function calls, and temporary
counting the computational steps, which lets data. When you store n elements in an array, you
need memory proportional to n. If you choose a
you compare efficiency without worrying
linked list instead, you also need extra memory
about the type of computer you are using.
for the pointers that link the elements together.
To talk about complexity, you use Big O, Big (Ω)Omega, and Big
(𝞗)Theta notations. Big O describes the worst case scenario, showing
how long it will take at most. Big Omega shows the best case, indicating
the fastest your algorithm can run. Big Theta is the tight bound,
meaning it stays within a certain time range for both the best and worst
cases. These notations give you a common language to describe and
compare algorithms.
Thank You
chupol

for your attention!!!