Sign in
Skip to solution
easyDSA

What is the difference between an array and a linked list?

1.1k views
01

Understand the problem

Compare arrays and linked lists.

arrayslinked-list
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

An array stores elements contiguously: O(1) index access but O(n) insert/delete in the middle and fixed/expensive resizing. A linked list stores nodes with pointers: O(1) insert/delete given a node but O(n) access and extra memory for pointers. Choose based on access vs mutation patterns.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Singly linked node + traversal
Run Playground
class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def get(head, index):          # O(n) - must walk
    cur, i = head, 0
    while cur and i < index:
        cur, i = cur.next, i + 1
    return cur.val if cur else None

def push_front(head, val):     # O(1) - just relink
    return Node(val, head)


# --- demo ---
head = Node(10, Node(20, Node(30)))   # 10 -> 20 -> 30
print(get(head, 1))            # 20
head = push_front(head, 5)
print(get(head, 0))            # 5
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 3 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track