This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Can we assume this is a non-circular, singly linked list?
• Yes
• Do we keep track of the tail or just the head?
• Can we insert None values?
• No

## Test Cases¶

### Insert to Front¶

• Insert a None
• Insert in an empty list
• Insert in a list with one element or more elements

### Append¶

• Append a None
• Append in an empty list
• Insert in a list with one element or more elements

### Find¶

• Find a None
• Find in an empty list
• Find in a list with one element or more matching elements
• Find in a list with no matches

### Delete¶

• Delete a None
• Delete in an empty list
• Delete in a list with one element or more matching elements
• Delete in a list with no matches

### Length¶

• Length of zero or more elements

### Print¶

• Print an empty list
• Print a list with one or more elements

## Algorithm¶

### Insert to Front¶

• If the data we are inserting is None, return
• Create a node with the input data, set node.next to head
• Assign the head to the node

Complexity:

• Time: O(1)
• Space: O(1)

### Append¶

• If the data we are inserting is None, return
• Create a node with the input data
• If this is an empty list
• Assign the head to the node
• Else
• Iterate to the end of the list
• Set the final node's next to the new node

Complexity:

• Time: O(n)
• Space: O(1)

### Find¶

• If data we are finding is None, return
• If the list is empty, return
• For each node
• If the value is a match, return it
• Else, move on to the next node

Complexity:

• Time: O(n)
• Space: O(1)

### Delete¶

• If data we are deleting is None, return
• If the list is empty, return
• For each node, keep track of previous and current node
• If the value we are deleting is a match in the current node
• Update previous node's next pointer to the current node's next pointer
• We do not have have to explicitly delete in Python
• Else, move on to the next node
• As an alternative, we could avoid the use of two pointers by evaluating the current node's next value:
• If the next value is a match, set the current node's next to next.next
• Special care should be taken if deleting the head node

Complexity:

• Time: O(n)
• Space: O(1)

### Length¶

• For each node
• Increase length counter

Complexity:

• Time: O(n)
• Space: O(1)

### Print¶

• For each node
• Print the node's value

Complexity:

• Time: O(n)
• Space: O(1)

## Code¶

In [1]:
%%writefile linked_list.py
class Node(object):

def __init__(self, data, next=None):
self.next = next
self.data = data

def __str__(self):
return self.data

def __len__(self):
counter = 0
while curr is not None:
counter += 1
curr = curr.next
return counter

def insert_to_front(self, data):
if data is None:
return None
return node

def append(self, data):
if data is None:
return None
node = Node(data)
return node
while curr_node.next is not None:
curr_node = curr_node.next
curr_node.next = node
return node

def find(self, data):
if data is None:
return None
while curr_node is not None:
if curr_node.data == data:
return curr_node
curr_node = curr_node.next
return None

def delete(self, data):
if data is None:
return
return
return
while curr_node is not None:
if curr_node.data == data:
prev_node.next = curr_node.next
return
prev_node = curr_node
curr_node = curr_node.next

def delete_alt(self, data):
if data is None:
return
return
if curr_node.data == data:
curr_node = curr_node.next
return
while curr_node.next is not None:
if curr_node.next.data == data:
curr_node.next = curr_node.next.next
return
curr_node = curr_node.next

def print_list(self):
while curr_node is not None:
print(curr_node.data)
curr_node = curr_node.next

def get_all_data(self):
data = []
while curr_node is not None:
data.append(curr_node.data)
curr_node = curr_node.next
return data

Overwriting linked_list.py

In [2]:
%run linked_list.py


## Unit Test¶

In [3]:
%%writefile test_linked_list.py
import unittest

def test_insert_to_front(self):
print('Test: insert_to_front on an empty list')

print('Test: insert_to_front on a None')

print('Test: insert_to_front general case')

print('Success: test_insert_to_front\n')

def test_append(self):
print('Test: append on an empty list')

print('Test: append a None')

print('Test: append general case')

print('Success: test_append\n')

def test_find(self):
print('Test: find on an empty list')
self.assertEqual(node, None)

print('Test: find a None')
self.assertEqual(node, None)

print('Test: find general case with matches')
self.assertEqual(str(node), 'a')

print('Test: find general case with no matches')
self.assertEqual(node, None)

print('Success: test_find\n')

def test_delete(self):
print('Test: delete on an empty list')

print('Test: delete a None')

print('Test: delete general case with matches')

print('Test: delete general case with no matches')

print('Success: test_delete\n')

def test_len(self):
print('Test: len on an empty list')

print('Test: len general case')

print('Success: test_len\n')

def main():
test.test_insert_to_front()
test.test_append()
test.test_find()
test.test_delete()
test.test_len()

if __name__ == '__main__':
main()

Overwriting test_linked_list.py

In [4]:
%run -i test_linked_list.py

Test: insert_to_front on an empty list
Test: insert_to_front on a None
Test: insert_to_front general case
Success: test_insert_to_front

Test: append on an empty list
Test: append a None
Test: append general case
Success: test_append

Test: find on an empty list
Test: find a None
Test: find general case with matches
Test: find general case with no matches
Success: test_find

Test: delete on an empty list
Test: delete a None
Test: delete general case with matches
Test: delete general case with no matches
Success: test_delete

Test: len on an empty list
Test: len general case
Success: test_len