You are here:   HomeData StructuresLinked ListsWhat is Linked lists? How Many Type of Link List

# What is Linked lists? How Many Type of Link List

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.

Types of linked lists

The different types of linked lists include:

1.  Singly linked lists

2.  Circular linked lists

3   Doubly 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

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.

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

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.

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.

Subscribe To Free Daily Newsletter!

Get Free News Updates Delivered Directly To Your Inbox
 Name E-mail

Dinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes 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.

What's New and Popular

Popular Article

Search Content

Basic Courses