Splat | WiseTome.com

This time, we will look at yet another data structure - tree. The structure of the tree is quite different from the linked list. Going into details of tree data structure makes it look much lesser like a list and more like - well - a tree.

But it must be noted that the ‘linked’ can still remain in a description. The tree data structure is a set of linked nodes. They are linked in a specific manner. The fundamental nodes have following elements.

• Data element
• One or more reference elements

The tree structure has a root node, which contains data and contains references to child nodes. The child nodes, recursively will have data elements and reference to more nodes. This continues down to different branches, and ends when the entire bottom most nodes have their reference nodes empty. The child nodes are also called as leaf nodes.
Read the rest of this entry »

We have been looking into data structures in this series. First we looked at linked list, and then a specialization of it - the queue. The linked list can also be specialized to form a structure, that is called Stack.

The stack behaves - well, just like a stack of boxes. If queue were a first-in-first-out setup, then stacks have a ‘first in, last out’ or the FILO configuration. Nodes that are added in the beginning would be removed at the end after all other nodes that were added after it are removed.

As with the queue, these two operations are made to operate on the list in a certain way for it to be a stack.

• Push - or add node
• Pop - or retrieve node

When a node is added, it is added at the ‘top’ of the list. Also, when a node is poped, it is done so from the top. (In the context of stack, ‘top’ and ‘bottom’ are used instead of start and end of a list).

We can state the operations performed for pushing and popping a node in pseudo code.
Read the rest of this entry »

In the last post of the series, we looked at the linked list - the basic form of data structure. In this part, we will look at the specialized type of a linked list - a queue.

The queue is nothing but a linked list, and the protocols to add and remove data from the queue are specified in a certain way. These specific constraints, when applied to a linked list, gives us a queue.

The queue of the software realm acts quite similar to the queue you find in real life. It is quite similar to the queue you find at movie theaters or bank teller counters. When people need to join the queue, they do so from behind - at the end of the queue. When they need to leave the queue, it is done at the starting point of the queue. The protocol is said to be ‘first in, first out’.

Read the rest of this entry »

Data structures give order to the abstract world of code (software). There are many types of data structure. Among them linked list is the most fundamental type of data structure. Using one or another form of linked list, other data structures (queues or stacks for example) can be created.

Let us look at the theory behind linked list. I promise to try and make it interesting.

The basic unit of a linked list is what is called a node. A node is something like a Lego brick, many of which you can combine to create something. As with the Lego brick, there are different types of nodes, but the most basic form contains a data element and a reference element.

• Data Element - As the name suggests, the data element holds the data. It can be anything from simple data like numbers or characters, to complex data like a record holding the details of a song in a music album.
• Reference Element - Reference element is of the node can either be empty or be containing the information of where the next node of the list is present. When implemented in machine code, it has the address within the memory where the next node is residing.

Read the rest of this entry »

As we came to the end of the Journey Of Code series, we moved on from the realm of hardware and stepped into the world of software - the abstract world. Software can be called abstract because there is really no physical structure for it. And these abstract concepts can easily become disorganized.

The software can be broadly classified to be code and data. When we say data - it is meant the whole concept of storing the data, and also how the data is stored.

The data structures are protocols or concepts that say how the data is stored. By storing it in a particular way - a particular operation on the data is optimized in terms of memory required and also time required to perform the operation. A well designed data structure needs to perform set of operations using as few resources (time and memory) as possible.

You must realize though, that there is no ideal type of data structure to this date. Every data structure has its own set of advantages and disadvantages based on the operations it is subjected to. That is the reason why there are different data structures which are used in situations where they perform the best.

The different data structures are made up of units called native data types and references. They are called by different names in different languages. By using these units in a certain way, different kinds of data structures can be constructed.

Some of the types of data structures are as follows.

• linked lists
• queues
• stacks
• trees
• graphs

This is not a exhaustive list - there are many more.

But we can look at some of them - and that is what we will be doing in the posts that will follow in this series.

The series, Journey Of Code, comes to an end with this post. During this journey we have explored the technology stack from transistors, logic gates, chip level units, processors and the interface between the hardware and software – machine code.

The exploration has led us to the realm of software. It may be an end to this series, but it is a realm that deserves several such journeys. We will though, briefly look into the different aspects of software and applications.

As we have seen in the earlier post, the machine code is written using the mnemonic – assembly language. In spite of the use of these human readable syntax, it can get quite complex and cumbersome to design applications that would serve any purpose more than simple calculator. Even a calculator application could get out of hand.

To alleviate from this problem, high level languages were created. These programs take more complex syntax which make it simpler to write programs, and compile them into machine code. Applications can be made to perform several complex tasks with the help of the code that is generated from compiling the programs written in high level languages.

The processors, as we have seen can perform a basic set of operations. These set of operations when combined in a certain way perform myriad of tasks. In order to reduce the size of applications and also to manage the loading and execution of these programs, operating systems were designed.
Read the rest of this entry »