Preview

04 - Linked Lists

 1. A linked list is exactly the same as an ordinary list - there is absolutely no difference.

  FALSE

  TRUE

 2. Linked lists are used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions

  TRUE

  FALSE

 3. Read the following excerpt and see if you can fill in the blanks. 
Linked lists were developed in 1955–1956 
by Allen Newell, Cliff Shaw and Herbert 
A. Simon at RAND Corporation as the 
primary data structure for their 
Information Processing Language. 

IPL was used by the authors to develop 
several early ________________________
programs, including the Logic Theory 
Machine, the General Problem Solver, 
and a computer chess program.
randcorporation.png

  artificial intelligence

  government global policing

  general purpose

  nuclear weapons

 4. Linked lists have elements or nodes in them. Each element (node) __________________________

  ends the linked list

  is deleted upon retreival

  points to another node in the linked list

  is held in isolation

 5. Each node in a ___________ has two parts: the node item itself, and a single "pointer". The pointer tells the program where the next associated node is located.

  doubly linked list

  singly linked list

  zero based linked list

  simple (or non linear) list

 6. A _______________will have two pointers. One will reference the location of the next node and the other points to the previous node

  doubly linked list

  simple (or non linear) list

  zero based linked list

  singly linked list

 7. In a doubly linked list if the _______ node is NULL, then that is the start of the list.

  next

  duplicated

  previous

  final

 8. if the _____________ pointer is NULL, then that would indicate the end of the list.

  final

  previous

  next

  duplicated

 9. In a linked list, it is the pointers and the links they make that makes addition and deletion from a list simple - and __________________________.

  there is no need for any order whatsoever

  the order is not broken

  the order is deleted and created again at random

  the order is entirely changed, which is useful

 10. If an item is added or removed from a linked list then_______________________________

  the pointers of its neighbors are updated

  the list is duplicated, deleted and then copied

  the item is first duplicated and appended on to the end of a second list

  everything has to be deleted and initialised from scratch

 11. The main benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reorganization of the entire structure because ______________________ 
Note: You may want to look up and understand the term "contiguously"

  the data items are all exactly the same size

  the data items need not be stored contiguously in memory or on disk

  the data items can all be stored contiguously in memory or on disk

  the data items are all smaller than 4 bits

 12. Linked lists have several advantages over dynamic arrays. Fill in the blanks for this excerpt that explains an advantage. 
Insertion or deletion of 
an element at a specific point of a list, 
assuming that we have indexed a pointer 
to the node (before the one to be removed,
 or before the insertion point) already, 
is a ____________________________ (otherwise 
without this reference it is O(n)), whereas
 insertion in a dynamic array at random 
locations will require moving half of the 
elements on average, and all the elements 
in the worst case.

  O(3)

  linear-time operation

  non-linear time operation

  constant-time operation

 13. On the other hand, dynamic arrays (as well as fixed-size array data structures) allow constant-time random access, while linked lists allow only ________________to elements.

  limited access

  access via the last node

  completely random access

  sequential access

 14. Singly linked lists can be traversed in only one direction. This makes linked lists highly suitable for applications where it's useful to look up an element by its index quickly, such as heapsort.

  TRUE

  FALSE

 15. A disadvantage of linked lists is the __________________________which often makes them impractical for lists of small data items such as characters or boolean values

  excessive speed at which the nodes point to one another

  small amount of storage needed for references

  poor organisation and need for re-allocation of nodes

   extra storage needed for references,

 16. The following diagram shows that inserting a node before an existing one _______________________; instead, one must keep track of the previous node and insert a node after it.
addlinkedlistpicture.png

  can be done directly

  cannot be done directly

  can be done instantly and with no need to change references or pointers

  can be done by changing the index numbers and their orders

 17. In the following code, removeBeginning() sets list.firstNode to __________________________________ 
 function removeAfter(Node node) // remove node past this one
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 function removeBeginning(List list) // remove first node
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next // point past deleted node
     destroy obsoleteNode
deletelinkedlistpicture.png

  NULL when removing the last node in the list

  point to the next node in the linked list

  become the last node in the list (e.g. with a referenece that points to the next available NULL pointer)

  ZERO when adding the last node to the linked list

 18. In the following linked list (python) implementation, what is happening on line 18? 
class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()

list1.headval = Node("Mon")

a2 = Node("Tue")
a3 = Node("Wed")


list1.headval.nextval = a2


a2.nextval =a3

print(a2.dataval)
print(a3.dataval)

  We are linking the first node to the second node

  We are linking all the nodes with the last node

  We are linking the second node to the third node

  We are linking the third node to the second node

 19. In the following linked list (python) implementation, what is happening on line 21? 
class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()

list1.headval = Node("Mon")

a2 = Node("Tue")
a3 = Node("Wed")


list1.headval.nextval = a2


a2.nextval =a3

print(a2.dataval)
print(a3.dataval)

  We are deleting the last node and setting its value to NULL

  We are creating a first node and deleting the rest of the list

  We are linking the second node to the third node

  We are linking the third node to the second node

 20. When the following code is executed, what would the output be? 
class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

  Mon, Tues, Wed, Sun

  Sun

  Mon, Tues, Wed

  Sun, Mon, Tues, Wed


Report an error