Hello Viewer! how are you? I hope you are very well. Today I have learned about Linear & Non-Linear Data Structure. below I have written whatever I learn today ...
Linear Data Structure
If the elements of a data structure are stored in a linear or sequential order then it is a linear data structure.
- examples: Arrays, Linked List and Queues
Linear Data Structure can be represented in memory in two different ways.
- One way is to have a linear relationship between elements by means of sequential memory locations.
- The other way is to have a linear relationship between elements by means of links.
Non-Linear Data Structure
If the elements of a data structure are not stored in sequential order then it is Non-Linear Data Structure.
The relationship of adjacency is not maintained between elements of a non-linear Data Structure.
- examples: Trees and graphs
ARRAYS
- An array is a collection of similar data elements.
- These Data Elements have the same data type.
- The elements of the array are stored in consecutive memory locations and referenced by an index. (aka subscript)
In C, arrays are declared using the following syntax:
- type_name [ size ]
- example: int marks [5]
The above array declares an "Array" name marks that contain 5 elements.
In C, arrays index starts from 0 [Zero]. The 1st element will be stored in marks[0], 2nd element will be stored in marks[1] and so on and so forth. therefore the last element that is the 5th element will be stored in marks[4]. fig(1) shows how elements will be stored in memory.
Arrays are generally used when we want to store large amounts of similar types of data but they have the following limitations:
- Arrays are of fixed size
- Data elements are stored in contiguous memory locations may not be always available.
- Insertion and Deletion of elements can be problematic because of the shifting of elements from their positions.
However, these limitations can be solved using a linked list. we will discuss more about arrays in upcoming posts.
LINKED LIST
A linked list is a very flexible data structure in which elements(called nodes) form a sequential list
In contrast to static arrays, a programmer need not worry about how many elements will be stored in a linked list. this feature enables the programmers to write a robust program that requires less maintenance.
In a linked list each node is allocated space as it is added to the list. every node in the list points to the next nodes in the list therefore in a linked list every node contains two types of data.
- The value of the node or any other data that corresponds to that node.
- A pointer or link to the next node in the list.
The last node in the list contains a NULL pointer to indicate that it is the end of the list.
Since the memory for the node is dynamically allocated when it is added to the list, the total number of nodes that may be added to a list is limited only by the amount of memory variable. fig(2) shows a linked list of five nodes.
Note:
- Advantage: easier to insert or delete data elements.
- Disadvantage: Slow search operation and require more memory space.