GATE CS - PROGRAMMING & DATA STRUCTURES:Arrays and Linked Lists

Mastering arrays and linked lists concepts and implementation.

Arrays and Linked Lists

GATE asks about pointer chasing, insertion cost, row-major address math, and “what does this fragment print?” Memorise the complexity table, then practise tracing given C structs — not rewriting textbook insert/delete routines from memory.

Complexity table (recite cold)

Operation	Array	Singly linked list
Access by index	O(1)	O(n)
Search (unsorted)	O(n)	O(n)
Insert at head	O(n) shifts	O(1)
Insert at tail	O(1) amortized*	O(1) with tail ptr, else O(n)
Delete at known node	O(n) shifts	O(1) if you hold prev (singly: need prev)

\*Dynamic array amortised; fixed array needs free slot.

Arrays: contiguous memory

c

int arr[10];
int *dyn = malloc(n * sizeof(int));

Row-major address for A[m][n] element A[i][j] (0-based):

Base + (i × n + j) × sizeof(element)

GATE loves asking for the address or the index given Base and size. Column-major swaps the roles of i and j in the formula — know which convention the question assumes (C is row-major).

Trace: pointer into an array

c

int a[] = {2, 4, 6, 8};
int *p = a + 1;     // points at 4
printf("%d", *p++); // prints 4, then p points at 6

Strings are char arrays ending in \0. Length is O(n) unless stored separately.

Linked lists

c

struct Node {
    int data;
    struct Node *next;
};

Insert at head is O(1): new node’s next = old head; head = new node.

Delete by value on a singly list needs the previous pointer — walk carefully so you do not lose the list. Doubly linked lists store prev and make reverse traversal / delete easier at the cost of extra memory.

Circular lists (last → first) show up in round-robin sketches.

Array vs list — pick for the question

Need random access or cache-friendly scans → array
Need frequent insert/delete at head / unknown size → list
Need both ends efficiently → consider deque / doubly list with head+tail

Cycle detection (classic)

Floyd: tortoise and hare pointers. If they meet, there is a cycle. GATE may ask whether a cycle exists or where it starts (reset one pointer to head after meeting, advance both one step).

What not to grind

Implementing every variant of insert-at-position from scratch without tracing a given snippet. Exam credit goes to correct simulation of the code on the page.

Next: Stacks and Queues, then timed questions on the GATE hub.

Progress

Previous Next: Stacks and Queues