Preview

06 - Linked Lists Algorithms

 1. A linked list is a linear data structure where each element is a separate object.

  TRUE

  FALSE

 2. Each element (i.e node) of a list is comprised of two items - the _____________________________ The last node has a reference to null.
linkedlist_question1_intro.png

  the data and the node itself

   data and a reference to the next node.

  NULL node and the FULL node

  the boolean flag and the node

 3. In a linked list the order of elements is not given by their physical placement in memory. Instead, each element points to the next

  TRUE

  FALSE

 4. Linked lists are linear and stand-alone structures which means they cannot be used to implement other abstract data types,such as stacks or queues

  TRUE

  FALSE

 5. Fill in the blanks in this excerpt on the advantages of linked lists over arrays 
Advantage of linked list over an array
=======================================

The principal benefit of a linked list over a conventional array is that the list elements 
can be easily inserted or removed without _______________________________________________
 because the data items need not be stored contiguously in memory or on disk, 
while restructuring an array at run-time is a much more expensive operation. Linked lists 
allow insertion and removal of nodes at any point in the list, and allow doing so with a
constant number of operations by keeping the link previous to the link being added or 
removed in memory during list traversal.

  updating a pointer

  the need for any changes, including the need for variables or next pointers

  the necessity to employ a queue

  reallocation or reorganization of the entire structure

 6. Linked lists are also advantageous because they allow random access to the data at any given time

  FALSE

  TRUE

 7. They use more memory than arrays because of the storage used by their pointers

  FALSE

  TRUE

 8. What is the following code implementation of a linked list doing? 
node addNode(node head, int value){
   node temp,p;// declare two nodes temp and p
   temp = createNode();// assume createNode creates a new node with data = 0 and next pointing to NULL.
   temp->data = value; // add element's value to data part of node
   if(head == NULL){
       head = temp;     //when linked list is empty
   }
   else{
       p  = head;//assign head to p 
       while(p->next != NULL){
           p = p->next;//traverse the list until p is the last node.The last node always points to NULL.
       }
       p->next = temp;//Point the previous last node to the new node created.
   }
   return head;

}

  demonstrates how to create a node in a linked list and duplicate its contents

  demonstrates how to create a node in a linked list and search for the element contained in that node

  demonstrates how to set up a linked list with two variables and a pointer

  demonstrates how to add a new node with data "value" to the end of a singly linked list

 9. In a 'doubly linked list', each node contains, besides the next-node link, a second link field _____________________

   pointing to the 'previous' node in the sequence

  that signifies the end of the linked list

  that creates a duplicate of the entire list, hence the term 'double'

  that contains a variable containing the value NULL

 10. The code below is creating a _________________________ 
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")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

  single linked node class that contains three header values and no nodes

  node class with three linked lists

  node class and a linked list that sets up two nodes (in this case e2 and e3)

  linked list with three data elements

 11. Singly linked lists can be traversed in a forward direction only starting form the first data element. We simply print the value of the next data element by ___________________ 
class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

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

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

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

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint() #with thanks to tutorialspoint.com

  assigning the value of the last node to NULL

  assigning the pointer of the last node to the next node to allow for the continuation of the sequence

  assgining the pointer of the next node to the current data element.

  assigning the pointer of the current node to the current data element

 12. What is output when the following code is executed? 
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()

  Sun,Mon,Tues,Wed

  Only 'Sun' will be printed for obvious reasons

  Mon,Tues,Wed,Sun

  Wed,Tues,Mon,Sun

 13. What is happening in line 6 and 7 of this code? 
def remove(self,item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()

    if previous == None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

  we ask whether the current data item is equal to the previous item, and if so found is set to True

  we ask whether the item stored in the next node is the item we wish to remove. If so, found can be set to True

  we ask whether the current data item is equal to the current node's index and if so set found to True

   we ask whether the item stored in the current node is the item we wish to remove. If so, found can be set to True

 14. What is happening on line 3 of this code? 
def add(self,item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp

  changes the last reference of the old node to refer to the new first node of the list

  changes the next reference of the new node to refer to the old first node of the list.

  changes the next reference of the old node to refer to the new first node of the list

  changes the first reference of the linked list to refer to the last node of the old list

 15. The question in line 5 asks whether the data item is present in the current node. If so, found can be set to True. 
def search(self,item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()

    return found

  TRUE

  FALSE


Report an error