Stacks

“Stack those papers “. What image comes to ur mind when you read this? Of a neatly arranged set of papers, one on top of each other, right ? 

So, what do we do with a stack of papers?Assuming we are neatness freaks,we would not pick off papers from middle. We would pick them from the top and also add new sheets on the top. 

So, when computer geeks wanted a mechanism to do this, they named that concept as , luckily, Stack.

That is all there is to stacks. Neat arrangement of nodes one after another in which you have access to the top most node only. You add (PUSH), get the top most node (POP) from the top.

I could try and give more examples, but thats all there is . 

Simplest way to implement stacks: Singly Linked Lists with a head pointer.

When we deal with stacks, the following considerations need to be considered:

1) When PUSHing , you can optionally check whether you have exceeded the maximum stack size that you want. To do this you will need an extra variable which stores the value of the current number of elements (called STACK DEPTH)

2) When POPping, check if you are not trying to POP the last element . This is a special case and needs to be considered separately.

From this point on, I will write the simple explanation and code snippets in diff posts. Both posts will contain the url of each other for easy access.

Singly Linked Lists

Have u ever played those childish games in which few kids used to hold hands and run around in  a line, maybe in shape of a train. Ever thought why that train was able to move.Wasnt ie because of the order of holding hands. What would have happened of the fourth kid said “Wait, I will not hold of the third and fifth guy but third and sixth”. Would that train survive? And what used to happen when a kid in between had to leave. Your answer would be “Duh, thats simple.Join the link. The guy before and the gal after him should join hands”. And what if a new guy came:”Come on, Dont mock my intelligence. Either fit him in between or at one of the ends”. So, whats the most important point abt this human chain.I am pretty sure all of you would say :”If at all points, it is ensured that if you start at one end of  the chain and reach the other hand by just following the hands, everything is fine”

Before you start screaming on me, understand this “You have just told the condition of existence and operation of a linked list” This is all there to linked lists(more specifically Singly Linked Lists). Just ensure that at any point of time , the link is traversable from one end to another and u can use the list. Now, you would have understood why it is called linked list too. Coz  each kid (called a node) is linked to the next kid. And what do you need to modify the lists, change the links.

In Coding paradigm, each kid is called a node. Going thru the list is called Traversal. Adding a kid to the list is called, well, Adding. Removing the kid is called Deletion. There are few new terms though: Head Pointer, Tail Pointer.

If  u imagine the chain as a dragon, the the begining of the chain (Dragon’s head), thats the Head Pointer. The end the Tail Pointer. The Head Pointer is a very imp pointer , because  it lets you access the linked list. The Tail Pointer is the end pointer, so that you know that there are no more nodes to traverse.

In some cases, head node and tail nodes contain valid data, In some cases, they dont . Generally, tail node is set as NULL.

(Q: whats the benefit/disadvantage of storing data in the head and tail nodes?  Hint: For any node,how will you know that it is tail Node. Think maan )

To put the operations in more geeky language,  here is the pseudo-code for basic operations

In the foll pseudo codes, Head Pointer means the first node containing valid data.

Traversal

Start from Head Pointer

Get_next:

Get the Pointer of next node

Is the value of next node pointer equal to the Tail Pointer

If yes, Then Stop Traversing(Goto Exit)

Else, Continue Traversing (Goto Get_next)

Exit: Done

Search for a entry

Start from Head Pointer

Get_next:

Get the data of the node

Is the data of the node is the search value

If yes: return the pointer of current node

Else continue,

Get the Pointer of next node

Is the value of next node pointer equal to the Tail Pointer

If yes, Then Stop Traversing(Goto Exit)

Else, Continue Traversing (Goto Get_next)

Exit: Done

Lets take the complex case now, addition after a particular entry .(Lets assume it is in middle)(A node containing data NEW to be added after a node containing OLD)

Addition :

Search and get the pointer of the node containing OLD (Lets call it OLD_NODE)

In a temp node pointer, save  the next node pointer of the node containing OLD (OLD_NEXT)

set the next pointer of OLD_NODE to the new node’s pointer

Make the next pointer of the new node to OLD_NEXT

