Amazon Interview Question
7. google for depth-first tree
8. I think that using up more memory is one of the disadvantage too. For searching, I think that array and linked list are about the same. Of course, linked list needs to access the node member to get the value, which uses up extra time. But it won't be too much difference I assume.
Linked List:
? They allow a new element to be inserted or deleted at any position in a constant number of operations (changing some references) O(1).
? Easy to delete a node (as it only has to rearrange the links to the different nodes).
? To find the nth node, will need to recurse through the list till it finds [linked lists allow only sequential access to elements. ]
Array
? Insertion or deletion of element at any position require a linear (O(n)) number of operations.
? Poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one.
? Poor at inserting as an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller
? easy to find the nth element in the array by directly referencing them by their position in the array.[ arrays allow random access ]
7.
//data-leftchild-rightchild order
struct binarytreenode
{
struct binarytreenode *lchild;
int data;
struct binarytreenode *rchild;
}
preorder (binarytreenode *node)
{
printf("%d",node->data);
preorder(node->lchild);
preorder(node->rchild);
}
8. In addition to above advantages of linked list, one more advantage I can think of is that linked lists dont have to be stored in contigous memory location whereas arrays require it. If an array contains a large number of elements, that becomes a definite disadvantage in instances where storage is limited. Linked lists take up whatever memory area is available in such cases, hence they are more effecient in certain cases.
please give me the answer
- aditya June 30, 2005