Arrays, linked lists, stacks and queues: what each operation costs

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• 1 + 2 + … + n = ? from Lesson 0.1.2
• How many times does a loop doubling i from 1 up to n run? from Lesson 0.1.2
• What is an instance? from Lesson 0.1.1

1 · The Hook

🎣

An algorithm is only as fast as the operations it uses. "Insert at the front" costs one step in a linked list but n steps in an array. Before analysing algorithms we need a price list for the basic structures. This lesson is that price list for linear structures.

2 · Predict First

🤔

An array holds n elements in positions 0 … n−1 with space to spare. How many elements must move to insert a new element at position 0? At the end?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

At position 0 every element shifts right by one: n moves. At the end: 0 moves (just write into position n).

Arrays

Elements sit in consecutive memory; A[i] is found by arithmetic (Lesson 0.1.1's "one step").

Linked lists

Each node holds a value and a pointer to the next node (doubly linked: also to the previous).

Stacks and queues

• Stack (LIFO): push and pop at one end: constant time with an array or a linked list.
• Queue (FIFO): enqueue at the rear, dequeue at the front: constant time with a circular array or a linked list with head and tail pointers.

Here "constant" means a fixed number of steps independent of n; Phase 1 writes it O(1).

4 · Visual

Array insert at index 1 (n = 5):
 before: [ a | b | c | d | e |   ]
 after : [ a | X | b | c | d | e ]     b, c, d, e each moved: 4 shifts

Singly linked list: head -> [a] -> [b] -> [c] -> [d] -> NULL
 insert at front: new node points to [a], head points to new node: 2 pointer changes

5 · Worked Examples

Example 1 Easy

An array of 1,000 elements: how many shifts to delete the element at index 10?

Solution

Elements at 11 … 999 move left: 989.

Example 2 Medium

A singly linked list has only a head pointer. Which is slow (proportional to n): inserting at the front, or deleting the last node?

Solution

Deleting the last node: you must walk to the second-last node to update its pointer.

Example 3 GATE

A queue is built with a singly linked list with only a head pointer, enqueuing at the tail. What does each enqueue cost for a queue of n elements?

Solution

About n steps (walk to the tail) unless a tail pointer is kept; with a tail pointer it is constant.

6 · GATE Traps

⚠️

• Array access is constant; inserting in the middle is not.
• A singly linked list cannot delete a node without its predecessor.
• Queues need a tail pointer (or circular array) for constant-time enqueue.
• "Constant" means independent of n, not "one step".

7 · Memory Hook

🧠

"Arrays jump, lists walk." Index is instant in an array; position k is k steps in a list.

8 · Connect the Dots

This lesson priced linear structures. Next: trees, binary search trees and binary heaps, where costs depend on the height.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markShifts

Inserting into position 0 of an array holding 250 elements requires how many shifts?

Numerical answer: ________

Q2MCQ1 markLinked list

In a singly linked list with only a head pointer, which operation takes time proportional to n?

• (A) Delete the first node
• (B) Insert at the front
• (C) Delete the last node
• (D) Read the first element

Q3MSQ2 marksConstant-time operations

Which are constant time?

• (A) Searching an unsorted array
• (B) Dequeuing from a circular-array queue
• (C) Pushing onto a stack
• (D) Reading A[500] of an array

Q4NAT1 markAccess cost

How many pointer steps from the head reach the 8th node (the first node is the 1st) of a singly linked list?

Numerical answer: ________

Q5NAT2 marksDelete shifts

An array holds 600 elements at indices 0–599. Deleting the element at index 150 requires how many shifts?

Numerical answer: ________

10 · Rule Card

• Array: index O(1); insert/delete at k: n − k shifts; search unsorted n.
• Singly linked: front ops constant; delete needs predecessor; last node costs n.
• Doubly linked with tail: delete given node / last node constant.
• Stack push/pop and queue enqueue/dequeue (circular array or tail pointer): constant.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

array operation costsshiftingsingly linked listdoubly linked listhead and tail pointersstack (LIFO)queue (FIFO)circular array

12 · Answer Vault