by Dinesh Thakur Category: Linked Lists

A linked list can be viewed as a group of items, each of which points to the item in its neighbourhood. An item in a linked list is known as a node. A node contains a data part and one or two pointer part which contains the address of the neighbouring nodes in the list.

Linked list is a data structure that supports dynamic memory allocation and hence it solves the problems of using an array.

The different types of linked lists include:

In singly linked lists, each node contains a data part and an address part. The address part of the node points to the next node in the list.

Node Structure of a linked list

An example of a singly linked list can be pictured as shown below. Note that each node is pictured as a box, while each pointer is drawn as an arrow. A NULL pointer is used to mark the end of the list.

A head pointer to a list

Possible Operations on a singly linked list

Deletion: Elements are deleted at any position in a linked list by altering the links of the adjacent nodes.

Searching or Iterating through the list to display items.

To insert or delete items from any position of the list, we need to traverse the list starting from its root till we get the item that we are looking for.

Implementation of a singly linked list

A node in a linked list is usually a structure in C and can be declared as

struct Node

{

int info;

Node *next;

}; //end struct

A node is dynamically allocated as follows:

Node *p;

p = new Node;

For creating the list, the following code can be used:

do

{

Current_node = malloc (sizeof (node) );

Current_node->info=input_value;

Current_node->next=NULL;

if(root_node==NULL) // the first node in the list

root_node=Current_node;

else

previous_node->next=Current_node;

previous_node=Current_node;

scanf("%d",&input_value);

} while(x!=-999);

The above given code will create the list by taking values until the user inputs -999.

Inserting an element

After getting the position and element which needs to be inserted, the following code can be used to insert an element to the list

if(position==1||root_node==NULL)

{

Current_node->next=root_node;

Root_node=Current_node;

}

else

{

counter=2;

temp_node=root_node;

while((counter<position) &&(temp_node!=NULL))

{

counter++;

temp_node=temp_node->next;

}

Current_node->next=temp_node->next;

temp_node->next=Current_node;

}

The following figure illustrates how a node is inserted at an intermediate position in the list.

The following figure illustrates how a node is inserted at the beginning of the list.

Deleting an element

After getting the element to be removed, the following code can be used to remove the particular element.

temp_node=root_node;

if ( root_node != NULL )

if ( temp_node->info == input_element )

{

root_node=root_node->next;

return;

}

While ( temp_node != NULL && temp_node->next->info !=

input_element )

temp_node = temp_node->next;

if ( temp->next != NULL )

{

delete_node = temp_node->next;

temp_node->next=delete_node->next;

free ( delete_node ) ;

}

The following figures illustrate the deletion of an intermediate node and the deletion of the first node from the list.

To display the elements of the list

temp_node = root_node;

while(temp_node != NULL)

{

printf("%d\t", temp_node->info);

temp_node = temp_node->next;

}

The following figure illustrates the above piece of code.

The effect of the assignment temp_node = temp_node->next

Although arrays require same number of comparisons, the advantage lies in the fact that no items need to be moved after insertion or deletion.

As opposed to fixed size of arrays, linked lists use exactly as much memory as is needed.

Individual nodes need not be contiguous in memory.

Dinesh Thakur holds an B.C.A, MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.

Related Articles