# 11 - Linked Lists and Arrays

1. There are several differences between an array and a linked list. Fill in the blanks to complete the points below.
```1. A linked list is a _________ data structure whereas an array is _____
2. An array can have any element accessed ________ (i.e. random access)
whereas a linked list needs to be traversed until the
desired element is found
3. Contents of an array are stored ___________ in memory whereas the contents of a

small / depleted /directly / continuously

static / dictionary / indirectly / noncontiguously

static / dynamic / directly / contiguously

static / drastic / directly / constantly

2. A linked list maintains the memory _________ of each item in the list by using a series of '_________' within the data structure.

location / pointers

cache / points

RAM / placeholders

lists / stacks

3. A number of pointers are required, these are: (fill in the blanks for the below)
```The '______ pointer' points to the first node in the list.
The last node in the list has a '_____ pointer' (which is an empty pointer)
Each node has a pointer providing the location of the _____ node in the list.```

start / null / next

null / start / next

start / next / null

next / null / first

4. A linked list can be considered a recursive data structure because it has a recursive definition.

True

False

5. For the object orientated example below, fill in the blanks: Linked lists are made up of ______, where each node contains a r______ to the next node in the list. In addition, each node contains a unit of data called the ______.
```class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next  = next

def __str__(self):
return str(self.cargo)

>>> node = Node("test")
>>> print(node)
test```

nodes / recursion / conditons

nulls / references / carts

nodes / reference / cargo

nodes / reference / pointers

6. Analyse the code below to explain what is happening in lines 14 and 15.
```class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next  = next

def __str__(self):
return str(self.cargo)

#creating a list with more than one node
>>> node1 = Node(1)
>>> node2 = Node(2)
>>> node3 = Node(3)
#What is happening in lines 14 and 15?
>>> node1.next = node2
>>> node2.next = node3```

deleting next pointers: deleting the next pointers of nodes 1 and 2

emptying list: setting node1 and 2 to a next pointer, which sets their values to null

linking lists: setting nodes 1 and 2 to actually contain the next node itself

linking nodes: first node refers to second and the second node refers to the third:

7. Lists are useful because they provide a way to assemble multiple objects into a single entity, sometimes called a collection. In this example, the first node of the list serves as ...
```def print_list(node):
while node is not None:
print(node, end=" ")
node = node.next
print()

>>> print_list(node1)
1 2 3```

list within a list, which is in fact a linked list

a dangerous obstruction that ought to be removed

a reference to the entire list.

a pointer through which to delete or add a node

8. What is happening in the code below?
```def remove_second(list):
if list is None: return
first = list
second = list.next
# Make the first node refer to the third
first.next = second.next
# Separate the second node from the rest of the list
second.next = None
return second

>>> print_list(node1)
1 2 3
>>> removed = remove_second(node1)
>>> print_list(removed)
2
>>> print_list(node1)
1 3```

removing the third node (0,1,2) in the list and returning the remaining list

removing the second node in the list and returning a reference to the removed node

removing the second last node in the list and returning a reference to node 1

removing the second node in the list and returning all elements in the list

9. A node can refer back to an earlier node in the list, including itself. For example, in a list with two nodes, one may refer to itself: If we invoke print_list on this list, it will

cause an error as a node should not refer back to an earlier node

loop forever.

display the result of the node being referred to

loop for as many times as there are nodes

10. There are two ways to modify a linked list.We can perform operations to add, remove, or reorder the nodes or ...

delete all the null pointers to allow for modification

directly edit the next pointer for the last node

modify the pointer to allow it to hold cargo (data elements)

directly change the cargo of one of the nodes