Introduction to Linear Data Structure
A linear data structure is a way of organising data where elements are stored in a sequential order, meaning each element is placed one after another. In this structure, every element (except the first and last) has exactly one predecessor and one successor.
A linear data structure is a type of data structure in which elements are arranged in a sequential (one-by-one) order. Each element is connected to its previous and next element, forming a straight line.
A linear data structure is a structure in which:
- Data elements are arranged in a straight line
- Each element is connected to its previous and next element
- Traversal is done sequentially
Simple Definition
A linear data structure stores data elements in a continuous sequence, where each element has a unique position.
What does “Linear” mean?
“Linear” means in a straight line. Data elements are arranged in such a way that they can be traversed (accessed) sequentially, from the first element to the last.
Basic Concept
- Data is stored in a single level
- Elements are connected one-to-one
- Access is usually sequential (though sometimes direct access is possible, like in arrays)
Common Types of Linear Data Structures
- Array – Fixed size, stored in contiguous memory
- Stores elements in contiguous memory locations
- Fast access using index
- Fixed size
- Linked List – Dynamic size, elements connected via pointers
- Elements (nodes) are connected using pointers
- Size can grow or shrink dynamically
- Stack – Works on LIFO (Last In First Out) principle
- Follows LIFO (Last In First Out)
- Operations: Push, Pop
- Queue – Works on FIFO (First In First Out) principle
- Follows FIFO (First In First Out)
- Operations: Enqueue, Dequeue
Key Features of Linear Data Structure
- Easy to implement and understand
- Elements are stored in order
- Efficient for simple data storage and traversal
- Can be static (Array) or dynamic (Linked List)
Advantages of Linear Data Structures
- Simple and easy to use
- Efficient memory utilization (in dynamic structures)
- Suitable for sequential processing
Disadvantages of Linear Data Structures
- Limited flexibility (especially arrays)
- Insertion and deletion can be time-consuming
- Not suitable for complex relationships
Key Characteristics of Linear Data Structures
- Elements are arranged sequentially
- Easy to traverse (go through elements)
- Memory can be static (array) or dynamic (linked list)
- Each element (except first and last) has one predecessor and one successor
Examples of Linear Data Structures
- Array
- Stores elements in contiguous memory locations
- Example: [10, 20, 30, 40]
- Linked List
- Elements (nodes) are connected using pointers
- Each node points to the next node
- Stack
- Follows LIFO (Last In First Out)
- Example: Stack of plates
- Queue
- Follows FIFO (First In First Out)
- Example: Line of people waiting
Real-Life Example
A train is a good example — each coach is connected in a line, and you can move from one coach to the next in sequence.
Think of a queue at a ticket counter — people stand in a line, and service is given one by one in order.
What is an Array in linear data structure?
An array is a linear data structure used to store multiple elements of the same data type in contiguous (continuous) memory locations.
It means all elements are stored one after another in memory, and each element can be accessed using an index.
Example:
A = [10, 20, 30, 40, 50]
Each element in an array has a unique index (position):
Index: 0 1 2 3
Array: [5] [10] [15] [20]
Formula to calculate address:
Address = Base Address + (Index × Size of each element)
Characteristics of Array
- Stores homogeneous elements (same data type)
- Uses contiguous memory allocation
- Supports random/direct access
- Indexing usually starts from 0
- Size is fixed (declared at compile time in many languages)
Types of Arrays
1. One-Dimensional Array (1D Array)
A simple list of elements:
int A[5] = {1, 2, 3, 4, 5};
2. Two-Dimensional Array (2D Array)
Used for matrix representation:
A[2][3] =
1 2 3
4 5 6
3. Multi-Dimensional Array
Arrays with more than two dimensions:
int A[2][2][2];
Operations on Array
1. Traversal
Accessing each element:
for(i = 0; i < n; i++)
print(A[i]);
Time Complexity: O(n)
2. Insertion
Adding a new element at a position:
- Requires shifting elements
- Time Complexity: O(n)
3. Deletion
Removing an element:
- Requires shifting elements
- Time Complexity: O(n)
4. Searching
- Linear Search → O(n)
- Binary Search (sorted array) → O(log n)
5. Updating
Changing an element value:
- Time Complexity: O(1)
Advantages of Array
✔ Fast access using index (direct access)
✔ Easy to implement
✔ Efficient memory usage for fixed-size data
Disadvantages of Array
Fixed size (cannot grow or shrink easily)
Insertion and deletion are costly
Possible memory wastage
Applications of Array
- Storing student marks
- Matrix operations
- Implementing sorting and searching algorithms
- Used in stacks, queues, and other data structures
- Example in C
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
for(int i = 0; i < 5; i++) {
printf(“%d “, arr[i]);
}
return 0;
}
Linked List in Linear Data Structure
What is a Linked List?
A linked list is a linear data structure where elements (called nodes) are stored non-contiguously (not in continuous memory).
Each node contains:
- Data (value)
- Link/Pointer (address of the next node)
Unlike arrays, linked lists do not use contiguous memory.
Each node looks like:
[ DATA | NEXT ]
Example:
10 → 20 → 30 → 40 → NULL
- First node is called Head
- Last node points to NULL
Key Characteristics
- Elements are stored dynamically
- Memory is not continuous
- Size can grow or shrink
- Each element is connected using pointers
Types of Linked List
1. Singly Linked List
Each node points to the next node only:
10 → 20 → 30 → NULL
2. Doubly Linked List
Each node has two pointers:
- One to next node
- One to previous node
NULL ← 10 ⇄ 20 ⇄ 30 → NULL
3. Circular Linked List
Last node points back to the first node:
10 → 20 → 30 → (back to 10)
Basic Operations
1. Traversal
Visiting each node
Time Complexity: O(n)
2. Insertion
Adding a node
- At beginning → O(1)
- At end or middle → O(n)
3. Deletion
Removing a node
Time Complexity: O(n)
4. Searching
Finding a value
Time Complexity: O(n)
Advantages of Linked List
✔ Dynamic size (no fixed limit)
✔ Efficient insertion/deletion (no shifting needed)
✔ Better memory utilization
Disadvantages
Extra memory required for pointers
No direct access (no indexing like arrays)
Traversal is slower than arrays
Applications
- Implementing stack and queue
- Dynamic memory allocation
- Music playlist (next/previous songs)
- Undo/redo operations
Example (C Code)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int main() {
struct Node* head = NULL;
struct Node* first = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
first->next = NULL;
head = first;
printf(“Linked List Created with value: %d”, head->data);
return 0;
}
Real-Life Example
Think of a train :
- Each coach is a node
- Each coach is connected to the next one
- Coaches are not stored in one fixed block (like array)
Stack in Linear Data Structure
What is a Stack?
A stack is a linear data structure that follows the principle of
LIFO (Last In, First Out)
This means the last element inserted is the first one to be removed.
Example:
Stack: [10, 20, 30]
Top → 30
If you remove an element, 30 will be removed first.
Think of a stack like a pile of plates :
- You add a plate on top → Push
- You remove a plate from top → Pop
Key Operations on Stack
1. Push
- Add an element to the top
- Time Complexity: O(1)
2. Pop
- Remove the top element
- Time Complexity: O(1)
3. Peek (or Top)
- View the top element without removing
- Time Complexity: O(1)
4. isEmpty
- Check if stack is empty
5. isFull
- Check if stack is full (in case of array implementation)
Representation of Stack
1. Array Implementation
- Uses array
- Fixed size
- Easy to implement
2. Linked List Implementation
- Uses nodes
- Dynamic size
- No overflow (until memory is full)
Characteristics of Stack
- Follows LIFO order
- Insertion and deletion happen only at one end (Top)
- Simple and efficient operations
Advantages of Stack
✔ Easy to implement
✔ Fast operations (Push/Pop in O(1))
✔ Useful in many applications
Disadvantages
Limited access (only top element accessible)
Fixed size (in array implementation)
Possible overflow and underflow
Applications of Stack
- Function calls (call stack)
- Expression evaluation (infix, postfix)
- Undo/Redo operations
- Parenthesis checking
- Backtracking (e.g., maze solving)
Queue in Linear Data Structure
What is a Queue?
A queue is a linear data structure that follows the principle of
FIFO (First In, First Out)
This means the first element inserted is the first one to be removed.
Example:
Queue: [10, 20, 30]
Front → 10 Rear → 30
If you delete an element, 10 will be removed first.
Think of a queue like a line at a ticket counter:
- Person joins at the back → Enqueue
- Person leaves from the front → Dequeue
Basic Operations on Queue
1. Enqueue
- Add an element at the rear (end)
- Time Complexity: O(1)
2. Dequeue
- Remove an element from the front
- Time Complexity: O(1)
3. Peek (Front)
- View the front element without removing
- Time Complexity: O(1)
4. isEmpty
- Check if queue is empty
5. isFull
- Check if queue is full (in array implementation)
Types of Queue
1. Simple Queue (Linear Queue)
- Basic FIFO structure
2. Circular Queue
- Last position connects to first
- Avoids memory wastage
3. Priority Queue
- Elements served based on priority, not order
4. Double-Ended Queue (Deque)
- Insertion & deletion from both ends
Characteristics of Queue
- Follows FIFO order
- Insertion at rear, deletion at front
- Uses two pointers: Front and Rear
Advantages of Queue
✔ Easy to implement
✔ Efficient for scheduling tasks
✔ Maintains order of data
Disadvantages
Fixed size (array implementation)
Can lead to unused space (in simple queue)
Applications of Queue
- CPU scheduling
- Printer queue
- Call center systems
- Breadth-First Search (BFS) in graphs
- Buffering (keyboard input, streaming)
What is sorting in data structure?
How to reverse a Linked list?