position: fixed; top: auto !important; margin-left: 112px;

Linked List

Till now we all studied about arrays right? Arrays are used to store data of the same type. In arrays, we must know the size of the array. That's why an array size is fixed every time.

For example,

Assume there is an array like this,

1030 40 50 60 70

Now suppose you want to add 20 at first index after 10. Now to insert 20 after 10 you have to shift everything one position towards the right. So a shifted array looks like this,

1020 30 40 50 60 70

Now think for a while, how expensive an operation of shifting elements of an array is. Now suppose you have to remove element 30 from an array. So you have to shift all the elements towards left. Here well-known Data Structure is being used called the Linked list in Data Structures.

ArrayList vs Linked List

Difference between Array and Linked list is explained here by advantages of Linked List over Arrays.

1) Dynamic size 
2) Insertion/Deletion is easy in Linked List.

What is Linked List?

The linked list is a linear data Structure used to store elements dynamically. No need to know the actual size. In the case of arrays, you must know the size of an array. Linked List in Data Structure gives better advantages than arrays.

Linked List looks like this

    +---+-----+------       +----+----+------         +----+----+-----
    | Data | Pointer|-----> | Data | Pointer| ------> | Data  | NULL |  
    +---+-----+------       +----+----+------         +----+----+-----

Linked List is created using nodes. Each node contains Data and Pointer. And each Pointer is attached with Next pointer. And the end Pointer contains NULL to indicate that the linked list is finished. The first Node is HEAD always.

Program to introduce Linked List

This basic linked list in C programming explains the concept of how to create the linked list in Data Structures.

           head        first             Second
             |            |                |
             |            |                |
             V            |                |
        +---+---+     +---+---+       +----+------+
        | 1  | o----->|  2  | o-----> |  3 | NULL |
        +---+---+     +---+---+       +----+------+    
/* Created by Manish Methani
Copyright @Codzify */

// A simple C program to introduce a linked list
#include <stdio.h>
#include <stdlib.h>
struct node 
  int data;
  struct node *next;

/* Program to create a simple linked list with 3 nodes */
int main()
  struct node* head = NULL;
  struct node* first = NULL;
  struct node* second = NULL;
/* allocate 3 nodes in the heap  */
  head = (struct node*)malloc(sizeof(struct node)); 
  first = (struct node*)malloc(sizeof(struct node));
  second = (struct node*)malloc(sizeof(struct node));
  head->data = 1;       //assign data in head node
  head->next = first;  // Link head node with the first node

  first->data = 2;      //assign data to first node
  first->next = second; // Link first node with the second node
  second->data = 3;      //assign data to second node
  second->next = NULL;    
  return 0;

Note, firstly head is pointing to head node. Then head node to the first node and the first node to the second node.

Comments itself are self-explanatory. What we did is first we allocated three Nodes using malloc named head, first, second. Then we added data in the head node and linked it with the first node. Then we added data to the first node and linked it with the second node. Then we added data to the second node and then added NULL to indicated the end of the linked list.

It's easy if you looked at the program carefully. Just three boxes. Add data into it and link it to the next node. Now you can create any number of nodes you want.

Solve the Quiz of Article

1) While implementing the bubble sort algorithm, what do you think algorithm needs n - 1 comparison in Pass 1?

2) What do you think best case performance of Bubble Sort Algorithms is O(n2)?

Previous Next Article


Largest collection of up-to-date tutorials to learn programming languages. We are focused on easy learning. Massive collection of interview questions one may need for preparation.

Social Profile


Copyright 2018. All rights reserved.