Memory Layout Comparison Array vs Linked List in DSA Python - Build Both Approaches

Memory Layout Comparison: Array vs Linked List

📖 Scenario: Imagine you have a row of mailboxes (like an array) and a chain of mailboxes connected by ropes (like a linked list). You want to see how these two ways of organizing mailboxes look in memory.

🎯 Goal: You will create a simple array and a linked list with the same numbers. Then, you will print their contents to understand how data is stored and accessed differently.

📋 What You'll Learn

Create a list called array_numbers with the values 10, 20, 30, 40, 50

Create a linked list using a Node class with the same values in order

Write a function print_linked_list(head) to print linked list values separated by arrows

Print the array_numbers elements separated by arrows

Print the linked list elements separated by arrows

💡 Why This Matters

🌍 Real World

Understanding arrays and linked lists helps in choosing the right data structure for tasks like managing playlists, undo history, or memory buffers.

💼 Career

Software developers often decide between arrays and linked lists based on performance needs and memory usage in applications.

1

Create an array with numbers

Create a list called array_numbers with these exact values: 10, 20, 30, 40, 50

DSA Python

# Create the list array_numbers with values 10, 20, 30, 40, 50
# Your code here

Hint

Use square brackets [] to create a list with the given numbers separated by commas.

2

Create a linked list with the same numbers

Define a class called Node with attributes value and next. Then create linked list nodes for values 10, 20, 30, 40, 50 connected in order. Assign the first node to a variable called head.

DSA Python

array_numbers = [10, 20, 30, 40, 50]

# Define Node class and create linked list nodes connected in order
# Your code here

Hint

Create a Node class with value and next attributes. Then link nodes by setting next to the next node.

3

Write a function to print the linked list

Write a function called print_linked_list(head) that prints the linked list values separated by arrows like 10 -> 20 -> 30 -> 40 -> 50 -> None.

DSA Python

array_numbers = [10, 20, 30, 40, 50]

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

head = Node(10)
second = Node(20)
third = Node(30)
fourth = Node(40)
fifth = Node(50)

head.next = second
second.next = third
third.next = fourth
fourth.next = fifth

# Define print_linked_list(head) function to print linked list values
# Your code here

Hint

Use a while loop to go through each node until current is None. Print each value followed by an arrow.

4

Print the array and linked list

Print the array_numbers elements separated by arrows like 10 -> 20 -> 30 -> 40 -> 50 -> None. Then call print_linked_list(head) to print the linked list.

DSA Python

array_numbers = [10, 20, 30, 40, 50]

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

head = Node(10)
second = Node(20)
third = Node(30)
fourth = Node(40)
fifth = Node(50)

head.next = second
second.next = third
third.next = fourth
fourth.next = fifth

def print_linked_list(head):
    current = head
    while current is not None:
        print(current.value, end=" -> ")
        current = current.next
    print("None")

# Print array_numbers elements separated by arrows
# Then print linked list using print_linked_list(head)
# Your code here

Hint

Use a for loop to print each number in array_numbers followed by an arrow. Then print None. Finally, call print_linked_list(head).

Practice

1. Which of the following best describes the memory layout of an array compared to a linked list?

easy

A. Array stores elements in contiguous memory locations, linked list stores elements scattered with pointers.

B. Array stores elements scattered with pointers, linked list stores elements in contiguous memory.

C. Both array and linked list store elements in contiguous memory locations.

D. Both array and linked list store elements scattered randomly without pointers.

Solution

1. Step 1: Understand array memory layout

   Arrays store elements one after another in a continuous block of memory.

2. Step 2: Understand linked list memory layout

   Linked lists store elements anywhere in memory, each element points to the next.

3. Final Answer:

   Array stores elements in contiguous memory locations, linked list stores elements scattered with pointers. -> Option A

4. Quick Check:

   Array = contiguous, Linked List = scattered with pointers [OK]

Hint: Arrays are continuous blocks; linked lists use scattered nodes with pointers [OK]

Common Mistakes:

• Thinking linked lists store elements contiguously
• Confusing pointers with contiguous storage
• Assuming arrays use pointers between elements

2. Which Python code snippet correctly creates a linked list node with a value and a pointer to the next node?

