Array and Linked List Data Structure

336
data structure

Data Structure is a method by which we can collect and organize data so that various operations can be performed on the data in an efficient manner. Various data structures which are used are array, queues, file, table, tree, heap, linked list etc. all these data structures hold various data types like int, char, float etc.

In this article we will be discussing about the array and the linked list data structures.

Array in Data Structure

An array can be defined as a collection of data stored at contiguous memory locations. The concept behind array is to keep multiple data items of same data type together at contagious memory locations to make it easy to locate the position of each data element by adding an offset to a base value. Let us first discuss about some important terms to understand Array.

  • Element: Element is the data item stored in the array.
  • Index: Each position of an element in an array has a numerical index associated with it, which is used to identify the element.
  • Offset: An offset is an integer which indicates the distance or displacement between the first element and a given element or point, within the same array.

Elements stored in arrays can be accessed randomly to make access fast.

An array of type int or float is called an array but an array of characters is called a ‘string’.

Now, let us look into how arrays are represented and declared in C language:

data_type array_name [array_size];

An integer type array is defined as:

int A[5]=[4, 5, 2, 20, 6]

The above declaration declares an array A of integer type which can hold five elements and the elements are

 A[0]=4,

A[1]= 5,

A[2]=2,

A[3]=20 and

A[4]=6.

This is example of one dimensional array. Array can be one dimensional or multi-dimensional.

So, a multi-dimensional array can be declared as

data_type array_name [array_size1][array_size2]….[array_sizen];

Example of a two-dimensional array:

int B[2][2]= [1, 3][2, 4];

This is an integer type array which has two rows and two columns. Position of each array is given as:

B[0][0]=1;

B[0][1]=3;

B[1][0]=2and

B[1][1]=4

Operations Performed on Arrays

We can perform various operations on arrays like searching, sorting, adding an element, deleting an element etc.

Linked List in Data Structure

Linked List is also a linear data structure like arrays but elements of linked list data structure are not stored at contiguous memory locations. The elements in linked list are linked using pointers. A linked list is represented by a pointer which indicates the first node of the linked list. This first node is known as head. Linked list consists of collection of nodes and if the linked list do not hold any data or value, then head value is NULL.

The linked list nodes consists of two parts:

  1. Data node: data item is stored in data part and pointer 
  2. Pointer: pointer is reference to the next node

Representation of linked List

Nodes of linked list are represented using structures and pointers C. Now, let us see how to declare and represent the linked list in C language:

struct linkedlist {

            int data

struct linkedlist *next;

}:  

This is an example of a linked list node with an integer data.          

A linked list can be single, double or circular.

Let us look upon the pictorial representation of all three types of linked lists.

Single Linked List

Head indicates the first node of the linked list.

Data saves the data item to be stores in the linked list.

Pointer is reference to the address of next data element.   

Double linked list

Double linked list has two pointers as prev and next.

Prev is a pointer to refer the previous data node.

Next is a pointer to refer to the next location of data element.

Circular Linked List

As we can see the pointer of the last node points to the first node in circular linked list.

Array vs Linked List

Both Arrays and Linked List are linear data structure used to store data of similar types. Now let us compare both the data structure:

  1. An array is a collection of similar type of data elements and the Linked list is a collection of unordered linked elements called nodes.
  2. Element in a linked list cannot be randomly accessed, they need to be accessed serially, but we can randomly access any element in array randomly by proving its index.
  3. Operations like insertion and deletion in linked list are easy and fast whereas it is time consuming in arrays
  4. Arrays have fixed size but the size of linked lists can be expanded or contracted depending on the need, since they are dynamic and flexible.
  5. Memory assignment in arrays is done during compile time and in Linked list it is done at the execution or runtime.
  6. Elements are stored in contagious memory locations in arrays but in linked list data is stored randomly.
  7. The arrays require less memory as actual data is stored within the index. But in linked list memory requirement is more because of pointers prev and next.
  8. Memory utilization in linked list is efficient as compared to arrays.

Conclusion

Both array and linked list are data structure. They are used to arrange store and manage data. Both are linear data structure. Both have their advantages and disadvantages.

Leave a Reply !!

This site uses Akismet to reduce spam. Learn how your comment data is processed.