Linked Lists

Linked list is one of the fundamental,simplest and most common data structures in C programming language.A linked list is a data structure consisting of a group of nodes which together represent a sequence.Each node comprises of data and a link to the next node in the sequence.

Advantages of Linked List over an array-

1.Linked list is a dynamic data structure whose length can be increased or decreased at run time.An array is a static data structure that is length of array cannot be altered at run time.

2.In an array, all the elements are kept at consecutive memory locations while in a linked list the elements (or nodes) may be kept at any location but still connected to each other through pointers.The list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk.

3.Linked lists are preferred mostly when we don’t know the volume of data to be stored.

Creating a Linked List-

A block in a linked list is represented through a structure-

typedef struct node_type
{

int data;
struct node_type *link;

} node;

The value ‘data’ can be any value while the pointer ‘link’ contains the address of next block of this linked list.
The ‘next’ pointer of the last node would contain a NULL.

A node is created by allocating memory to a structure in the following way-

struct node_type *ptr = (struct node_type*)malloc(sizeof(struct node_type));

The pointer ‘ptr’ now contains address of a newly created node.

To assign a value to the node-

ptr->val = data;

To assign its next pointer,the address of next node-

ptr->next = NULL;

The first node of the list is known as head node.

Algorithm-

//initialization

head->data=X;
head->next=NULL;

PROCEDURE-

//let the new node be temp
//inserted at the beginning

temp->data=X;
temp->next=head;

head=temp;

REPEAT PROCEDURE

Code-


//Insertion at the beginning of the list

typedef struct node_type
{

int data;
struct node_type *link;

} node;

typedef node *list;

list head;

//value to be entered in the list is dat which is the input 

scanf("%d",&dat);

//creating the first node

head=(list)malloc(sizeof(node));

head->data = dat;
head->link=NULL;

list temp;

//dat!=99 denotes stopping condition

while(dat!=99)
{
scanf("%d",&dat);

//creating node
temp=(list)malloc(sizeof(node));

temp->data=dat;
temp->link=head;

//since inserted at the beginning
// the new node will become the head

head=temp; 

}

//Printing the list

temp=head; //initialization

while(temp!=NULL)
{
printf("%d ",temp->data);

//going to next node
temp=temp->next;
}

Leave a Reply

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

*

* Copy This Password *

* Type Or Paste Password Here *

42,320 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>