Data Structure Questions/Concepts – Part 1
1. Searching data in a Linked List
The only way to search a linked list is with a linear search, because the only way a linked list’s members can be accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data structure so that searches can be more efficient
2. Linear and Non-linear Data Structures
A linear data structure is one in which, while traversing sequentially, we can reach only one element directly from another. Eg, Array, List, Stack, Queue etc.
(Note: 2D array, though seems to be non-linear, is actually linear data structure. This is bcoz memory is single dimensional and when it is stored in the memory it is stored as a single dimension array in either row-major or column-major format. Similarly all multi-dimensional arrays are also linear, for the same reason)
Non linear data structures do not maintain a linear structure. It branches to more than one node and cannot be traversed in a single run. Eg. Tree, Graph etc.
3. Hash Function and the Concept of Hashing
A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array). The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.
Hashing is a way of retrieving records from memory in faster way. Record are inserted into memory by using any hash function (division, midsqure, folding, digit analysis etc) and retrieved using the same hash function.
4. Data Structure Used In Recursion
It’s Stack. Stack has the LIFO (Last In First Out) property; it remembers its’ ‘caller’. Therefore, it knows to whom it should return when the function has to return. On the other hand, recursion makes use of the system stack for storing the return addresses of the function calls. Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written explicit, stack is to be used.