Advanced Data Structures and Algorithms Overview

Linked Lists & Hash Tables ENEE150 0102 ANDREW GOFFIN

Project 3 Questions? Remember to do the correct type of insertion for each linked list Head insertion for user list Tail insertion for playlist list Goffin ENEE150

Head/tail linked list insertion // head insertion // pass head by reference node->next = *head; *head = node; return; // tail insertion // pass head by reference pnode cur = NULL; if (*head == NULL){ *head = node; return; } for(cur=*head;cur->next!=NULL;cur=cur->next); cur->next=node; return; Goffin ENEE150

Linked List Deletion // given userID to delete pnode cur = NULL; pnode return_val = NULL; if (*head->userID == givenID){ return_val = *head; *head = (*head)->next; return return_val; // returns reference to deleted node } for (cur = *head; cur->next!=NULL; cur=cur->next){ if (cur->next->userID == givenID){ return_val = cur->next; cur->next = cur->next->next; break; } } return return_val; Goffin ENEE150

Hash Tables Basically just an array of linked lists Splits linked list up into more manageable chunks called buckets MUCH easier to search! Hash functions determine which buckets a particular node goes into Key associated with each node is what hash function looks at to sort node Goffin ENEE150

Hash Table Picture Goffin ENEE150

Hash Table Search Complexity Ideally, hash splits keys evenly among buckets This way search complexity does not depend on which bucket you look into When two keys are mapped to the same bucket, a collision occurs Collisions are often inevitable but should be minimized Goffin ENEE150

Midterm #2 Review Strings Pointer Arrays Structures Dynamic Memory Allocation Linked Lists Hash Tables / Trees ** Recursion ** ** - less emphasis on these, since no project on them before exam Goffin ENEE150