Linked Lists, Stacks & Queues · question

Question 7 of 78

What do insertion and deletion cost in a linked list versus an array?

beginner

← All Linked Lists, Stacks & Queues questions

Re-explain

Inserting or deleting in a linked list costs O(1) once you hold the right node. You rewire a pointer or two and you are done. Nothing else moves, and the rest of the list stays where it sat.

An array behaves differently. To insert or delete in the middle, you must shift every later element over one slot. That shift costs O(n). Only changes at the very end avoid it.

The catch is reaching the node. The linked list is O(1) only after you get there, and finding it first still costs O(n) hops. Arrays trade cheap access for expensive reshaping, and linked lists do the reverse.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Linked Lists, Stacks & Queues One question at a time. Answer out loud, get graded, see what you missed.

See it - interactive diagram

Inserting D in the middle of an array and a linked list

class Node:

def __init__(self, val, next=None):

self.val, self.next = val, next

arr = ["A", "B", "C", "E", "F", None]

head = Node("A", Node("B", Node("C", Node("E", Node("F")))))

i = 3

for j in range(len(arr) - 1, i, -1):

arr[j] = arr[j - 1] # slide right

arr[i] = "D"

cur = head

for _ in range(i - 1):

cur = cur.next # one hop

node = Node("D")

node.next = cur.next

cur.next = node

Arrayslots side by side

ABCEFNone

List nodesas they sit in memory

ABCEFfree

next pointersthe list's real order

A.nextB

B.nextC

C.nextE

E.nextF

F.nextNone

1step

Both hold A, B, C, E and F. The array has one spare slot. D must go at index 3, between C and E.

1 / 10

An array insert moves every later element. A linked list insert changes two pointers, but only after walking from the head to the spot.

Other questions have diagrams like this too. Sign in to ask for one where it's missing - it's free.

Create a free account

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

If the array is sorted, how does inserting into it compare with inserting into a sorted linked list? The array finds the spot by binary search in O(log n) but still shifts O(n). The list walks O(n), then links in O(1). Both end up O(n).
In a singly linked list, how do you delete a node when you only have a pointer to that node? Name the need for the previous node's next pointer. Copying the next node's value in works, but it fails on the tail and breaks outside references.
Big-O says lists win at middle inserts. Why do arrays often still win in practice? Contiguous memory lets the CPU prefetch, so a shift is a fast block move. Each list hop follows a pointer and can miss the cache.
You said changes at the end of an array are cheap. What happens when a dynamic array runs out of room? Name the O(n) copy into a bigger array, then show how growing by a factor makes appends O(1) amortized but not O(1) worst case.
Given these costs, when would you actually pick a linked list over an array? Tie it to the workload, such as frequent splices at nodes you already hold, as in an LRU cache, and little need for indexing.

What you can say

In a linked list, inserting or deleting is O(1) once you already hold the right node, because you only rewire a pointer or two.
Nothing else moves, so the rest of the list stays where it was.
In an array, inserting or deleting in the middle means shifting every later element over by one slot, and that shift is O(n).
The only cheap place to change an array is the very end, where nothing has to shift.
The catch for the linked list is reaching that node, because finding it still takes O(n) hops.
So arrays give you cheap access and expensive reshaping, linked lists flip that, and the list only wins when you already hold the node.

Weak answers to avoid

Says list insert is O(1), full stop That skips the O(n) walk to reach the node. Say it is O(1) once you hold the node, and O(n) if you have to find it first.
Calls every array insert or delete O(n) Changes at the end need no shift. Split end operations from middle ones, or you miss the case people use most.
Ignores the previous node in a singly linked list Deleting means changing the previous node's next pointer. If you never say which node you hold, it sounds like you have not written the code.
Treats Big-O as the whole story Arrays shift contiguous memory fast and stay cache friendly, while each list hop can miss the cache. Say that real workloads often favor arrays anyway.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Linked Lists, Stacks & Queues cheatsheet.

← Back to all Linked Lists, Stacks & Queues questions

Pro · $10/mo

67 of 78 Linked Lists, Stacks & Queues answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →