1 of 35

Lecture 4-5:�Arrays & Linked Lists

2 of 35

Announcement

Goal:�Searching

Recursion

Array & Linked List

Stack & Queue

2024/10/13(MON) – Quiz 1

2

3 of 35

Arrays

3

4 of 35

Internal Implementation: Memory

Internally, all variables and constants we use in our program should be stored somewhere in memory.

For a single variable of a primitive type (int, float, …), we know its size (how many bits are needed).

3

10

a = 3

b = 10

b += 7

17

c = 1234567890L

1234567890

4

5 of 35

Array Resizing

Two problems of an array due to its fixed length

Memory wastage: if it contains only n << N valid elements
Memory shortage: if it wants to contain more than N elements

Array resizing: create another larger array and copy all the elements

L.append(3) when the current array is full.

Index	0	1	2	3	4	5	6	7	8	9
Value	0	0	0	0	0	0	0	0	-0	0

Index	0	1	2	3	4	5	6	7	8	9
Value	-7	15	2	6	-1	5	4	10	-4	21

L

Index	0	1	2	3	4	5	6	7	8	9
Value	-7	15	2	6	-1	5	4	10	-4	21

10
0

10
3

Create a new long array O(1)

Create(copy) a new long array O(N)

Add a new element O(1)

5

6 of 35

Internal Implementation: Memory

Now, let’s think about the time complexity!

Theoretical time complexity for a.append(6)?
Actual time complexity for a.append(6), if there’s no enough space after it?

3

10

17

1234567890

1

2

3

4

5

a.append(6)

This is not ideal, since we do not have to know how memory space is being used at every moment!

O(1)

O(N)

6

7 of 35

Arrays

An array is an object comprising a numbered sequence of memory boxes

More fundamental data structure that Python lists are built on.
This is why we can easily access the i-th element of list A by using A[i].�

An array comprises

Fixed integer length (N) – should be set when initializing it
A sequence of N memory boxes (numbered 0 through N - 1)

Array�(Fixed length)

List�(Dynamic length)

Resizing

Shifting

Copying

7

8 of 35

Array Resizing

Array resizing is expensive: new memory boxes and copy operation

Increasing size by one every time is not efficient (too many resizing)
Increasing size too much at once is not efficient either (memory wastage)�

To resize fewer, Python list size grows as 0, 4, 8, 16, 25, 35, 46, 58, …

Mild over-allocation proportional to the current size�

Anyway, is there any better way of organizing a collection of data to support append and pop easily?

8

9 of 35

Linked Lists

9

10 of 35

Linked Lists

Main idea:

Allow each element in the list to be scattered in the memory.
Instead, each element points to the next one.

3

10

17

1234567890

1

2

3

4

5

l.append(5)

1

2

7

3

4

5

4

5

7

2

13579246810

l.append(7)

l.append(2)

10

11 of 35

Linked Lists

Class Node

Because we always need to store the item and the pointer to the next node, let’s make this as a class!

class Node():

def __init__(self, x):

self.item = x

self.next = None

a = Node(5)

b = Node(6)

a.next = b

5

a

6

b

print(a.item)

print(a.next.item)

5

6

item

12 of 35

Review: Python Object Reference

p = Node(5)

p = Node(6)

p.item

q.item

5

6

q = p

6

q = Node(9)

6

9

p = None

Error!

9

q = p

Error!

12

13 of 35

Singly Linked List

Let’s design the singly linked list data structure. What functionalities do we need?

Creating an empty list
Adding / inserting a new item
Retrieving an item
Deleting / removing an existing item

5

a

6

item

7

at position i

13

14 of 35

Singly Linked List

Class LinkedList

We keep only the reference to the first node.
At creation, first node is None, having no element in the list.

class Node():

def __init__(self, x):

self.item = x

self.next = None

class LinkedList():

def __init__(self):

self.first = None

def insert(self, x, i):

# insert x at [i]

def get(self, i):

# get item at [i]

def delete(self, i):

# delete item at [i]

5

first

6

item

15 of 35

Inserting an Item at position i

Step 1: Creating a new node with the given item.

Step 2: Traverse to the (i - 1)-th position.

Step 3: Set the new node’s next as the original i-th node.

Step 4: Update the (i - 1)-th node’s next as the new node.

Example:�insert “4” at position 2.

5

first

6

item

7

4

curr

15

16 of 35

Inserting an Item at position i

Step 1: Creating a new node with the given item.
Step 2: Traverse to the (i - 1)-th position.
Step 3: Set the new node’s next as the original i-th node.
Step 4: Update the (i - 1)-th node’s next as the new node.

def insert(self, x, i):

# insert x at [i]

new_node = Node(x)

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1

new_node.next = curr.next

curr.next = new_node

class Node():

def __init__(self, x):

self.item = x

self.next = None

5

first

6

item

7

4

curr

new_node

Step 1

Step 2

Step 3

Step 4

16

17 of 35

Does this work at the end?

Step 1: Creating a new node with the given item.

Step 2: Traverse to the (i - 1)-th position.

Step 3: Set the new node’s next as the original i-th node.

Step 4: Update the (i - 1)-th node’s next as the new node.

Example:�insert “4” at position 4.

5

first

6

item

7

4

curr

17

18 of 35

Does this work at the beginning?

Step 1: Creating a new node with the given item.

Step 2: Traverse to the (i - 1)-th position.

We need special treatment when we insert at position 0!

Example:�insert “4” at position 0.

5

first

6

item

7

4

curr

i - 1 = -1 😨

18

19 of 35

Inserting an Item at position i

If inserting at the first position:

Step 1: Creating a new node with the given item.
Step 2: Set the new node’s next as the original first node.
Step 3: Update the first node reference to the new node.

else:

Step 1: Creating a new node with the given item.
Step 2: Traverse to the (i - 1)-th position.
Step 3: Set the new node’s next as the original i-th node.
Step 4: Update the (i - 1)-th node’s next as the new node.

Check: does this work when we insert the very first item (that is, does it work when self.first = None)?

def insert(self, x, i):

# insert x at [i]

if i == 0:

new_node = Node(x)

new_node.next = self.first

self.first = new_node

else:

new_node = Node(x)

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1

new_node.next = curr.next

curr.next = new_node

19

20 of 35

Inserting an Item at position i

Check: what happens with our code if i > last position?

It will crash here, when it tries to access None.next

We should prevent this, instead of letting the users to be responsible!

def insert(self, x, i):

# insert x at [i]

if i == 0:

new_node = Node(x)

new_node.next = self.first

self.first = new_node

else:

new_node = Node(x)

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1

new_node.next = curr.next

curr.next = new_node

7

curr

…

None

20

21 of 35

Size Variable

First try:

Let’s add a check at the beginning, if i is within the valid range.
Valid range?

But, how do we know the size?

A naive way: traverse from the first until we meet None.
This is not efficient, since we need to traverse N items whenever we insert a new item, regardless of the target position. 😨
Any better way?

def insert(self, x, i):

# insert x at [i]

� if i == 0:

new_node = Node(x)

new_node.next = self.first

self.first = new_node

else:

new_node = Node(x)

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1

new_node.next = curr.next

curr.next = new_node

From 0 to current length (item count)

if i > size: return

elif i <= size:

21

22 of 35

Size Variable

Solution: Let’s keep the size variable in the class, and maintain it whenever we insert or delete an element.
Time complexity?

class LinkedList():

def __init__(self):

self.first = None

self.size = 0

def insert(self, x, i):

# insert x at [i]

def get(self, i):

# get item at [i]

def delete(self, i):

# delete item at [i]

def insert(self, x, i):

# insert x at [i]� if i == 0:

new_node = Node(x)

new_node.next = self.first

self.first = new_node

self.size += 1

elif i <= self.size:

new_node = Node(x)

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1

new_node.next = curr.next

curr.next = new_node

self.size += 1

O(1)

22

23 of 35

Retrieving an Item at position i – Homework

Basic logic

Step 1: Traverse to the i-th position.
Step 2: Return the item in the node.�

Any special cases to consider?

Check if your implementation works when

i = 0
i > self.size
self.size = 0
…

def get(self, i):

# get item at [i]

# TODO(students): implement!

return ?

23

24 of 35

Deleting an Item at position i

Step 1: Traverse to the (i - 1)-th position.

Step 2: Set the (i - 1)-th node’s next as the target’s next.

Example:�delete item at position 2.

This node is no longer accessible. “3” is no longer in your list!

5

first

6

item

7

curr

24

25 of 35

Deleting an Item at position i

Step 1: Traverse to the (i - 1)-th position.
Step 2: Set the (i - 1)-th node’s next as the target’s next.

def delete(self, i):

# delete item at [i]

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1�

curr.next = curr.next.next

self.size -= 1

class Node():

def __init__(self, x):

self.item = x

self.next = None

5

first

6

item

7

curr

Any edge case here?

Step 2

Step 1

25

26 of 35

Does this work at the end?

Step 1: Traverse to the (i - 1)-th position.

Step 2: Set the (i - 1)-th node’s next as the target’s next.

Example:�delete item at position 3.

5

first

6

item

7

curr

26

27 of 35

Does this work at the beginning?

Step 1: Traverse to the (i - 1)-th position.

Step 2: Set the (i - 1)-th node’s next as the target’s next.

Example:�delete item at position 0.

Again, we need special treatment when we delete the first one!

This condition is never satisfied.

5

first

item

i - 1 = -1 😨

def delete(self, i):

# delete item at [i]

pos = 0

curr = self.first

while pos < i - 1:

curr = curr.next

pos += 1�

curr.next = curr.next.next

self.size -= 1

if i == 0:

self.first = self.first.next

else:

...

27

28 of 35

Time Complexity

Time complexity of Linked List?

Happen when?

Task	Worst case	Average case	Best case
Insertion
Retrieval
Deletion

O(N)

O(1)

28

29 of 35

Doubly Linked List

Sometimes it is useful to have ability to access previous items.
No asymptotic benefit on complexity.

29

30 of 35

Comparison

Array

Consecutive memory space is assigned.
Fixed length
Random access is supported in O(1).
Suffers from item shifting.�

Linked list

Scattered in the memory space.
Additional space is needed for storing the next reference.
No random access allowed. (Linear traversal is required, taking O(N).)
No shifting is needed even with size change.

30

31 of 35

Applications of Linked Lists��Code: https://colab.research.google.com/drive/16mXIWEEsKeH52HPPdpVA7EEvDTckGWnH?usp=sharing

31

32 of 35

Application Questions

Print the middle of a given linked list. (Assume list size is not maintained.)

Brute-force solution

Traverse the entire list to count the number of elements.
Traverse half of them again.
→ O(N)

5

7

2

8

2

4

9

32

33 of 35

Application Questions

33

34 of 35

Application Questions

Reverse a given linked list.

5

7

2

8

2

4

9

4

2

8

2

7

5

34

35 of 35

Application Questions

Detect if there is a cycle in the given linked list.

5

7

2

8

2

4

9

35