4.4 Linear

Linear Data Structure:

Linear data structure is linear if element is adjacent to each other. It has exactly two
neighbors elements to which it is connected as its previous and next member.

Example of Linear Data Structure

Array
Linked List
Stack
Queue

Non- Linear Data Structure

Non-Linear data structure is that if one element can be connected to more than two
adjacent element then it is known as non-linear data structure.

Example of Linear Data Structure:

Tree
Graph 

Difference Between Linear and Nonlinear Data Structures

 A data structure is a method for organizing and storing data, which would allow efficient data retrieval and usage. Linear data structure is a structure that organizes its data elements one after the other. Linear data structures are organized in a way similar to how the computer’s memory is organized. Nonlinear data structures are constructed by attaching a data element to several other data elements in such a way that it reflects a specific relationship among them. Nonlinear data structures are organized in a different way than the computer’s memory.

Linear data structures

Linear data structures organize their data elements in a linear fashion, where data elements are attached one after the other. Data elements in a liner data structure are traversed one after the other and only one element can be directly reached while traversing. Linear data structures are very easy to implement, since the memory of the computer is also organized in a linear fashion. Some commonly used linear data structures are arrays, linked lists, stacks and queues. An arrays is a collection of data elements where each element could be identified using an index. A linked list is a sequence of nodes, where each node is made up of a data element and a reference to the next node in the sequence. A stack is actually a list where data elements can only be added or removed from the top of the list. A queue is also a list, where data elements can be added from one end of the list and removed from the other end of the list.

Nonlinear data structures

In nonlinear data structures, data elements are not organized in a sequential fashion. A data item in a nonlinear data structure could be attached to several other data elements to reflect a special relationship among them and all the data items cannot be traversed in a single run. Data structures like multidimensional arrays, trees and graphs are some examples of widely used nonlinear data structures. A multidimensional array is simply a collection of one-dimensional arrays. A tree is a data structure that is made up of a set of linked nodes, which can be used to represent a hierarchical relationship among data elements. A graph is a data structure that is made up of a finite set of edges and vertices.

Difference between Linear and Nonlinear Data Structures

Main difference between linear and nonlinear data structures lie in the way they organize data elements. In linear data structures, data elements are organized sequentially and therefore they are easy to implement in the computer’s memory. In nonlinear data structures, a data element can be attached to several other data elements to represent specific relationships that exist among them. Due to this nonlinear structure, they might be difficult to be implemented in computer’s linear memory compared to implementing linear data structures. Selecting one data structure type over the other should be done carefully by considering the relationship among the data elements that needs to be stored.


Since the computer's memory is also linear, it is very easy to see how we can represent this list with the computer's memory. Any data structure which organizes the data elements one after the other is known as linear data structure. So far we have seen two examples of linear data structures: the string data structure and the ABC company list.

You may have noticed that these two examples of linear data structures resemble to each other. This is because they both are really different kinds of lists. In general, all linear data structures look like the list. However, this does not mean that all the linear data structures are exactly the same. Suppose I want to design a list to store the names of the ABC employees in the computer. One possible design is to organize the names similar to the example picture above. Another possible design is to use the pointers we learned about in the last lesson. While these two designs provide the same functionality the way they are implemented in the computer is much different. This means that there is an abstract view of a list which is distinct from any particular computer implementation


You may have also noticed that the picture of the ABC employees is not as exactly the same as the original list. When we make a list of names, we tend to organize this list into a column rather than a row. In this case, the conceptual or logical representation of a list is the column of names. However, the physical representation of the list in the computer's memory is the row of strings. For most data structures, the way that we think about them is far different from the way they are implemented in the computer. In other words, the physical representation is much different from that of the logical representation, especially in data structures that use pointers. 

#include <stdio.h>


#define SIZE 100

int linearSearch( const int array[], int key, int size );

int main()
{
    int a[ SIZE ];
    int x;
    int searchKey;
   int element;

   for ( x = 0; x < SIZE; x++ ) {
        a[ x ] = 2 * x;
    }

    printf( "Enter integer search key:\n" );
    scanf( "%d", &searchKey );

   element = linearSearch( a, searchKey, SIZE );

    if ( element != -1 ) {
        printf( "Found value in element %d\n", element );
    }
    else {
        printf( "Value not found\n" );
    }

    return 0;

}

int linearSearch( const int array[], int key, int size )
{
    int n;
    for ( n = 0; n < size; ++n ) {
        if ( array[ n ] == key ) {
            return n;
        }
    }
    return -1;

}