Hashing and using a doubly-linked list to solve collisions

247 views Asked by At

I'm trying to figure how to append a list value that indexes at the same location in the hash list to the beginning of that hash index. I have the double linked list code and the hashing code that uses the single list chaining method I'm just having a hard time understanding how to do it with a double linked list.

Here is my code:

# Collisions are resolved by chaining, except that instead of storing the
# collisions in a list, store them in a doubly-linked list. Use the doubly-linked
# list code below, but modify it to insert new elements at the beginning of the
# list instead of the end. You cannot use other modules.

import math


class Node(object):
    def __init__(self,data=None,next_node=None,prev_node=None):
        self.data=data
        self.next_node=next_node
        self.prev_node=prev_node


class DoubleLinkedList():
    def __init__(self,head=None):
        self.head=head

    def traverse(self):
        curr_node=self.head
        while curr_node != None:
            print(curr_node.data)
            curr_node=curr_node.next_node

    def get_size_list(self):
        #create a counter
        count=0
        curr_node = self.head

        while curr_node != None:
            #add to old count
           count=count+1
           curr_node = curr_node.next_node

        return count

    def prepend(self,data):
        #define new node
        new_node=Node(data)
        #set the next node equal to old head
        new_node.next_node=self.head
        #because its the head the prev point will point to nothing
        new_node.prev_node=None
        #handle the non-empty list case
        if self.head!=None:
            self.head.prev_node=new_node
        #update the head
        self.head=new_node

list_=[43,22,1,0,15,31,99,218,4,7,11,8,9]

hash_val= [[] for _ in range(13)]

Dlist=DoubleLinkedList()

def display_hash(hashTable):
    for i in range(len(hashTable)):
        print(i,end=" ")
        for j in hashTable[i]:
            print("-->",end=" ")
            print(j,end=" ")
        print()

def hash_func(list_):
    list_2=[None for i in range(13)]

    for i in list_:
        #print(math.floor((pow((key+6),3)/17+key)%13)
        hash_key=math.floor((pow((i+6),3)/17+i)%13)
        hash_val[hash_key].append(i)
        list_2[math.floor((pow((i+6),3)/17+i)%13)]=i

    print(list_2)
    print(list_)
    print(hash_val)
    print (math.floor((pow((43+6),3)/17+43)%13))
    print(math.floor((pow((218 + 6), 3) / 17 + 218) % 13))

print(hash_func(list_))
0

There are 0 answers