# 06 - Linked Lists Algorithms

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

FALSE

TRUE

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

NULL node and the FULL node

the boolean flag and the node

data and a reference to the next 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
removed in memory during list traversal.```

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

updating a pointer

TRUE

FALSE

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
}
else{
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.
}

}```

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

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

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

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

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

that contains a variable containing the value NULL

pointing to the 'previous' node in the sequence

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

that signifies the end of the linked list

10. The code below is creating a _________________________
```class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None

def __init__(self):

e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node

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

node class with three linked lists

linked list with three data elements

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

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

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

def __init__(self):

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

e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node

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

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

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

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.

12. What is output when the following code is executed?
```class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None

def __init__(self):

def listprint(self):
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

e2 = Node("Tue")
e3 = Node("Wed")

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):
previous = None
found = False
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()

if previous == None:
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)

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

changes the last 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

changes the next reference of the old node to refer to the new first node of the 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):