Linear data structures store elements in sequence and are the foundation for memory management, parsing, scheduling and graph traversal. PSC questions often test stack/queue ADT operations, circular queue conditions, linked-list pointer updates and complexity.

Engineering Definitions

Linear data structure

Standard definition: A data structure whose elements are arranged in a sequential order.

Exam meaning: Elements एकपछि अर्को sequence मा राखिने structure।

Stack

Standard definition: A LIFO abstract data type where insertion and deletion occur at the top.

Exam meaning: Last-In First-Out structure: push/pop top बाट हुन्छ।

Queue

Standard definition: A FIFO abstract data type where insertion occurs at rear and deletion at front.

Exam meaning: First-In First-Out structure: enqueue rear, dequeue front।

Linked list

Standard definition: A dynamic linear structure made of nodes connected by links/pointers.

Exam meaning: Nodes र pointers बाट बनेको dynamic list।

Concept Teaching

The exam trick is to separate ADT behavior from implementation. A stack can be implemented using array or linked list. A queue can be simple, circular, deque or priority queue. Linked lists are flexible for insertion/deletion but cost extra pointer memory and slow random access.

Stack

Stack is used when most recent item must be processed first.

  • Operations: push, pop, peek/top, isEmpty, isFull.
  • Applications: function call stack, expression evaluation, parenthesis matching, undo, DFS.
  • Array stack can overflow if fixed size.
  • Linked stack grows dynamically until memory limit.
  • Pop from empty stack causes underflow.

Queue and Variants

Queue is used in scheduling and buffering.

Type Behavior Use
Simple queue FIFO Basic buffering
Circular queue Rear wraps around array Efficient fixed-size queue
Deque Insert/delete at both ends Flexible scheduling
Priority queue Serves by priority Heap implementation, CPU/event scheduling

Linked Lists

Linked lists trade direct indexing for dynamic insertion/deletion.

  • Singly linked list has next pointer.
  • Doubly linked list has previous and next pointers.
  • Circular linked list last node points back to first.
  • Insertion/deletion after known node is O(1).
  • Searching by value is O(n).
  • Random access by index is O(n), unlike array O(1).

Array vs Linked List

This comparison is very common.

Aspect Array Linked list
Memory Contiguous Non-contiguous nodes
Random access O(1) O(n)
Insertion middle May shift elements Pointer changes if node known
Overhead Low Pointer overhead
Cache locality Good Poorer
Size Fixed/dynamic depending language Dynamic naturally

Engineering Mechanism

  • Choose ADT based on access pattern.
  • Implement storage using array or nodes.
  • Maintain top/front/rear/head/tail pointers carefully.
  • Check overflow/underflow conditions.
  • Update links in correct order to avoid losing nodes.
  • Analyze operation complexity by access path.

Diagrams / Models To Draw

  • Draw stack push/pop.
  • Draw circular queue front/rear wraparound.
  • Draw singly and doubly linked list nodes.
  • Draw linked-list insertion and deletion pointer updates.

Formulas, Algorithms and Code Patterns

  • Stack push/pop: O(1).
  • Queue enqueue/dequeue: O(1) with proper front/rear.
  • Circular queue full condition often (rear + 1) mod size == front.
  • Linked list search: O(n).
  • Array random access address = base + index x element_size.
Structure Access rule Main applications
Stack LIFO Recursion, parsing, DFS
Queue FIFO Scheduling, BFS, buffering
Deque Both ends Sliding window, flexible queues
Priority queue Priority order Dijkstra, scheduling
Linked list Pointer traversal Dynamic insertion/deletion
Array Index access Fast random access

Exam Point

  • Draw pointer changes in linked list answers.
  • For circular queue, mention modulo arithmetic.
  • Differentiate stack overflow and underflow.
  • Use applications: stack for DFS, queue for BFS.
  • State complexity for each operation.

Worked Example

To insert node N after node P in singly linked list, first set N.next = P.next, then set P.next = N. Reversing the order can lose the rest of the list because the old link from P is overwritten.

Subjective Answer Pattern

  • Define linear data structure.
  • Explain stack, queue and linked list operations.
  • Compare array and linked list.
  • Give applications and complexity.
  • Show diagram for operation asked.

Common Engineering Mistakes

  • Updating linked-list pointers in wrong order.
  • Confusing stack LIFO with queue FIFO.
  • Forgetting circular queue wraparound.
  • Assuming linked list has O(1) random access.
  • Ignoring underflow/overflow conditions.

MCQ Revision

  • Stack follows which principle?
  • Queue follows which principle?
  • Which structure is used in BFS?
  • Which structure is used in function calls?
  • Linked list random access complexity?
  • Circular queue uses which arithmetic?

Final Summary

  • Stacks, queues and linked lists are core linear structures.
  • ADT behavior differs from implementation.
  • Array gives fast indexing; linked list gives flexible links.
  • Correct pointer/front/rear updates are essential.
  • Applications connect structures to algorithms.