1
\$\begingroup\$

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 :-))

Methods:

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[0])
            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)

main:

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()

Linked list:

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.