easy

A. class Node:
def __init__(self, val, next):
self.val = val
self.next = next

B. class Node:
def __init__(self, val):
self.val = val
self.next = None

C. class Node:
def __init__(self):
self.val = None
self.next = None

D. class Node:
def __init__(self, val):
self.val = val
self.next = val

Solution

1. Step 1: Check constructor parameters

   class Node: def __init__(self, val, next): self.val = val self.next = next takes both value and next node pointer, which is correct for linked list nodes.

2. Step 2: Verify pointer assignment

   class Node: def __init__(self, val, next): self.val = val self.next = next assigns self.next to the passed next node, correctly linking nodes.

3. Final Answer:

   class Node: def __init__(self, val, next): self.val = val self.next = next -> Option A

4. Quick Check:

   Node needs value and next pointer parameters [OK]

Hint: Linked list nodes need value and next pointer in constructor [OK]

Common Mistakes:

• Not passing next pointer in constructor
• Assigning next pointer incorrectly
• Using value for next pointer

3. Consider this Python code creating an array and a linked list with 3 elements each. What is the output of printing their sizes?

import sys

arr = [10, 20, 30]

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

node3 = Node(30)
node2 = Node(20, node3)
node1 = Node(10, node2)

print(sys.getsizeof(arr))
print(sys.getsizeof(node1))

medium

A. Code will raise an error due to sys.getsizeof usage

B. Array size is smaller than single node size

C. Array and node sizes are equal

D. Array size is larger than single node size

Solution

1. Step 1: Understand sys.getsizeof on array

   sys.getsizeof(arr) returns size of list object plus references to elements, usually larger than single node.

2. Step 2: Understand sys.getsizeof on node

   sys.getsizeof(node1) returns size of one Node object, smaller than whole array size.

3. Final Answer:

   Array size is larger than single node size -> Option D

4. Quick Check:

   Array holds multiple elements, node is single object [OK]

Hint: Array holds multiple items, so size > single node size [OK]

Common Mistakes:

• Assuming node size includes whole list
• Thinking array size is smaller than node
• Believing sys.getsizeof causes error

4. The following code attempts to traverse a linked list but causes an error. What is the bug?

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

node3 = Node(30)
node2 = Node(20, node3)
node1 = Node(10, node2)

current = node1
while current.next is not None:
    print(current.val)
    current = current.next

medium

A. The code raises AttributeError on current.next

B. The loop causes infinite iteration

C. The loop misses printing the last node's value

D. The code prints values in reverse order

Solution

1. Step 1: Analyze loop condition

   The loop runs while current.next is not None, so it stops before last node.

2. Step 2: Check printed values

   Last node's value is never printed because loop ends before current becomes last node.

3. Final Answer:

   The loop misses printing the last node's value -> Option C

4. Quick Check:

   Loop condition excludes last node printing [OK]

Hint: Use 'while current is not None' to print all nodes [OK]

Common Mistakes:

• Assuming last node prints automatically
• Thinking loop causes error
• Believing loop prints in reverse

5. You want to store 1 million integers and frequently insert elements in the middle. Considering memory layout and performance, which data structure is better and why?

hard

A. Array, because contiguous memory improves cache performance despite costly middle insertions

B. Linked list, because scattered nodes allow fast middle insertions without shifting elements

C. Array, because it uses pointers to link elements making insertions fast

D. Linked list, because it stores elements contiguously for faster access

Solution

1. Step 1: Consider insertion cost in arrays

   Arrays require shifting elements for middle insertions, which is slow for large data.

2. Step 2: Consider linked list insertion

   Linked lists insert by changing pointers, no shifting needed, so faster for middle insertions.

3. Step 3: Consider memory layout tradeoff

   Linked lists use scattered memory but benefit insertion speed; arrays have better cache but slower insertions.

4. Final Answer:

   Linked list, because scattered nodes allow fast middle insertions without shifting elements -> Option B

5. Quick Check:

   Linked list = fast middle insertions [OK]

Hint: Linked lists excel at middle insertions; arrays need shifting [OK]

Common Mistakes:

• Choosing array for fast middle insertions
• Confusing memory layout benefits
• Assuming arrays use pointers like linked lists