Examples

ll.py

# -*- 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 here

Second Tab