Turn Desktop View Off
by Dinesh Thakur

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.

 

Types of linked lists

 

The different types of linked lists include:

 

1.  Singly linked lists

2.  Circular linked lists

3   Doubly linked lists

 

Simple/Singly Linked Lists

 

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

 

                                             Node Structure

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.

                  singly linked list

The head pointer points to the first node in a linked list If head is NULL, the linked list is empty

Head Pointer

 

A head pointer to a list

 

Possible Operations on a singly linked list

 

.Insertion: Elements are added at any position in a linked list by linking nodes.

 

 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

 

Creating a 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.

 Insert a Node

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

 Insert a Node at the Begining

 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.

 Delete Intermediate

Delete First

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.

 Piece Of Code

The effect of the assignment temp_node = temp_node->next

 

Efficiency and advantages of Linked Lists

 

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.