Linked Lists

http://install4install.com

Linked Lists is the data structure which 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 data item and the right part of node has the address of succeeding node.The  address of elements may be  sequential or may be not.START  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
};
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

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



Short URL: http://tinyit.cc/c9e284
Author: Cusp2207 on April 3, 2014
Category: Computer Science, Data Structures
Tags:
1 response to “Linked Lists”
  1. Rob says:

    Very nice job. Clear and succinct.

Leave a Reply

Last articles