# -*- coding: utf-8 -*-
"""Linked Lists.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/17MD2e14fi7n95HTvy1K_ttM0FZSYnLmm

# 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 here
# -*- coding: utf-8 -*-
"""Linked Lists.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/17MD2e14fi7n95HTvy1K_ttM0FZSYnLmm

# 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 here
# -*- coding: utf-8 -*- Linked Lists.ipynb  Automatically generated by Colaboratory.  Original file is located at     https://colab.research.google.com/drive/17MD2e14fi7n95HTvy1K_ttM0FZSYnLmm  # 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)  ``` Simple Singly Linked List Node Class     value -> int     next -> LinkedListNode # set current as a ref to self # thile there is still more nodes # traverse to the next node # create a new node and set the ref from current.next to the new node # create a new node with the value provided # set a ref to the current node # while the current nodes value is not the target # traverse to the next node # set the new nodes next pointer to point toward the current nodes next pointer # set the current nodes next to point to the new node # CODE 9571 Simple Doubly Linked List Node Class     value -> int     next -> LinkedListNode     prev -> LinkedListNode 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 Linked List hash table key/value pair # Hash table can't have fewer than this many slots A hash table that with `capacity` buckets     that accepts string keys     Implement this. # Number of buckets in the hash table 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 Return the load factor for this hash table.         Implement this. DJB2 hash, 32-bit         Implement this, and/or FNV-1. # 64-bit hash Take an arbitrary key and return a valid integer index         between within the storage capacity of the hash table. Store the value with the given key.         Hash collisions should be handled with Linked List Chaining.         Implement this. Remove the value stored with the given key.         Print a warning if the key is not found.         Implement this. # Your code here Retrieve the value stored with the given key.         Returns None if the key is not found.         Implement this. # Your code here