Now, think what we have done.We have ensured that the link’s order is maintained.

Q: What change will be needed to above for handling adding at the beginning and adding at the end?

Hint: Those two are special pointers. The head and Tail pointer I mean. So, their integrity should be preserved.

Big HW: Write deletion pseudo code. Would have written but this keyboard is killing me.

Before signing off, where are linked lists used: Ans: practically for everywhere, be it Stacks, Queues, Trees, all use some form of the Linked List .

Inside the Post Office

So our routers just behave like post offices , just sending packets from one post office to another , till it reaches the destination.
To do this forwarding, the routers take the help of the routing table. Based on the entry in routing table, the router decides where to send the packet.In the end , router is just a machine. And any machine cant have information by itself? So , who or what makes the routing table in the machine called the router?
The answer to this two fold:
1. A person mananging the router, normally referred to as the administrator
2. Automatic applications, called Routing Protocols
Route entries made using approach 1 are called static routes. Route entries made using approach 2 are called dynamic routes.
Static routes are well static. Once they are made, they will not be removed unless the administrator removes them . Dynamic routes are learned automatically by the interaction of routing protocols. They are added dynamically at run time and they may be removed dynamicaly too. Dynamic routes are required because, in general, the entire network topology is not known before-hand.
We have said that dynamic routes are added by Routing Protocol. Routing Protocol is an application which runs on the routers and whose responsibility is to exchange network topology information(in other words, routes ) with corresponding routign protocols running on other routes. In other words, it is just an intelligent piece of software which has the capability of discovering the network topology information, sending it to other routers as well as the capability to process such information recived from other routers.
To take the analogy with the post office setup further, static routes are well known routes, which dont change. Dynamic routes are routes which depend on the road/traffic condition Routing protocols are like dedicated professionals in the post office whose responsibility is to find out about the neighboring roads/routes and send to the corresponding professional in another post office. These professional’s job is to ensure that any change in road conditions in their vicinity is conveyed to other post offices asap, so that no letters are lost.

With this, we close a very very high-level overview of how packets are sent from source to destination. At the end of this, you should be able the foll questions:
1. What is the role of IP Address ?
2. What is a packet ?
3. What is a routing table ?
4. What does a routing protocol do ?

The next series will be a bit more tech, carrying on from where this series has left. The aim will be to introduce the elements of any typical network topology. At the end of the next series, you will be able to answer questions like:
1. What is a subnet?
2. What is MAC address?
3. What packet enters a router and what leaves, whats the diff in the two packets?
4. When does a packet not reach a destination ?
and some more

The Post Offices of the Networks

So, we now know that data is sent in packets and that the destination and source address is written in the headers.

In a normal worldly scenario, what happens to the letter which you had dropped in the mail box? It goes to your area post-office, there based on the destination address it is sent to either the City post office or if the destination address is within the area of the same post-office, it is delivered. In real world, we have a hierarchy of post-offices. City Post offices cover lot of area post offfices. Country post offices are used for sending international mails etc. Same structure is used for receiving the letter too. First it is delivered to the city post office, from where it is delivered to the area post office and finally those soothing words reach you.
Computer networks are similar. Just replace post-offices by what are called routers. And the basic operation is pretty much similar. The packet which you sent first reaches a router which is in-charge of your local area ( called Local Area Network or LAN ) . The router will decide where it should send the packet based on the destination address. Your LAN router will send it to either another router in the same hierarchy or to a router which is one level up in hierarchy. The interconection of these routers is what is referred to as the network topology, and these may vary based on the requirements.

