Data Structure operations
Data Structure is defined as a mathematical or logical model to store data and perform operation on the stored data. The operations are the functions using which the data can be processed. All the data structure have some common operations to manipulate data and process it for the user. The most common data structure operations are as following
Traversal of a data structure can be defined as the process of visiting every element of a data structure at least once. This operation is most commonly used for printing, searching, displaying or reading the elements stored in the data structure. It is usually done by using a variable or pointer that indicates the current element of the data structure being processed. This variable or pointer is updated after visiting an element so that the location or address of next element can be found. When the last element of the data structure is reached the traversal process ends. Traversal can be useful when all the elements of the data structure have to be manipulated in similar way.
In an array traversal begins from the first element. A variable stores the index of first element of the array and it is incremented after visiting each node. When the value of this variable is equal to the index of last node, the traversal of the array ends.
Once a data structure is created, it can be extended by adding new elements. The process of adding new elements in an existing data structure is called insertion. Where the element can be added depends upon the data structure that a user is dealing with. Insertion operation always ends up in increasing the size of the data structure.
A linked list and an array allow a user to insert a new element at any location. A stack and a queue allow a user to insert a new element only at a specific end. New nodes can be added to a graph or tree in a random fashion. For all the data structure the insertion can be done till the data structure has enough space to store new elements either due to its defined size or memory availability. A condition when a user tries to insert a new element in a data structure that does not have the needed space for new element is called Overflow
Once a data structure is created, a user can remove any of the existing elements and free up the space occupied by it. The process of deleting an existing element from a data structure is called deletion. Which element can be deleted depends upon the data structure that a user is dealing with. Deletion operation always ends up in reducing the size of the data structure.
A linked list and an array allow a user to delete a existing element at any location i.e. start, mid or end. A stack and a queue allow a user to delete an element only at a specific end. Nodes can be deleted from a graph or tree in a random fashion. For all the data structure the deletion can be done till the data structure has elements. A condition when a user tries to delete an element from a data structure that does not have any element is called Underflow
The process of locating an element in data structure and returning its index or address is called Search. This is the most commonly used operation in a data structure. Since a data structure stores data in an organized fashion for convenient processing, it is important that an element could be easily located in a data structure.
When performing search in a data structure a key value is needed, this is matched with the values stored in the data structure. When the value of the element matches the key value successful search is done and the search operation returns the location of that element. If the key value does not match any element in the data structure and reaches end, it is unsuccessful search and a null location is returned as a result of search operation.
For example in a list of students containing registration number, name and score of students of a course, then searching can be done with registration number as the key value. The user has to provide the key value i.e. registration number here for which she is searching the data structure. If the data is unsorted then each registration number in list is compared with the key value to perform search operation.
The process of arranging the data elements in a data structure in a specific order (ascending or descending) by specific key values is called sorting. The students records stored in an array can be sorted by their registration numbers, names or the scores. In each sorting the criteria will be different to fulfill the processing needs of a user.
Sorting may result in physical relocation of elements or it can be just a rearrangement of key values as index without changing the physical address of complete data element so that a subsequent traversal operation displays the data in sorted manner.
Merging can be defined as the process of combining elements of two data structures. In a simpler form merging can be treated as appending set of elements of one data structure after elements of another data structure of same element structure. For example two arrays containing student data of two different classes with same fields to form one list. The final data structure may or may not be sorted.
Another form of merging can be to merge two data structure of different constructions to create totally new data structure. For example one data structure with student registration number and name can be merged with another data structure containing course and result data of same set of students to form one list( or file)
The process of copying is the operation that makes a new data structure from an existing data structure. In the process of copying the original data structure retains its structure and data elements. The new data structure has same data elements. Both these data structure can be used to perform all the operations discussed previously. Changes in one data structure will not affect the elements or count of elements of the other data structure.