Data structure is simply a group of data elements put together under one name. The main goal of using data structure is to have good organization of data. Data structure has many applications in the real world, also many ways to implement it. It is imperative to understand that the following article will be based on C language. To begin this topic, we will go through array and pointer, followed by a brief description about data structure, and last, implementation examples of data structure, including linked list, stack, queue, and binary tree.

Before we study deeper, it is important to understand the following terms:

• Traversal means accessing each data elements exactly once to be processed.
• Searching is used to find a location of data elements that satisfy the given constraint(s). The data searched may or may not exist on the structure.
• Inserting means adding new data to the structure.
• Deleting means removing a data from the structure.
• Sorting is done to arrange data elements in order, either ascending or descending.
• Merging is combining two or more sorted data items to form a new single list of sorted data elements.

ARRAY

An array is a collection of similar data type, stored in consecutive memory location. The location of the array is referenced by an index (usually starting from 0). To declare an array, we must set the data type, then the array’s name, and the memory allocated or the size for that array. For example:

int num[10]      (ex. 1)

The example above (ex. 1) will allocate 10 memory location for array num that can only contain integer data type, declared int above. The first element will be written as num[0] and the last element is called num[9]. Any attempt to enter more than 10 integers to the array num will result in buffer overflow.

 

Fig. 1 – Representation of array num[10]

So, we can conclude that to declare an array, the following syntax must be typed correctly:

data_type array_name[array_size];      <def. 1>

If more than one dimension array is needed, simply add [array_size] after the previous array size (data_type array_name[array_size1][array_size2];).

POINTER

A pointer is a variable of a data type that contains another variable’s location with the same data type the pointer has. Pointer points to an address of another variable to provide indirect access. The operators used are & and *. The & symbol is a symbol of address, and to access the value stored in the address, we use * symbol. The following is the syntax of pointer declaration:

data_type *pointer_name;               <def. 2>

And to make the pointer points to another variable’s value, we can type the following:

pointer_name = &target_variable;          <def.3>

The &target_variable is the address of variable target_variable, and by declaring <def. 2> and <def. 3>, we have a pointer pointer_name that points to the value of variable target_variable. This is called indirect access. And to be noted, a pointer can point to another pointer, typed **pointer_name;.

Good understanding of pointer is essential to ease the study of data structure. Therefore, if the reader has any difficulty to understand pointer, I recommend to search and study about pointer more.

DATA STRUCTURE

As stated before, a data structure is a group of data elements put together under one name. Data structure is grouped into two type, primitive and non-primitive. Primitive data structure are data types which are provided by the programming language, for instance, integer, character, float, and many more. On the other hand, non-primitive data structure is created using primitive data structures. The examples of non-primitive data structure are linked list, stack, trees, and graphs. If the elements in the data structure is stored sequentially, it is called linear structures; otherwise, it is called non-linear structures.

A data structure has three characteristics. The first is correctness, where the codes are successfully executed and execute well. The second characteristic is time complexity. In programming, programmers are required to create a program that can run with the smallest amount of time. The last characteristic is space complexity. Free memories are finite, therefore it is essential for programmers to be able to code a program that uses spaces/memories as small as possible. However, it is not easy to develop good program. Also, in using data structure, three main problem could be faced: data searching, the processor’s speed, and multiple requests. Thus, lots of practice and study is required to master data structure.

Since the concepts of data structure has been elaborated above, it is inappropriate if the basic concepts of data structure implementations are not explained. The following are the examples of data structure implementations with their brief description:

1. Array

An array is a data structure since it is a collection of data elements, contained under one name. Array’s elements are stored in consecutive memory locations, and arrays are generally used to store large amount of similar data type. However, arrays can only store similar data type and are made of fixed size. Also, it can be problematic to do insertion and deletion of data because of shifting of elements from their positions.

2. Linked list

A linked list is a very flexible and dynamic data structure since insertion and deletion can be done at any point. The memory used in linked list are not consecutive. A linked list can be either a single, double, circular, or multiple linked list. Each data element in linked list has a pointer that points to another element. The last element of a linked list could point back to the first element, or point to nowhere (point to NULL value).

Although insertion and deletion can be done easily, one may be confused with how linked list works at first. But as time flows, it will become easier.

 

Fig. 2 – Representation of linked list

3. Stack

Technically, a stack uses principle known as LIFO or FILO (Last In First Out or First In Last Out). To understand this concept better, imagine a pile of disks. The last disk inserted to the pile will always be the first to be taken. The same principle applies to the stack concept.

Fig. 3 – Illustration of stack (pile of disks)

4. Queue

Slightly different than stack, a queue is a data type that has the following principle: insertion of new data element will become the tail/rear or the last element of the data structure, and the deletion from the queue must begin from the head/front or the first data element in the structure. This principle is known as FIFO (First In First Out).

Fig. 4 – Illustration of queue

(source: http://key-to-programming.blogspot.co.id/2015/02/queue-data-structure-queue-ds-queue.html)

5. Binary Tree

A binary tree has elements (called nodes) that consist of one right pointer, one left pointer, and its data element. The left pointer points to another element that has smaller value than the data element, whereas the right pointer points to another element that has bigger value than the data element. A binary tree is usually used to do sorting, searching, creating artificial intelligence, and many more. Traversal of data can be done fast since each node has a maximum of two ‘children’ (left and right pointers).

Fig. 5 – Representation of binary tree

          To conclude, data structure is quite a topic to be mastered, but with proper training and understanding of the basic concepts used such as pointer, it will be easy to apply the implementations of data structure, such as array, linked list, stack, queue, and binary tree.

 

Source:

Reema Thareja,. 2014. Data structures using C. OXFORD. New Delhi. ISBN:978-0-19-809930-7  Chapter 1, 2, 3.

http://key-to-programming.blogspot.co.id/2015/02/queue-data-structure-queue-ds-queue.html