Preview

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 
linked list may not be

  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