data structure and algorithms

chapter - arrays and recursion

4. (a) State what the following pseudocode does. Then, modify the code to perform insertion at the head on a singly-linked list. Note that each node consists of node.data and node.next, where "." denotes a pointer item and ".next" a pointer to the next node; and "NULL" denotes a null pointer. Assume there is a non-empty (i.e., with at least a node) singly-linked list. head - 1st_node; /* head pointer to point at 1st node in the list */ create new_node; /* allocate a new node */ new_node.data = "aaa"; new_node.next = NULL; head - new_node; /* update head pointer to point to new node */ new_node = head; /* have new node to point to head */ (b) Write a pseudocode to perform insertion into the i'th position on a doubly-linked list. Assume a temporary pointer is ponting at the (i-1)'th node on the list. (You may assume pointers such as tmp, cur, head, tail and pointers within a node such as tmp-prev and tmp-inext as necessary. Also, use NULL to indicate a null pointer.) (c) What's the asymptotic upper bound of insertion/deletion in doubly-linked list without a pointer to the previous access point in the list