Examples
# -*- coding: utf-8 -*-
"""Copy of Linked Lists.ipynb
Automatically generated by Colaboratory.
Original file is located at
https://colab.research.google.com/gist/bgoonz/73035b719d10a753a44089b41eacf6ca/copy-of-linked-lists.ipynb
# Linked Lists
- Non Contiguous abstract Data Structure
- Value (can be any value for our use we will just use numbers)
- Next (A pointer or reference to the next node in the list)L1 = Node(34) L1.next = Node(45) L1.next.next = Node(90)
while the current node is not none
do something with the data
traverse to next node
L1 = [34]-> [45]-> [90] -> None
Node(45) Node(90)
"""
class LinkedListNode:
"""
Simple Singly Linked List Node Class
value -> int
next -> LinkedListNode
"""
def __init__(self, value):
self.value = value
self.next = None
def add_node(self, value):
# set current as a ref to self
current = self
# thile there is still more nodes
while current.next is not None:
# traverse to the next node
current = current.next
# create a new node and set the ref from current.next to the new node
current.next = LinkedListNode(value)
def insert_node(self, value, target):
# create a new node with the value provided
new_node = LinkedListNode(value)
# set a ref to the current node
current = self
# while the current nodes value is not the target
while current.value != target:
# traverse to the next node
current = current.next
# set the new nodes next pointer to point toward the current nodes next pointer
new_node.next = current.next
# set the current nodes next to point to the new node
current.next = new_node
ll_storage = []
L1 = LinkedListNode(34)
L1.next = LinkedListNode(45)
L1.next.next = LinkedListNode(90)
def print_ll(linked_list_node):
current = linked_list_node
while current is not None:
print(current.value)
current = current.next
def add_to_ll_storage(linked_list_node):
current = linked_list_node
while current is not None:
ll_storage.append(current)
current = current.next
L1.add_node(12)
print_ll(L1)
L1.add_node(24)
print()
print_ll(L1)
print()
L1.add_node(102)
print_ll(L1)
L1.insert_node(123, 90)
print()
print_ll(L1)
L1.insert_node(678, 34)
print()
print_ll(L1)
L1.insert_node(999, 102)
print()
print_ll(L1)
"""# CODE 9571"""
class LinkedListNode:
"""
Simple Doubly Linked List Node Class
value -> int
next -> LinkedListNode
prev -> LinkedListNode
"""
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
"""
Given a reference to the head node of a singly-linked list, write a function
that reverses the linked list in place. The function should return the new head
of the reversed list.
In order to do this in O(1) space (in-place), you cannot make a new list, you
need to use the existing nodes.
In order to do this in O(n) time, you should only have to traverse the list
once.
*Note: If you get stuck, try drawing a picture of a small linked list and
running your function by hand. Does it actually work? Also, don't forget to
consider edge cases (like a list with only 1 or 0 elements).*
cn p
None [1] -> [2] ->[3] -> None
- setup a current variable pointing to the head of the list
- set up a prev variable pointing to None
- set up a next variable pointing to None
- while the current ref is not none
- set next to the current.next
- set the current.next to prev
- set prev to current
- set current to next
- return prev
"""
class LinkedListNode():
def __init__(self, value):
self.value = value
self.next = None
def reverse(head_of_list):
current = head_of_list
prev = None
next = None
while current:
next = current.next
current.next = prev
prev = current
current = next
return prev
class HashTableEntry:
"""
Linked List hash table key/value pair
"""
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
# Hash table can't have fewer than this many slots
MIN_CAPACITY = 8
[
0["Lou", 41] -> ["Bob", 41] -> None,
1["Steve", 41] -> None,
2["Jen", 41] -> None,
3["Dave", 41] -> None,
4None,
5["Hector", 34] -> None,
6["Lisa", 41] -> None,
7None,
8None,
9None
]
class HashTable:
"""
A hash table that with `capacity` buckets
that accepts string keys
Implement this.
"""
def __init__(self, capacity):
self.capacity = capacity # Number of buckets in the hash table
self.storage = [None] * capacity
self.item_count = 0
def get_num_slots(self):
"""
Return the length of the list you're using to hold the hash
table data. (Not the number of items stored in the hash table,
but the number of slots in the main list.)
One of the tests relies on this.
Implement this.
"""
# Your code here
def get_load_factor(self):
"""
Return the load factor for this hash table.
Implement this.
"""
return len(self.storage)
def djb2(self, key):
"""
DJB2 hash, 32-bit
Implement this, and/or FNV-1.
"""
str_key = str(key).encode()
hash = FNV_offset_basis_64
for b in str_key:
hash *= FNV_prime_64
hash ^= b
hash &= 0xffffffffffffffff # 64-bit hash
return hash
def hash_index(self, key):
"""
Take an arbitrary key and return a valid integer index
between within the storage capacity of the hash table.
"""
return self.djb2(key) % self.capacity
def put(self, key, value):
"""
Store the value with the given key.
Hash collisions should be handled with Linked List Chaining.
Implement this.
"""
index = self.hash_index(key)
current_entry = self.storage[index]
while current_entry is not None and current_entry.key != key:
current_entry = current_entry.next
if current_entry is not None:
current_entry.value = value
else:
new_entry = HashTableEntry(key, value)
new_entry.next = self.storage[index]
self.storage[index] = new_entry
def delete(self, key):
"""
Remove the value stored with the given key.
Print a warning if the key is not found.
Implement this.
"""
# Your code here
def get(self, key):
"""
Retrieve the value stored with the given key.
Returns None if the key is not found.
Implement this.
"""
# Your code hereLast updated