Assume Hashtable is a simple array of size 8 with indices 07

Assume Hashtable is a simple array of size 8, with indices 0..7. Numeric keys are mapped by a Hashfunction that gives the mod(8,n) value for any key “n” yielding the Hashtable index for that key (0..7). A Hashtable entry is null unless a key exists with that index as its hashed index; if so, the Hashtable entry points to the first node of a linked list of keys with that hash index. The last node on this linked list has a null reference for the next referenced node. Assume the occurrence of a linked list node is represented by the object “Node” and its “Data” and “NextRef” attributes.

Create pseudocode for the \"Insert\" operation.

Solution

Removal of a Node from a Singly Linked List

To complete deletion of firstNode in the list we have to change Head pointing to NextRef of firstNode.

Pseudocode:
firstNode = Head

Head = firstNode->NextRef

free firstNode
Complexity:
Time Complexity: O(1)
Space Complexity: O(1)

Sourcecode:
int delNodeData(int num)
{
struct Node *prev_ptr, *node;

node=Head;

while(cur_ptr != NULL)
{
if(cur_ptr->Data == num)
{
if(cur_ptr==Head)
{
Head=cur_ptr->NextRef;
free(node);
return 0;
}
else
{
prev_ptr->NextRef=node->NextRef;
free(node);
return 0;
}
}
else
{
prev_ptr=node;
node=node->NextRef;
}
}

printf(\"\ Element %d is not found in the List\", num);
return 1;
}
Deleting Last Node in the Singly Linked List

Traverse to Last Node in the List using two pointers namely prevNode and node. Once node reaches the last Node in the list point NextRef in prevNode to NULL and free the node.

Pseudocode:
node = head

forever:

if node->NextRef == NULL
break

prevNode = node
node = node->NextRef

prevNode->NextRef = NULL

free Node
Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

Deleting Node from position \'p\' in the List

To delete a Node at the position \'p\' we have to first traverse the list until we reach the position \'p\'.
For this case have to maintain two pointers namely prevNode and Node.
Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position \'p\' we have to modify prevNode NextRef pointing to Node NextRef and free Node.

Pseudocode:
curNode = head
curPos = 1

forever:

if curPos == P || Node == NULL
break

prevNode = node
node = node->NextRef
curPos++

if noode != NULL:

prevNode->NextRef = node->NextRef
free curNode
Complexity:
Time Complexity: O(n) worst case
Space Complexity: O(3)

Sourcecode:
int delNodeLoc(int loc)
{
struct Node *prev_ptr, *node;
int i;

node=Head;

if(loc > (length()) || loc <= 0)
{
printf(\"\ Deletion of Node at given location is not possible\ \");
}
else
{
// If the location is starting of the list
if (loc == 1)
{
Head=node->NextRef;
free(node);
return 0;
}
else
{
for(i=1;i<loc;i++)
{
prev_ptr=node;
node=cur_ptr->NextRef;
}

prev_ptr->NextRef=node->NextRef;
free(node);
}
}
return 1;
}