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.

About these ads

One comment

  1. [...] Data Structure Questions/Concepts – Part 1 (singztechmusings.wordpress.com) Advertisement Eco World Content From Across The Internet. Featured on EcoPressed A cheat sheet of peer-to-peer car sharing players Share this:TwitterFacebookLike this:LikeBe the first to like this post. [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 27 other followers

%d bloggers like this: