• Skip to main content
  • Skip to primary sidebar
  • Skip to secondary sidebar
  • Skip to footer

Computer Notes

Library
    • Computer Fundamental
    • Computer Memory
    • DBMS Tutorial
    • Operating System
    • Computer Networking
    • C Programming
    • C++ Programming
    • Java Programming
    • C# Programming
    • SQL Tutorial
    • Management Tutorial
    • Computer Graphics
    • Compiler Design
    • Style Sheet
    • JavaScript Tutorial
    • Html Tutorial
    • Wordpress Tutorial
    • Python Tutorial
    • PHP Tutorial
    • JSP Tutorial
    • AngularJS Tutorial
    • Data Structures
    • E Commerce Tutorial
    • Visual Basic
    • Structs2 Tutorial
    • Digital Electronics
    • Internet Terms
    • Servlet Tutorial
    • Software Engineering
    • Interviews Questions
    • Basic Terms
    • Troubleshooting
Menu

Header Right

Home » DS » Linked Lists

What is Linked Lists

By Dinesh Thakur

A linked list is called so because each of items in the list is a part of a structure, which is linked to the structure containing the next item. This type of list is called a linked list since it can be considered as a list whose order is given by links from one item to the next. [Read more…] about What is Linked Lists

Short Note on Single Linked List

By Dinesh Thakur

A singly linked list is a linked list in which each node contains only one link field pointing the next node in the list.

 

 Each node is divided in two parts.

1. data field.

2. pointer.

For Example: –

 

Node structure

                Single Link List

  The data field contains the data elements that have to be stored in the list. The pointer will point the next node in the list.

            The operations done on a list are: –

1     Insertion

2     Deletion

Insertion

 

 Insertion in the head node

 

To insert a node in the head node, just change the pointer field of the new node to point to the head node. Let the new node be ‘Temp’ and the head node be ‘Head’, then the insertion is

 
Temp ? data = X;

                           Head ? next = head      

 

Insertion in the middle node

To insert in the middle node we need to change two pointers. Let the new node be ‘Temp’ and the present node is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is

 
Temp? data = X

Present  ? next = temp

                 Temp  ? next = future                   

 

 Insertion in the last node

 

To insert an element in the last position just change the pointer field of the present last node to point to the new node, then set the pointer field of the new node to NULL. Let the new node be ‘Temp’ and the present node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is

                                                          Present ? next =Temp

                                                Temp ? next =null

                                                Temp ? data = X

Deletion


Deletion in the head node

To delete a node in the head node, just point the head node as the second node. Let the head node be ‘Head’, and then the deletion is

                                                Head ? next = head

 

Deletion in the middle node

 

To delete a node in the middle we need to change two pointers. Let the node to be deleted is  ‘Temp’ and the node previous to the node to be deleted is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the  data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is

                                                Present  ? next = future

                                               

 Deletion in the last node

 

To delete an element in the last position just change the pointer field of the previous node to the last to null. Let the last node be ‘Temp’ and the previous node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is

 
Previous ? next =NULL

Short Note on Singly Circular Linked List

By Dinesh Thakur

The advantage of using Circular Linked List is the last null pointer is replaced and the pointer field of the last node points to the first node, due to this circular arrangement the traversing become quite easier.

The insertion and deletion in the first and middle are same as singly linked list except the last node.
Insertion

    Insertion in the last node

To insert a node in the last position, insert the new node after the current last node, and then change the pointer field of the new node to point to the first node. Let the last node be last, the new node to be inserted to be new, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is

                                     Last ­? next = new

                                     New ? next =first

 Deletion

    Deletion in the last node

To delete a node in the last position, change the pointer field of the previous node to the current last to point the first node. Let the last node be last, the previous node to the current last node to be pre, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the deletion is                

                                  Prev ? next = first

What is Linked lists? How Many Type of Link List

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.

 

What is Doubly Linked List

By Dinesh Thakur

A more sophisticated kind of linked list is a doubly-linked list or a two-way linked list. In a doubly linked list, each node has two links: one pointing to the previous node and one pointing to the next node.

 

Node structure

 Node Structure

Implementation of a doubly linked list

 

Adding an element to the list

 

To add the first node

 

first_node->next = NULL;

first_node->data = input_element;

first_node->prev = NULL;

 

To add a node at the position specified

 

Temp_node = *first_node;

for ( counter = 0 ; counter<position-1 ; counter++ )

{

Temp_node = Temp_node->next;

}

new_node->next = temp_node->next;

temp_node->next->new_node;

new_node->prev = temp_node->next->prev;

temp_node->next->prev = new_node;

 

Deleting a particular element from the list

 

Temp_node = *first_node;

If ( temp_node->data = = input_element )

First_node = first_node->next;

else

{

while ( temp_node != NULL && temp_node->next->data !=

input_element)

temp_node = temp_node -> next;

delete_node=temp_node->next;

temp_node->next=delete_node->next;

delete_node->next->prev=temp_node;

free(delete_node);

}

 

What is Circular Linked Lists

By Dinesh Thakur

In a circularly-linked list, the first and final nodes are linked together. In another words, circularlylinked lists can be seen as having no beginning or end. To traverse a circular linked list, begin at any node and follow the list in either direction until you return to the original node.

This type of list is most useful in cases where you have one object in a list and wish to see all other objects in the list. The pointer pointing to the whole list is usually called the end pointer.

What is Singly-circularly-linked list

By Dinesh Thakur

In a singly-circularly-linked list, each node has one link, similar to an ordinary singly-linked list, except that the link of the last node points back to the first node. As in a singly-linked list, new nodes can only be efficiently inserted after a node we already have a reference to.

 

For this reason, it’s usual to retain a reference to only the last element in a singly-circularly-linked list, as this allows quick insertion at the beginning, and also allows access to the first node through the last node’s next pointer. The following figure shows a singly circularly linked list.

                      Node Structure

 

What is Doubly-circularly-linked list

By Dinesh Thakur

In a doubly-circularly-linked list, each node has two links, similar to a doubly-linked list, except that the previous link of the first node points to the last node and the next link of the last node points to the first node. As in doubly-linked lists, insertions and removals can be done at any point with access to any nearby node.

 

 

Double Circularly linked list

 

Circularly-linked list vs. linearly-linked list

By Dinesh Thakur

Circularly linked lists are useful to traverse an entire list starting at any point. In a linear linked list, it is required to know the head pointer to traverse the entire list. The linear linked list cannot be traversed completely with the help of an intermediate pointer.

 

Access to any element in a doubly circularly linked list is much easier than in a linearly linked list since the particular element can be approached in two directions. For example to access an element present in the fourth node of a circularly linked list having five elements, it is enough to start from the last node and traverse the list in the reverse direction to get the value in the fourth node.

 

Implementation of a circular linked list:

 

Creating the list

 

while (input_element != -999)

{

new_node=(struct node *) malloc (size);

new_node->info=input_element;

if ( root_node==NULL )

root_node=new_node;

else

( *last_node )->next=new_node;

(*last_node)=new_node;

scanf(“%d”,&input_element);

}

if(root!=NULL)

new->next=root;

return root;

 

Inserting elements into the list

 

After getting the position and value to be inserted, the following code can be followed:

 

new_node=(struct node *)malloc(sizeof(struct node));

new_node-> info=input_element;

 

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

{

new_node->next =*root_node;

*root_node = new_node;

if((*last_node)!=NULL)

(*last_node)->next=*root_node;

else

*last_node=*start_node;

}

else

{

temp_node=*root_node;

counter=2;

while ( (counter<position) && (temp_node->next !=

(*root_node) ) )

{

temp_node=temp_node->next;

++counter;

}

if(temp_node->next==(*root_node))

*last_node=new_node;

new_node->next=temp_node->next;

temp_node->next=new_node;

}

 

Deleting an element from the list

 

After getting the element to be deleted, the following code can be used:

 

If(*front_node != NULL)

{

printf(“The item deleted is %d”,(*front_node->info));

If (*front_node == *rear_node)

{

*front_node = *rear_node = NULL;

}

else

{

*front_node = *front_node->next;

*rear_node->link = *front_node;

}

}

Primary Sidebar

Data Structure

Data Structure Tutorials

  • DS - Home
  • DS - Sorting
  • DS - Shortest Path Algorithm
  • DS - free() Function
  • DS - Graph Traversals
  • DS - Linear Search
  • DS - Heap Sort
  • DS - Searching
  • DS - Linked Lists
  • DS - Algorithms
  • DS - Bubble Sort
  • DS - Quick Sort
  • DS - Binary Search
  • DS - realloc() Vs free()
  • DS - Steps to Plan Algorithm
  • DS - Record Structure
  • DS - Single Linked List
  • DS - Purpose of realloc()
  • DS - Use malloc()
  • DS - calloc() Vs malloc()

Other Links

  • Data Structure - PDF Version

Footer

Basic Course

  • Computer Fundamental
  • Computer Networking
  • Operating System
  • Database System
  • Computer Graphics
  • Management System
  • Software Engineering
  • Digital Electronics
  • Electronic Commerce
  • Compiler Design
  • Troubleshooting

Programming

  • Java Programming
  • Structured Query (SQL)
  • C Programming
  • C++ Programming
  • Visual Basic
  • Data Structures
  • Struts 2
  • Java Servlet
  • C# Programming
  • Basic Terms
  • Interviews

World Wide Web

  • Internet
  • Java Script
  • HTML Language
  • Cascading Style Sheet
  • Java Server Pages
  • Wordpress
  • PHP
  • Python Tutorial
  • AngularJS
  • Troubleshooting

 About Us |  Contact Us |  FAQ

Dinesh Thakur is a Technology Columinist and founder of Computer Notes.

Copyright © 2025. All Rights Reserved.

APPLY FOR ONLINE JOB IN BIGGEST CRYPTO COMPANIES
APPLY NOW