Note: I do know that Python libraries provide better solutions. This implementation has been done to practice python, data structures and Algorithms.
This is a implementation of Direct-address hash tables. It simply makes a
list of size
5000000 and initializes each spot with an empty doubly linked list (for chaining).
Feel free to make any suggestions about syntax, logic, or simply anything that you think i should become aware of.
Note: Max number of elements in each table is 5000000, as direct addressing doesn't do any good when table is too big and sorting will be too crazy (I Think :-))
dt_insert(value) - inserts and chains dt_search(value) - search in table and subsequent chain dt_delete(value) - delete from table and subsequent chain hash_to_index(value) - used in other methods, only to find the index of the table that value belongs to, and assign that value as key dump_table() - see everything inserted in table and the chains
from DoublyLinkedList import DoublyLinkedList class Node: def __init__(self, key = None, value = None): self.key = key self.value = value class DirectTable: def __init__(self): self.list = [None] * 5000000 # take care of chaining def dt_insert(self, value): node = self.hash_to_index(value) position = self.list[node.key] # if the index is None create a linked list for chaining if position is None: position = DoublyLinkedList() # chain position.add_node(node.value, node.key) self.list[node.key] = position def dt_search(self, value): node = self.hash_to_index(value) position = self.list[node.key] if position is not None: # search in the chain result = position.list_search(node.value) print(result.data) return result.data return False def dt_delete(self, value): node = self.hash_to_index(value) position = self.list[node.key] if position is not None: # delete in the chain result = position.list_delete(node.value) return result return False def hash_to_index(self, value): node = Node() if str(value).isdigit(): if value < 5000000: node.value = value node.key = value return node # if its a char else: key = ord(value) if key < 5000000: node.value = value node.key = key return node # dump the table def dump_table(self): for i in self.list: if i is not None: temp = i.dump() for j in temp: print(j)
from DirectTable import DirectTable def main(): my_table = DirectTable() my_list = [1, 'a', 7, 'ab', 8, 20] for i in my_list: my_table.dt_insert(i) my_table.dump_table() print("---------------") my_table.dt_search('a') print("---------------") print(my_table.dt_delete('a')) print("---------------") my_table.dump_table() print("---------------") print(my_table.dt_delete(10)) if __name__ == "__main__": main()
class Node: def __init__(self, value, key): self.data = value self.key = key self.next = None self.prev = None class DoublyLinkedList: def __init__(self): self.head = None # no need for tail as always the next pointer of last object will remain as none def add_node(self, value=None, key=None): node = Node(value, key) # make new node # self.head is either pointing to None or the first object, make the next pointer of the new node point to same node.next = self.head # if head is not null, than there is other items in the list if self.head is not None: # make the prev pointer of the node that head is pointing to point to the new node self.head.prev = node # make the head point to the new node self.head = node # make prev pointer of new node, point to head node.prev = self.head def list_search(self, value): # start from the head p = self.head # do it as long as there is no pointer and value not foun while p is not None: # make p reference to next node if p.data is not None: if p.data == value: return p if p.next is not None: p = p.next else: return False def list_delete(self, value): # find the node in the linked list p = self.list_search(value) # if what back pointer points to is not head if p is not False: if p.prev is not None and p != self.head: # make the next pointer of the node behind, point to the back of the node ahead p.prev.next = p.next else: # if the back node is the head, make it point to the node after self.head = p.next # if there is a node after if p.next is not None: # make the the back pointer of the node ahead point to the front pointer of the node behind p.next.prev = p.prev return True else: return False def dump(self): node = self.head i =  while node: if node.data is not None: i.append(node.data) node = node.next return i def get_top(self): return self.head