I am participating in the world's greatest shave and volunteering to shave my head clean to generate funds for leukemaea foundation. Please support the good cause by going to - http://my.imisfriendraising.com.au/personalPage.aspx?SID=58176
a small donation from you and a clean scalp for me will make a big difference :)
cheers
gaurav
Monday, February 23, 2009
Saturday, February 21, 2009
addendum
while going through my top 5's, gunjan was wondering how come i didn't put up my "hottie" list :D. it's essentially a no-brainer -
demi moore, emmanuelle chirqui, gayatri sharma, yamila diaz, penelope cruz
while I am at it, it might as well put down gunjan's hottie list :D
kaka, john abraham, kunal kapoor, sean connery (expired product), daniel craig
quoting gunjan - "I need a lot of hottie lists, a hottie soccer player list, a hottie cricketer list, a hottie actor list..."
..........................
gunjan's idea, and i quite agree with it, is to actually have a favorite characters from books/movies/ theater etc...
mine would be dr. who, jeeves and wooster (as a pair), denny crane (boston legal), chandeler (friends), will hunting (good will hunting)
gunjan's - dr. who, empress of blandings (the pig from pigs have wings by P G Wodehouse), captain nemo from 20000 leagues under the sea, rat creatures (you can see why gunjan also likes sean connery), sirius black (who weirdly is seriously white in the movie :D)
have a great weekend guys!
G2
demi moore, emmanuelle chirqui, gayatri sharma, yamila diaz, penelope cruz
while I am at it, it might as well put down gunjan's hottie list :D
kaka, john abraham, kunal kapoor, sean connery (expired product), daniel craig
quoting gunjan - "I need a lot of hottie lists, a hottie soccer player list, a hottie cricketer list, a hottie actor list..."
..........................
gunjan's idea, and i quite agree with it, is to actually have a favorite characters from books/movies/ theater etc...
mine would be dr. who, jeeves and wooster (as a pair), denny crane (boston legal), chandeler (friends), will hunting (good will hunting)
gunjan's - dr. who, empress of blandings (the pig from pigs have wings by P G Wodehouse), captain nemo from 20000 leagues under the sea, rat creatures (you can see why gunjan also likes sean connery), sirius black (who weirdly is seriously white in the movie :D)
have a great weekend guys!
G2
Thursday, February 19, 2009
too much time
having finished the preparation of my first two lectures, submitted a research paper and done designing all assignments, I have too much time remaining on my hands, so i came up with my top 5 list, after the conversation with chirayu regarding swades and whether it should be in top 5 hindi movies or not. thinking about my top 5 choices, I think this would be it (of course, subject to memory)
hindi movies: swades, andaz apna apna, sardar, hera pheri, raat
hindi movie albums: dil se, saathiya, thakshak, caravan, teesri manzil (i replaced bombay by saathiya)
hindi songs (individual): rooth ke hamse kaheen, phool gendawa na maro, thayya thayya, afreen afreen, aye mere pyaare watan (kaabuliwaala)
hindi actresses: smita pati, nandita das (don't care two cents about any others)
hindi actors: aamir khan
english and other language movies: when harry met sally, kung fu hustle, kill bill 1, matrix 1, run lola run
english albums: best of gipsy kings, best of me bryan adams, stripped, west life greatest hits, Abba gold
english and other language songs: djobi djoba (gipsy kings), beautiful, remember the time, in the arms of an angel, old town (wow, I come out as a real softy in this one :D)
english actors: eh...
english actresses: meg ryan (i know i know she can't act to save her life but there's just something about her, call it my guilty pleasure :D)
hindi movies: swades, andaz apna apna, sardar, hera pheri, raat
hindi movie albums: dil se, saathiya, thakshak, caravan, teesri manzil (i replaced bombay by saathiya)
hindi songs (individual): rooth ke hamse kaheen, phool gendawa na maro, thayya thayya, afreen afreen, aye mere pyaare watan (kaabuliwaala)
hindi actresses: smita pati, nandita das (don't care two cents about any others)
hindi actors: aamir khan
english and other language movies: when harry met sally, kung fu hustle, kill bill 1, matrix 1, run lola run
english albums: best of gipsy kings, best of me bryan adams, stripped, west life greatest hits, Abba gold
english and other language songs: djobi djoba (gipsy kings), beautiful, remember the time, in the arms of an angel, old town (wow, I come out as a real softy in this one :D)
english actors: eh...
english actresses: meg ryan (i know i know she can't act to save her life but there's just something about her, call it my guilty pleasure :D)
Saturday, February 14, 2009
could someone please tell me what "doubt" was about!?!?!
warning: contains spoiler
just finished watching "doubt". the movie's either
a) just weird
b) above my intellect
i just felt that the movie left too many questions unanswered. it's like trying to find the killer without knowing who was killed.
why does father flynn resign? is it because of
a) scared of getting previous wrongdoings becoming public
b) to save the black kid from further trouble
c) fed up (of streep's nagging)
d) the director had to end it because
i) movie was going over-budget
ii) meryl streep got pregnant and they
can't show that
just finished watching "doubt". the movie's either
a) just weird
b) above my intellect
i just felt that the movie left too many questions unanswered. it's like trying to find the killer without knowing who was killed.
why does father flynn resign? is it because of
a) scared of getting previous wrongdoings becoming public
b) to save the black kid from further trouble
c) fed up (of streep's nagging)
d) the director had to end it because
i) movie was going over-budget
ii) meryl streep got pregnant and they
can't show that
Friday, February 13, 2009
confucious says - friday the 13th
following material might be offensive to some people. don't read if you think you will be one of "those".
a man who can't give complements has trouble with the opposite sex
a man who comes to terms with giving complements will thrive
a man who gives complements and means it, is just gay...
--------
marriage is like a chair, have no clue why
--------
if you don't try, you have zero percent chance of success, if you do, you have 100 percent chance of dying (mahatma gandhi, on wasabi)
--------
behind every successful man, there's a women. behind every failure, there are two
--------
a person who can't find a job, does a phd. a person who doesn't get admission into phd becomes a toll collector. a person who gets rejected for that grows up to be sarah palin
--------
a friend in need is a pest indeed
--------
test cricket is like late-night television static. yuvraj brings the morning news.
--------
modern indian music is like a high-school passout. it doesn't know what to do so just follows the other "cool kids".
---------
saturday night debate - harry potter vs. wife; anybody's wife. HP is so f***ed :-(
a man who can't give complements has trouble with the opposite sex
a man who comes to terms with giving complements will thrive
a man who gives complements and means it, is just gay...
--------
marriage is like a chair, have no clue why
--------
if you don't try, you have zero percent chance of success, if you do, you have 100 percent chance of dying (mahatma gandhi, on wasabi)
--------
behind every successful man, there's a women. behind every failure, there are two
--------
a person who can't find a job, does a phd. a person who doesn't get admission into phd becomes a toll collector. a person who gets rejected for that grows up to be sarah palin
--------
a friend in need is a pest indeed
--------
test cricket is like late-night television static. yuvraj brings the morning news.
--------
modern indian music is like a high-school passout. it doesn't know what to do so just follows the other "cool kids".
---------
saturday night debate - harry potter vs. wife; anybody's wife. HP is so f***ed :-(
Thursday, February 12, 2009
quotes
from early childhood, i was always a fan of quotes from personalities and other people around me. maybe it was because i didn't have the patience to read beyond a couple of lines, or maybe because the inspirational quotes pump you with a kind of adrenaline, or mabye even because you can use them (of course, pretentiously, in conversations). there's a whole branch of wiki dedicated to good qutoes here.
anyhoo, a couple of my favorite quotes are:
you are not what you show, but what you hide
the more you practise, the luckier you get
Courage is not the absence of fear, but rather the judgement that something else is more important than fear.
We are what we repeatedly do; excellence, then, is not an act but a habit.
Everyone is a genius at least once a year. The real geniuses simply have their bright ideas closer together.
People often say that motivation doesn’t last. Well, neither does bathing - that’s why we recommend it daily.
When you want to spend the rest of your life with somebody, you want "that rest of life" to begin as soon as possible (from: when harry met sally)
An inventor is simply a fellow who doesn’t take his education too seriously.
Advice is what we ask for when we already know the answer but wish we didn’t.
When a person can no longer laugh at himself, it is time for others to laugh at him.
We are the people our parents warned us about.
some lighter ones -
If at first you don't succeed; call it version 1.0
The glass is neither half-full nor half-empty: it's twice as big as it needs to be.
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.
There's nothing more dangerous than an angry man with no sense of humor
God made the natural numbers, all the rest is the work of man.
If I feel unhappy, I do mathematics to become happy. If I am happy, I do mathematics to keep happy.
hope you guys liked some of these
cheers
gaurav
anyhoo, a couple of my favorite quotes are:
you are not what you show, but what you hide
the more you practise, the luckier you get
Courage is not the absence of fear, but rather the judgement that something else is more important than fear.
We are what we repeatedly do; excellence, then, is not an act but a habit.
Everyone is a genius at least once a year. The real geniuses simply have their bright ideas closer together.
People often say that motivation doesn’t last. Well, neither does bathing - that’s why we recommend it daily.
When you want to spend the rest of your life with somebody, you want "that rest of life" to begin as soon as possible (from: when harry met sally)
An inventor is simply a fellow who doesn’t take his education too seriously.
Advice is what we ask for when we already know the answer but wish we didn’t.
When a person can no longer laugh at himself, it is time for others to laugh at him.
We are the people our parents warned us about.
some lighter ones -
If at first you don't succeed; call it version 1.0
The glass is neither half-full nor half-empty: it's twice as big as it needs to be.
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.
There's nothing more dangerous than an angry man with no sense of humor
God made the natural numbers, all the rest is the work of man.
If I feel unhappy, I do mathematics to become happy. If I am happy, I do mathematics to keep happy.
hope you guys liked some of these
cheers
gaurav
Thursday, February 5, 2009
masala tea (chai)
quite a few non-indians are fascinated by the indian version of tea containing all kinds of flavors! Well the tea in villages uses tulsi (a version of basil which has two types "raam tulsi" and "shyaam tulsi", the latter being tastier and stronger while the former is bigger in size), fresh-ground cardamom and ginger, and i personally feel that it's the best tea ever. but in cities, the tea is made using a masala tea powder which is a blend of various spices such as cinnamon, aniseed, cardamom, a litttttttttle black pepper and clove, and more.
anyways, i would like to put the village version over here.
for two cups -
1 cup milk
2 cups water (1 cup evaporates)
about 10 leaves of tulsi
a small piece of ginger (best grated, but can also crush it)
sugar (i like 2 teaspoons per cup with this kind of tea)
2 tea bags (i like lipton)/ 3 teaspoons tea powder (if you can get your hands on it - taj mahal)
add the tulsi and ginger to the water and bring it to a boil. add the tea and sugar and boil for about 2 mins, the milk and another 2-3 mins and you have your tea :)
cheers
gaurav
Wednesday, February 4, 2009
OMG
I had the pleasure of calling ATO and waiting for just under 20 minutes when a lovely lady picked up the phone and inquired if I am calling the Australian Tax Office; not informing that "this is the ATO"; but inquiring whether I am looking for ATO or not.
Anyways, I wasn't sure if they had my current bank account details so after going through the usual security check, I ask her, is "111-222-333" the account number you have, and she replies in the green :) I, being a nerd, request her if she could repeat the number for me please, to which she replies "Sorry, we are not authorized to give out the account number over the phone". WOW!!!!
Anyways, I wasn't sure if they had my current bank account details so after going through the usual security check, I ask her, is "111-222-333" the account number you have, and she replies in the green :) I, being a nerd, request her if she could repeat the number for me please, to which she replies "Sorry, we are not authorized to give out the account number over the phone". WOW!!!!
Tuesday, February 3, 2009
tutorial on linked list - part 2
now coming to a bit more useful topics in linked lists. often, we require that our lists be sorted at all times. even the items we insert into the linked lists be places at the correct place. so let's look at the insert function.
struct node
{
int data;
node* next;
};
now the possibilities are:
1. list is currently empty
2. the item (head->data) at first place is bigger than item to be inserted
3. the new item needs to placed "somewhere" in between
4. the new item needs to placed at the end.
now look at the following code:
node *temp;
temp->data=item;
temp->next=head;
head=temp;
if the head is NULL OR head->data is more than item, the above code works. otherwise, we go to the node (current), BEFORE which, the new node should be inserted. we also heep a track of the node before that (last) so that we can insert the new node (temp) between last and current.
node *current=head,*last;
while(current!=NULL && current->data< item)
{
last=current;
current=current->next;
}
node *temp;
temp->data=item;
last->next=temp;
temp->next=current;
---------------------------------
deletion function - similar to the insertion function, cases are:
1. either list is empty (do nothing)
2. item to delete is at head (just shift head to the next node)
3. item to delete is in the middle or at the end. (link the item before the concerned item to the item next to the concerned item\)
if(head->data==item)
head=head->next;
else
{
node *current=head,*last;
while(current!=NULL && current->data!=item)
{
last=current;
current=current->next;
}
if(current!=NULL)
last->next=current->next;
//if we reach the end of list, the item is not found
}
struct node
{
int data;
node* next;
};
now the possibilities are:
1. list is currently empty
2. the item (head->data) at first place is bigger than item to be inserted
3. the new item needs to placed "somewhere" in between
4. the new item needs to placed at the end.
now look at the following code:
node *temp;
temp->data=item;
temp->next=head;
head=temp;
if the head is NULL OR head->data is more than item, the above code works. otherwise, we go to the node (current), BEFORE which, the new node should be inserted. we also heep a track of the node before that (last) so that we can insert the new node (temp) between last and current.
node *current=head,*last;
while(current!=NULL && current->data< item)
{
last=current;
current=current->next;
}
node *temp;
temp->data=item;
last->next=temp;
temp->next=current;
---------------------------------
deletion function - similar to the insertion function, cases are:
1. either list is empty (do nothing)
2. item to delete is at head (just shift head to the next node)
3. item to delete is in the middle or at the end. (link the item before the concerned item to the item next to the concerned item\)
if(head->data==item)
head=head->next;
else
{
node *current=head,*last;
while(current!=NULL && current->data!=item)
{
last=current;
current=current->next;
}
if(current!=NULL)
last->next=current->next;
//if we reach the end of list, the item is not found
}
alu matar (gunjan's fav) recipe
hey,
here's the alu matar recipe (potatoes with green peas).
ingredients:
potatoes - 3, diced
peas - 300-400 grams (really depends on how much you like them)
onion - 2 medium - chopped fine
tomatoes - 2, big, ripe, diced
bay leaves - 3
chilli powder - 1 teaspoon
turmeric power - 1/2 teaspoon
coriander powder - 2 heaped teaspoon
garam masala powder - 1/2 teaspoon
mustard seeds - 1/2 teaspoon
cumin seeds - 1/2 teaspoon
ginger paste 1 heaped teaspoon
garlic paste 1 heaped teaspoon
oil - 50ml
salt to taste
heat oil and when it's hot enough, add the mustard, cumin seeds and bay leaves. after 10 seconds or so (or before the cumin and mustard seeds start burning), add the onion and cook for 5 mins on high heat, stirring occasionally. add the ginger garlic paste and cook for 3 more minutes stirring occasionally.
put the four powders in a bowl, add 100 ml of water and mix thoroughly, add this to the onions cooking at high heat. keep stirring so that it doesn't stick to the base (if it sticks, add some water slowly). after about 30 seconds, add the diced potato, stir and cook for 2 mins. add the diced tomatoes and cook for another minute. add a litre of water and turn up the heat. when the boil comes, add salt, reduce heat to 4 o'clock position and cook for 20 minutes. add peas, cook for 3 more minutes. garnish with coriander leaves and ta-da!
here's the alu matar recipe (potatoes with green peas).
ingredients:
potatoes - 3, diced
peas - 300-400 grams (really depends on how much you like them)
onion - 2 medium - chopped fine
tomatoes - 2, big, ripe, diced
bay leaves - 3
chilli powder - 1 teaspoon
turmeric power - 1/2 teaspoon
coriander powder - 2 heaped teaspoon
garam masala powder - 1/2 teaspoon
mustard seeds - 1/2 teaspoon
cumin seeds - 1/2 teaspoon
ginger paste 1 heaped teaspoon
garlic paste 1 heaped teaspoon
oil - 50ml
salt to taste
heat oil and when it's hot enough, add the mustard, cumin seeds and bay leaves. after 10 seconds or so (or before the cumin and mustard seeds start burning), add the onion and cook for 5 mins on high heat, stirring occasionally. add the ginger garlic paste and cook for 3 more minutes stirring occasionally.
put the four powders in a bowl, add 100 ml of water and mix thoroughly, add this to the onions cooking at high heat. keep stirring so that it doesn't stick to the base (if it sticks, add some water slowly). after about 30 seconds, add the diced potato, stir and cook for 2 mins. add the diced tomatoes and cook for another minute. add a litre of water and turn up the heat. when the boil comes, add salt, reduce heat to 4 o'clock position and cook for 20 minutes. add peas, cook for 3 more minutes. garnish with coriander leaves and ta-da!
tutorial 1 for pointers
hey C++ nerds and geeks!
we will be tackling pointers, the most evil of the eviloparisuis brothers, the curse of the black dragon, the swallower of black holes.
int x=5;
what does the above innocent, sweet and simple statement mean?!?
that x is an integer, which tells the computer to reserve 4 bytes and the starting address of those 4 bytes (i.e. the first byte is referred by &x). when we output x, we are actually outputting value at address &x. we will come back to this later. but, right now, let's get started with pointers.
int *p
you read this statement as "integer pointer p" or simply "p points to an integer"
this statement means that "p contains starting address of some integer"
we can output value of "that" integer that p points to with "*p" (read as pointer p)
now why is it important for a pointer to be associated with a data type such as integer?
because when we output *p, 4 bytes from starting address (p) are fetched, encoded as an integer and displayed. hence we cannot copy an integer pointer to a double pointer and so on.
pass 1:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
p=&x; //means that p contains address of x, which means p=0x112233
cout<<*p< 5
*p=20; //modify value at address 0x112233 to 20
cout<< x<outputs 20
------------------------------------
pass 2:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
*p=x; //modify value at "that" address to 5
cout<<*p<< endl; address =""> 5
*p=20; //modify value at "that" address to 20
cout<< x<< endl; //still outputs 5
------------------------------------
the above two versions had just one statement different
p=&x versus *p=x
p=&x means that p stores address of x, and therefore x changes if *p is modified and *p changes if x is modified. This is called "tight coupling"
*p=x refers to a one time copy. value at address stored in p takes the value of x but p DOES NOT point to x actually. Thus *p DOES NOT change if x changes and vice versa. This is called "loose coupling"
-----------------------------------
int x=10,y=20;
int *p,*q;
p=&x;
q=&y;
q=p;
x++;
cout<< *q<< " ";
*p=y;
cout<< *q<< endl;
what's the output of the above code?
a) 10 20
b) 11 11
c) 20 20
d) 11 20
e) 10 11
you got it right if you answered 'd'. you see, q=p means q now contains whatever address p contains, which is the address of x. hence both p.q point to x. when x increases to 11 (using x++)
*p and *q output 11. then *p=y means *p which is value at address inside p (which is the address of x) becomes y. Thus x becomes y (20). Thus *q (q still points to x) outputs 20.
we will be tackling pointers, the most evil of the eviloparisuis brothers, the curse of the black dragon, the swallower of black holes.
int x=5;
what does the above innocent, sweet and simple statement mean?!?
that x is an integer, which tells the computer to reserve 4 bytes and the starting address of those 4 bytes (i.e. the first byte is referred by &x). when we output x, we are actually outputting value at address &x. we will come back to this later. but, right now, let's get started with pointers.
int *p
you read this statement as "integer pointer p" or simply "p points to an integer"
this statement means that "p contains starting address of some integer"
we can output value of "that" integer that p points to with "*p" (read as pointer p)
now why is it important for a pointer to be associated with a data type such as integer?
because when we output *p, 4 bytes from starting address (p) are fetched, encoded as an integer and displayed. hence we cannot copy an integer pointer to a double pointer and so on.
pass 1:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
p=&x; //means that p contains address of x, which means p=0x112233
cout<<*p<
*p=20; //modify value at address 0x112233 to 20
cout<< x<
------------------------------------
pass 2:
int x=5; //assume address of x to be 0x112233
int *p; //p points to "some" address
*p=x; //modify value at "that" address to 5
cout<<*p<< endl; address =""> 5
*p=20; //modify value at "that" address to 20
cout<< x<< endl; //still outputs 5
------------------------------------
the above two versions had just one statement different
p=&x versus *p=x
p=&x means that p stores address of x, and therefore x changes if *p is modified and *p changes if x is modified. This is called "tight coupling"
*p=x refers to a one time copy. value at address stored in p takes the value of x but p DOES NOT point to x actually. Thus *p DOES NOT change if x changes and vice versa. This is called "loose coupling"
-----------------------------------
int x=10,y=20;
int *p,*q;
p=&x;
q=&y;
q=p;
x++;
cout<< *q<< " ";
*p=y;
cout<< *q<< endl;
what's the output of the above code?
a) 10 20
b) 11 11
c) 20 20
d) 11 20
e) 10 11
you got it right if you answered 'd'. you see, q=p means q now contains whatever address p contains, which is the address of x. hence both p.q point to x. when x increases to 11 (using x++)
*p and *q output 11. then *p=y means *p which is value at address inside p (which is the address of x) becomes y. Thus x becomes y (20). Thus *q (q still points to x) outputs 20.
tutorial on linked list
a lot of students studying advanced C++ have some trouble understanding the concept of linked list. this is either due to lack of imagination, or lack of understanding of fundamental operations. but essentially, the problem arises due to students studying basic C++ tend to memorize topics rather than trying to build a deep understanding of the same.
you wouldn't think of memorizing addition, would you? addition is a primitive operation that everyone understands to the bone. a+b refers to the outcome of someone giving you 'b' dollars when you already have 'a' dollars in your purse, or vice versa (i think that concepts are much clearer when money is involved :D). the "vice versa" becomes really important since a+b=b+a which is the commutative property. similarily, it doesn't matter in which order you get the money (a+b)+c = a+(b+c). this is the associative property.
Sorry, the above image is a bit too small, but if you click on it, it will open in a new window/tab and is viewable.
I can also move the "head" around so that the first item changes. This happens when the first person in the queue (head) is served and now is no longer a part of the queue. Look at the following statement:
head=head->next;
the right hand side of this statement (head->next) contains address of temp (87)
so it simplifies to head=87
thus head now contains address 87 rather than the old address 84.
thus head now points to the second node.
thus the second node now becomes the first node :)
what happens to the old first node?!?!?! it is still in the memory. so it you want to remove it from memory, you use:
node* old=head //old points to same location as head (84)
head=head->next;
delete old //delete node contained at address inside old (84)
------------------------------------
Now let us look at some more useful operations on lists.
Operation 1: To check if list is empty or not?
The list is empty if head contains no address. That is, head is NULL. Which also tells us that when we create a list, we should assign NULL to head. Hence, the correct way to initialize a list is:
node* head=NULL;
bool isEmpty(node* head)
{
if(head==NULL)
return true;
else
return false;
}
---------------------------------------
Assuming that the list is containing a set of items where order isn't important. We pass the node pointer by reference (that is the actual head is modified rather than a duplicate copy of head being passed to the function).
We first create a node by reserving memory space.
We contain address of old head in node temp.
We move head so that head now contains address of temp.
void insert(node* &head, int item)
{
node* temp=new node;
temp->data=item;
temp->next=head;
head=temp;
}
Even if head was NULL (inserting item into an empty list), the statement temp->next=head means that temp->next contains NULL which is also correct :)
-----------------------------------
Operation 3: Deleting item from front of list:
void delete(node* &head)
{
if(head!=NULL)
{
node* temp=head;
head=head->next;
delete temp;
}
//if head is already NULL, it means nothing remaining to delete
}
-------------------------------
Operation 4: Traverse through the list (go through the list for some xyz purpose)
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
while(head)
{
cout<data<<" ";
head=head->next; //please remember the actual head is not modified since a duplicate
//pointer in memory is there, that contains same address as head
}
}
For those of you, who still are freaked out by me modifying "head" in the function, use the following function varient:
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
node* current=head;
while(current)
{
cout<data<<" ";
current=current->next;
}
}
------------------
Tutorial part 2 coming soon to a cinema near you!
cheers
gaurav
you wouldn't think of memorizing addition, would you? addition is a primitive operation that everyone understands to the bone. a+b refers to the outcome of someone giving you 'b' dollars when you already have 'a' dollars in your purse, or vice versa (i think that concepts are much clearer when money is involved :D). the "vice versa" becomes really important since a+b=b+a which is the commutative property. similarily, it doesn't matter in which order you get the money (a+b)+c = a+(b+c). this is the associative property.
anyways, so much so for kindergarten math. coming to linked lists now. before understanding linked lists, it is necessary to understand pointers. so please refer to my post on pointers if you think that pointers are nasty things planted on earth by the evil cybermen from outer universe. (i'm watching too much dr. who nowadays!)
(once you are happy with pointers, proceed)
a linked list is a linked collection of items of the same type such that first value knows where is the second value stored, the second value knows about the third value and so on. for example, a list of students can be encoded as a linked list (LL). If I want to display the list of students, I need to start from somewhere. Thus, the location of the first student, (to whom no one points - so sad) is important and should be stored somewhere. If the location of the first student is lost, then that of the second student is also lost (since the first student has that info) and so on.
A simple list looks like the following figure. It simply contains a set of integers, not stored in sorted order.
You can view this as ID of students standing in a queue. The person at the front of the queue has ID 8, the next one 3 and so on. It is useful to divide each item (from now on referred to as "node") as containing two parts: 1. data
2. link to next node
Thus we come to our first C++ definition, that of a node. A node is an abstract data type containing value and address of next node. From the discussion on pointers, what contains address of a node -- pointer to a node :) So,struct node
{
int data; //this can be int, double, even another structure object
node* next;
};
please be clear that the node DOES NOT contain another node, it simply contains address of another node.node* next;
};
Since it's important to have address of the first node somewhere, we call it "head", or "first", or "top" or "front" depending on the situation. I call it head over here. This is implemented as:
node* head;
head = new node;//allocate memory for a node and store it's location in head
head->data=8 //data part of node to which head points becomes 8
head->next=NULL //right now, head does not contain any address, thus it's the only node
If you want to add another node
node* temp=new node;
temp->data=3;
temp->next=NULL;
head->next=temp;
Sorry, the above image is a bit too small, but if you click on it, it will open in a new window/tab and is viewable.
I can also move the "head" around so that the first item changes. This happens when the first person in the queue (head) is served and now is no longer a part of the queue. Look at the following statement:
head=head->next;
the right hand side of this statement (head->next) contains address of temp (87)
so it simplifies to head=87
thus head now contains address 87 rather than the old address 84.
thus head now points to the second node.
thus the second node now becomes the first node :)
what happens to the old first node?!?!?! it is still in the memory. so it you want to remove it from memory, you use:
node* old=head //old points to same location as head (84)
head=head->next;
delete old //delete node contained at address inside old (84)
------------------------------------
Now let us look at some more useful operations on lists.
Operation 1: To check if list is empty or not?
The list is empty if head contains no address. That is, head is NULL. Which also tells us that when we create a list, we should assign NULL to head. Hence, the correct way to initialize a list is:
node* head=NULL;
bool isEmpty(node* head)
{
if(head==NULL)
return true;
else
return false;
}
---------------------------------------
Operation 2: To insert an item at the front of the list
Assuming that the list is containing a set of items where order isn't important. We pass the node pointer by reference (that is the actual head is modified rather than a duplicate copy of head being passed to the function).
We first create a node by reserving memory space.
We contain address of old head in node temp.
We move head so that head now contains address of temp.
void insert(node* &head, int item)
{
node* temp=new node;
temp->data=item;
temp->next=head;
head=temp;
}
Even if head was NULL (inserting item into an empty list), the statement temp->next=head means that temp->next contains NULL which is also correct :)
-----------------------------------
Operation 3: Deleting item from front of list:
void delete(node* &head)
{
if(head!=NULL)
{
node* temp=head;
head=head->next;
delete temp;
}
//if head is already NULL, it means nothing remaining to delete
}
-------------------------------
Operation 4: Traverse through the list (go through the list for some xyz purpose)
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
while(head)
{
cout<
head=head->next; //please remember the actual head is not modified since a duplicate
//pointer in memory is there, that contains same address as head
}
}
For those of you, who still are freaked out by me modifying "head" in the function, use the following function varient:
void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
node* current=head;
while(current)
{
cout<
current=current->next;
}
}
------------------
Tutorial part 2 coming soon to a cinema near you!
cheers
gaurav
Subscribe to:
Posts (Atom)