So, lets get to some nitty-gritties now,some tech details. If it gets too geeky somewhere, apologies for that are tendered now itself
When a packet reaches a router, we have said that it decides where to send it based on the destination address. Just exactly how does it do that? The answer lies in what is called a routing table. Each router has a routing table. These routing table contains the information which is required to know where to send the packet. Each router is basically a machine with several network interfaces. A typical routing table entry looks like:
Destination Address Mask Gateway METRIC INTERFACE
Based on the Destination address, router decides what thru what interface should the packet be sent out. The information of which interface to send it out is equivalent to the information where to deliver the packet. Coz, once you decide the interface, you put the packet on-wire on that interface .If normal conditions prevail, then there will be something at the other end of the wire. So, whether you say that I have to send the packet to router B or that I have to send it out via interface IF1 ( which is connected to router B), you mean the same thing. In networking terminology, router B is called the nexthop and IF1 is called the outgoing interface.
So thats that about routing tables. Now, you will say: Hold your horses. Before you carry on, who will explain what do the other fields mean. Now, dont blame me for making it geeky. These are the meaning of the entries:
Destination Address and MASK together determine what is called the Destination Prefix. They define what is called a subnet. Destination Prefix and subnets are just a simple concept of aggregating toghether computers which are in the same network hierarchy. For eg, the state name can be considered as a network prefix. The letters destined for any city in the state have the same state name, thereby enabling post offices to send the packet to the correct state.
GATEWAY is simply the IP address of router B. METRIC is a admin-configurable value assigned to the link (wire) connecting our router to router B.
The above was the basics of the routing table. But any information will not appear by itself. SO, the next logical question is: Who Put it there ?

Networking .. What is it all about

Its amazing how similar computer networks are to human networks. In the end, both are just a set of entities wanting to talk to each other. Humans have etiquettes, computers have protocols. Humans use pre-defined languages to communicate, computers use pre-defined packet formats.Humans use postal addresses (well, at least we used to) for communication, comps use ip or mac addresses. So you see, in the end, its just about that basic need, communication.
This series of articles will try to approach the field of computer networking as just an extension of the concepts inherent in human networking. As we proceed, it is inevitable that the explanations will become more and more technical. The effort from my side will always be to map it to very simple terms.
To begin with, lets define a computer from a network perspective. You will pause here and say that Come’on , I know what a computer is. To which I will say, “define from network perspective”. That you have a machine which has loads and loads of applications has nothing to do with the network. The only hardware that matters for the network is what is called a Network Interface. I am purposely not calling it a Network Interface Card, for reasons which will become clearer later.
So, what is a network interface? Very simply defined, network interface is a hardware which allows one to be plugged-in, get connected to the network. The LAN wire that we put in our comps is a network interface. Your bluetooth connection is thru netowrk interface. Infra Red Port is a network interface. Any entity in your comp which allows you to communicate with another comp is a network interface.
How does that map to real world. Any address identifier that you have which makes your location unique and communication possible is an example. Your house address, office address, cubicle number are all address identifiers. As we have diff such identifiers in real life, similarly we may have multiple such identifiers in the world of computer networks.

For communication to happen in real world, what is the condition to be imposed on these identifiers? The necessary condition is that within the geographical range in which the communication is to be established, the mails to be exchanged, the identifier should be unique. Non-uniqueness of the identifier is permissible provided it happens in two diff communication domains. For eg, zip codes of two cities, one in India and one in US may be same. But they will not cause any problem. The Zip code inside India has to be unique.
Similar condition exists fro comp networks.The network identifier should be unique. What is that unique identifier? For majority of applications, what is called the IP Address is that unique entity. Just like when you send a letter, you write the destination address and source address, similarly, for every packet (chunk of the letter) sent on network, where the packet should reach is indicated by the dest IP Address and source indicated by Source IP Address.
Now, you will ask me , hold on what is a packet ? When we send a letter from point A to point B, we follow the following seqeunce:
1. We write the letter
2. Put it in an envelope
3. Write the source and destination address
4. Put it in a mail box
(For those of you are unaware of the above, try writing a letter to someone. Believe me , worth the time and effort. Slowing things down in today’s fast world is a a good exp. More on that in some other post.)
In case of computer networks, its not much dissimilar .Replace letter by the data which you need to send.The seq of steps are as follows.
1. Break data so that it can fit into envelopes
2. Put each chunk of data into an envelope
3. Write the source and destination address
4. Send it to your post office (router/switch)
The content that we send finally looks something like this:

where denote single or multiple notifications which are either used for a) sending the packet eo destination b) maintaining/verifyifg the integrity of the packet
and
is just data