111CMSC 212 – F05 (lect 10)AnnouncementsExam #1 – Thursday, March 8, 6:00 – 7:30pm in ARM 0126 Reading– Chapter 12, 10.22CMSC 212 – F05 (lect 10)Linked Data StructuresLike classes with refs to same class in JavaHave pointers to a struct of the same typeExample Declaration:typedef struct NODE {struct NODE *next;int value;} Node;Node * root;next and root are pointers to Nodesroot5 10 15NULL223CMSC 212 – F05 (lect 10)Finding a value in a Linked StructureNode *find(Node *current, int val) {while (current && current->value != val) {current = current->next;}return current;}int IsIn(Node *current, int val) {while ((current != NULL) && ((current->value) != val)) {current = current->next;}if (current) {return 1;} else {return 0;}}4CMSC 212 – F05 (lect 10)Tracing Through Inserthead5 10 15X7Insert 7X2Insert 2NULL335CMSC 212 – F05 (lect 10)Inserting Into a Linked Listint insert(Node **head, int new_value) {Node *current = *head;Node *pred = NULL;Node *newItem; while (current && current->value < new_value) {pred = current;current = current->next;}newItem = (Node *) malloc(sizeof(Node));if (!newItem) return -1;newItem->value = new_value;newItem->next = current;if (!pred) {*head = newItem;} else {pred->next = newItem;}return 0;}6CMSC 212 – F05 (lect 10)Tracing Through Deletehead5 10 15Delete 72Delete 2NULL7447CMSC 212 – F05 (lect 10)Deleting From A Single Linked Listint delete(Node **head, int new_value) {Node *pred = NULL;Node *current = *head;while (current && (current->value != new_value)) {pred = current;current = current->next;}if (!current) {return -1; /* not found */}if (pred) {pred->next = current->next;} else {*head = current->next; /* deleted first item */}free (current);return 0;} 8CMSC 212 – F05 (lect 10)Doubled Linked ListsEach nodes– contains a value– a pointer the next and previous elementTypical Declaration:typedef struct NODE {struct NODE *next;struct NODE *prev;int value;} Node;root5 10 15NULLNULL559CMSC 212 – F05 (lect 10)Insert into a doubly Linked listThink about 4 cases:– Middle of the list• Update previous element's next pointer– new node’s previous pointer set to this node• Update next element’s previous pointer– new node’s next point set to that node– End of the list• Update previous element's next pointer– new node’s previous pointer set to this node– new node’s next pointer set to NULL– Start of the list• Update head of list• Update old head of list's previous element– new node’s next pointer set to this node– new node’s previous pointer set to NULL– An initially empty list• Update head of the list– new node’s next and previous pointer both NULL10CMSC 212 – F05 (lect 10)Inserting Into A Doubly Linked Listint insert(Node **head, int new_value) {Node *pred = NULL, *newItem;Node *current = *head;while (current && current->value < new_value) {pred = current;current = current->next;}newItem = (Node *) malloc(sizeof(Node));if (!newItem) return -1;newItem->value = new_value;newItem->next = current;newItem->prev = pred;if (!pred) {*head = newItem;} else {pred->next = newItem;}if (current) {current->prev = newItem;}}6611CMSC 212 – F05 (lect 10)Deleting from a Doubly Linked Listint delete(Node **head, int new_value) {Node *pred = NULL;Node *current = *head;while (current && (current->value != new_value)) {pred = current;current = current->next;}if (!current) return -1; /* not found */if (pred) {pred->next = current->next;} else {*head = current->next; /* deleted first item */}if (current->next) {current->next->prev = pred;}free (current);return 0;} 12CMSC 212 – F05 (lect 10)Binary TreesEach node– contains a value– a pointer a left child and a right childTypical Declaration:typedef struct NODE {struct NODE *left;struct NODE *right;int value;} Node;1007510 835097713CMSC 212 – F05 (lect 10)Lookup In A Binary Search TreeIf the element is less than the current node– Look in the left child treeIf the element is greater than current node– Look in the right child treeExample:int Lookup(Node *root, int value) {if (!root) return -1;if (root->value == value) {return 1;} else if (root->value > value) {return Lookup(root->left, value);} else { return Lookup(root->right, value);}}14CMSC 212 – F05 (lect 10)Insert Into a Binary SearchTreeint insert(Node **root, int value) {Node *new;if (!(*root)) {new = (Node *) malloc(sizefof(Node));if (!new) return -1;*root = new;new->left = new->right = NULL;new->value = value;return 0;} if ((*root)->value > value) {return insert(&((*root)->left), value);} else {return insert(&((*root)->right), value);}}8815CMSC 212 – F05 (lect 10)Graphs - DirectedIn a Graph– there can be an arbitrary number of nodes– each node can have an arbitrary number of out arcsDeclarations typedef struct ARC {struct NODE *nodePtr;struct ARC *next;} Arc;typedef struct NODE {Arc *outArcs;int value;} Node;16CMSC 212 – F05 (lect 10)GraphsNullNullNullNodeArc5714key9917CMSC 212 – F05 (lect 10)Adding Node To a GraphNode *AddNode(int value) {Node *new;new = (Node *) malloc(sizeof(Node));new->value = value;new->outArcs = NULL;return new;}You need to store this node into some type of structure so you don’t lose itlinked list of nodesarray of nodestree of nodesetc.18CMSC 212 – F05 (lect 10)Adding Arcs To a Graphint AddArc(Node *from, Node *to) {Arc *new, *pred, *current;pred = NULL;for (current=from->outArcs; current; current=current->next) {if (current->nodePtr == to) return 1; /* already defined this arc */pred = current;}new = (Arc *) malloc(sizeof(Arc));if (!new) return -1;new->nodePtr = to;new->next = NULL;if (!pred) {from->outArcs = new; /* first out arc for this node */} else {pred->next =