Python - DS: Linked Lists

Question 1

An immutable sequential data structure. (a finite unchanging amount of memory is set aside for this)

Answer 1

tuple

Question 2

A mutable sequential data structure.

Answer 2

list

Question 3

A mutable non-sequential data structure, which stores unique entries.

Answer 3

set

Question 4

A mutable non-sequential data structure with unique keys mapped to arbitrary values.

Answer 4

dictionary

Question 5

A primitive data structure consisting of data and a pointer / link. The data can be of a variety of types.

Answer 5

node

Question 6

If the value of the pointer / link in a node is *null* then what does this mean?

Answer 6

That this node represents the end of some sequence or path.

Question 7

The name of the *type of node* that occurs once you remove the single link to that node. This means that any consecutive linked nodes could be “lost”.

Answer 7

orphaned node

Question 8

Code up a class that represents a Node, with value and link_node as parameters.

Define methods: get_value, get_link_nodes, set_link_nodes

Answer 8

class Node:

 def \_\_init\_\_(self, value, link\_node=None):
 self.value = value self.link\_node = link\_node

 def set\_link\_node(self, link\_node):
 self.link\_node = link\_node

 def get\_link\_node(self):
 return self.link\_node

 def get\_value(self):
 return self.value

Question 9

Which of the following methods implemented in the Node class are required to establish a Node class with an accessible but immutable value?

class Node:
 def \_\_init\_\_(self, value, link\_node=None):
 self.value = value self.link\_node = link\_node
 def get\_value(self):
 return self.value
 def get\_link\_node(self):
 return self.link\_node
 def set\_link\_node(self, link\_node):
 self.link\_node = link\_node
 def set\_value(self, value):
 self.value = value
 def increment\_value(self):
 self.value = self.value + 1

Answer 9

__init__,
get_value,
get_link_node,
and set_link_node

Question 10

What kind of data structure is comprised of a series of nodes connected together? The head node is the node at the beginning of the path. Each node contains data and a link (or pointer) to the next node in the path. The path is terminated when a node’s pointer is null. This is called the tail node.

Answer 10

linked list

Question 11

What kind of data structure is comprised of a series of nodes connected together such that there are pointers allowing you to traverse forward and backward through the path?

Answer 11

doubly linked list

Question 12

We'll be using our Node class
class Node:
 def \_\_init\_\_(self, value, next\_node=None):
 self.value = value
 self.next\_node = next\_node

 def get\_value(self):
 return self.value

 def get\_next\_node(self):
 return self.next\_node

def set\_next\_node(self, next\_node):
self.next\_node = next\_node
 \_\_\_\_\_\_\_\_\_\_\_

Create your LinkedList class below:
# Define \_\_init\_\_, get\_head\_node, insert\_beginning, stringify\_list

Answer 12

Our LinkedList class
class LinkedList:
 def \_\_init\_\_(self, value=None):
 self.head\_node = Node(value)

 def get\_head\_node(self):
 return self.head\_node

Add your insert_beginning and stringify_list methods below:
def insert_beginning(self, new_value):
new_node = Node(new_value)
new_node.set_next_node(self.head_node)
self.head_node = new_node

def stringify_list(self):
string_list = “”
current_node = self.get_head_node()
while current_node:
if current_node.get_value() != None:
string_list += str(current_node.get_value()) + “\n”
current_node = current_node.get_next_node()
return string_list

Question 13

Add a remove\_node() method to the linked\_list class. It should just remove the first node that matches the value of the input parameter value\_to\_remove.
 \_\_\_\_\_\_\_\_\_\_\_
# We'll be using our Node class
class Node:

def __init__(self, value, next_node=None):

self.value = value self.next_node = next_node def get_value(self):
return self.value

 def get\_next\_node(self):
 return self.next\_node

 def set\_next\_node(self, next\_node):
 self.next\_node = next\_node
\_\_\_\_\_\_\_\_\_\_\_
# Our LinkedList class
class LinkedList:

 def \_\_init\_\_(self, value=None):
 self.head\_node = Node(value)

 def get\_head\_node(self):
 return self.head\_node

Add your insert_beginning and stringify_list methods below:
def insert_beginning(self, new_value):
new_node = Node(new_value)
new_node.set_next_node(self.head_node)
self.head_node = new_node

def stringify_list(self):
string_list = “”
current_node = self.get_head_node()
while current_node:
if current_node.get_value() != None:
string_list += str(current_node.get_value()) + “\n”
current_node = current_node.get_next_node()
return string_list

Answer 13

Define your remove_node method below:
def remove_node(self, value_to_remove):
current_node = self.get_head_node()
if current_node.get_value() == value_to_remove:
self.head_node = current_node.get_next_node()
else:
while current_node:
next_node = current_node.get_next_node()
if next_node.get_value() == value_to_remove:
current_node.set_next_node(next_node.get_next_node())
current_node = None
else: current_node = next_node

Question 14

What would you add to the remove_node method to properly maintain the linked list when removing a node?

Answer 14

current_node.next_node = next_node.next_node

Question 15

Given this code, what would you add to complete the add_new_head method?

Answer 15

new_head_node.next_node = self.head_node

Question 16

Fix the Node class so that some_node = Node(6) can run without error.

Answer 16

Line 2 should be 
def \_\_init\_\_(self, value, next\_node=None):

Question 17

What output would you expect to see in the terminal if you ran this code?

Answer 17

90.5675.70.5.