Facebook

Linked Lists

Linked List is the data structure that stores data elements  in a sequence. Each data element is called a Node.Each node further contains data field/fields and a pointer(Refer :Pointers ) to next node(Fig 1).

The  left part  of node has a data item and the right part of node has the address of succeeding node.The  address of elements may be  sequential or may be notSTART  node has the address of first node . The last node of linked list has  NULL  in the right part. NULL value indicates the  end of list. Chain of nodes is formed using this method.

TipIf  START = NULL ,it means that linked list does not contain any node and the list is empty.
Fig 1 : Linked Lists
FIG 2: A Linked List
Fig 2: A Linked List

In Fig 2,START  stores the address of first node(40).Nodes are at address 40,45,50,65  respectively.10,20,30,40 are the data elements in the left part .45 in first node points to second node at 45 address,50 in second points third node which is at location 50,65 in fourth part points to last node which further does not points to anything.i.e. the last node of list.

 

Implementation of Linked List

Linked lists are implemented in C through structures(Refer :Structures).

Syntax

struct node//Fig 3
{
int data_item;
struct node *link
};
  • node is the name of structure.
  • data_item of int type refers to element of linked list.
  • *link  is a pointer variable of structure .
Fig 3 : A Linked List
Fig 3 : A Linked List

Traversing a Singly Linked List

Program 1

#include<stdio.h>
struct node
{
    int item;
    struct node *link
};

int main()
{
    struct node *start,*list;
    int i;
    start = (struct node *)malloc(sizeof(struct node)); //Refer Program 2 for working of this statement.
    list = start;
    start->link = NULL;
    for(i=0;i<5;i++)
    {   
        list->item = i;
        list->link = (struct node *)malloc(sizeof(struct node));
        list = list->link;
    }   
    list->link = NULL;
    while(start != NULL)
    {   
        printf("%d\n",start->item);
        start = start->link;
    }  
    return 0;
}

Run

 

 

Illustration of Program

  • node is the name of structure.
  • item of int type refers to element of linked list.
  • *link is a pointer variable of structure used to point to next address.
  • *start and *list refers to pointer variables of structure.
  • The function malloc is used to allocate a certain amount of memory during the execution of a program. The malloc function will request a block of memory from the heap. If the request is granted, the operating system will reserve the requested amount of memory.
  • malloc allocates sizeof(struct node) bytes, and returns a void pointer to it, which we cast to  struct node *.
  • start points to the first node of linked list.

Working of Program 1

Screen Shot 2014-04-02 at 5.06.32 PM
Fig 4 : Working of Program1

Program 2

#include<stdio.h>
struct node
{
    int item;
    struct node *link
};

int main()
{
    struct node *start,*list;

    start = (sizeof(struct node));
    printf("%d\n",start);
    start =malloc(sizeof(struct node));
     printf("%d\n",start);
     start =  (struct node*) printf("%d",start);
     printf("%d\n",start);
     return 0;
};

Run

 

 

Practical applications of linked list

  • A list of images that need to be burned to a CD in a medical imaging application
  • A list of users of a website that need to be emailed some notification
  • A list of objects in a 3D game that need to be rendered to the screen
Rate this post

Comments

This post currently has one response

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar