What do you mean by linked list write an algorithm to insert a node in singly linked list?

Insertion in singly linked list at beginning

Inserting a new element into a singly linked list at beginning is quite simple. We just need to make a few adjustments in the node links. There are the following steps which need to be followed in order to inser a new node in the list at beginning.

• Allocate the space for the new node and store data into the data part of the node. This will be done by the following statements.

• Make the link part of the new node pointing to the existing first node of the list. This will be done by using the following statement.

• At the last, we need to make the new node as the first node of the list this will be done by using the following statement.

Linked List Operations: Traverse, Insert and Delete

In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.

There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

• Traversal - access each element of the linked list
• Insertion - adds a new element to the linked list
• Deletion - removes the existing elements
• Search - find a node in the linked list
• Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

• head points to the first node of the linked list
• next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

struct node { int data; struct node *next; };

---

Data Structure and Algorithms - Linked List

---

Advertisements

Previous Page

Next Page

A linked list is a sequence of data structures, which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

• Link − Each link of a linked list can store a data called an element.

• Next − Each link of a linked list contains a link to the next link called Next.

• LinkedList − A Linked List contains the connection link to the first link called First.

Linked List Data Structure

• Last Updated : 01 Feb, 2022

Practice Problems on Linked List
Recent Articles on Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Topics :

• Singly Linked List
• Circular Linked List
• Doubly Linked List

• Misc
• Quick Links

Singly Linked List :

1. Introduction to Linked List
2. Linked List vs Array
3. Linked List Insertion
4. Linked List Deletion (Deleting a given key)
5. Linked List Deletion (Deleting a key at given position)
6. Write a function to delete a Linked List
7. Find Length of a Linked List (Iterative and Recursive)
8. Search an element in a Linked List (Iterative and Recursive)
9. Write a function to get Nth node in a Linked List
10. Nth node from the end of a Linked List
11. Print the middle of a given linked list
12. Write a function that counts the number of times a given int occurs in a Linked List
13. Detect loop in a linked list
14. Find length of loop in linked list
15. Function to check if a singly linked list is palindrome
16. Remove duplicates from a sorted linked list
17. Remove duplicates from an unsorted linked list
18. Swap nodes in a linked list without swapping data
19. Pairwise swap elements of a given linked list
20. Move last element to front of a given Linked List
21. Intersection of two Sorted Linked Lists
22. Intersection point of two Linked Lists.
23. QuickSort on Singly Linked List
24. Segregate even and odd nodes in a Linked List
25. Reverse a linked list

More >>

Circular Linked List :

1. Circular Linked List Introduction and Applications,
2. Circular Linked List Traversal
3. Split a Circular Linked List into two halves
4. Sorted insert for circular linked list
5. Check if a linked list is Circular Linked List
6. Convert a Binary Tree to a Circular Doubly Link List
7. Circular Singly Linked List | Insertion
8. Deletion from a Circular Linked List
9. Circular Queue | Set 2 (Circular Linked List Implementation)
10. Count nodes in Circular linked list
11. Josephus Circle using circular linked list
12. Convert singly linked list into circular linked list
13. Circular Linked List | Set 1 (Introduction and Applications)
14. Circular Linked List | Set 2 (Traversal)
15. Implementation of Deque using circular array
16. Exchange first and last nodes in Circular Linked List

More >>

Doubly Linked List :

1. Doubly Linked List Introduction and Insertion
2. Delete a node in a Doubly Linked List
3. Reverse a Doubly Linked List
4. The Great Tree-List Recursion Problem.
5. Copy a linked list with next and arbit pointer
6. QuickSort on Doubly Linked List
7. Swap Kth node from beginning with Kth node from end in a Linked List
8. Merge Sort for Doubly Linked List
9. Create a Doubly Linked List from a Ternary Tree
10. Find pairs with given sum in doubly linked list
11. Insert value in sorted way in a sorted doubly linked list
12. Delete a Doubly Linked List node at a given position
13. Count triplets in a sorted doubly linked list whose sum is equal to a given value x
14. Remove duplicates from a sorted doubly linked list
15. Delete all occurrences of a given key in a doubly linked list
16. Remove duplicates from an unsorted doubly linked list
17. Sort the biotonic doubly linked list
18. Sort a k sorted doubly linked list
19. Convert a given Binary Tree to Doubly Linked List | Set
20. Program to find size of Doubly Linked List
21. Sorted insert in a doubly linked list with head and tail pointers
22. Large number arithmetic using doubly linked list
23. Rotate Doubly linked list by N nodes
24. Priority Queue using doubly linked list
25. Reverse a doubly linked list in groups of given size
26. Doubly Circular Linked List | Set 1 (Introduction and Insertion)
27. Doubly Circular Linked List | Set 2 (Deletion)

More >>

Misc :

1. Skip List | Set 1 (Introduction)
2. Skip List | Set 2 (Insertion)
3. Skip List | Set 3 (Searching and Deletion)
4. Reverse a stack without using extra space in O(n)
5. An interesting method to print reverse of a linked list
6. Linked List representation of Disjoint Set Data Structures
7. Sublist Search (Search a linked list in another list)
8. How to insert elements in C++ STL List ?
9. Unrolled Linked List | Set 1 (Introduction)
10. A Programmer’s approach of looking at Array vs. Linked List
11. How to write C functions that modify head pointer of a Linked List?
12. Given a linked list which is sorted, how will you insert in sorted way
13. Can we reverse a linked list in less than O(n)?
14. Practice questions for Linked List and Recursion
15. Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes
16. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
17. Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
18. Squareroot(n)-th node in a Linked List
19. Find the fractional (or n/k – th) node in linked list
20. Find modular node in a linked list
21. Construct a linked list from 2D matrix
22. Find smallest and largest elements in singly linked list
23. Arrange consonants and vowels nodes in a linked list
24. Partitioning a linked list around a given value and If we don’t care about making the elements of the list “stable”
25. Modify contents of Linked List

Quick Links :

• ‘Practice Problems’ on Linked List
• ‘Videos’ on Linked List
• ‘Quizzes’ on Linked List

If you still need more assistance with your placement preparation, have a look at our Complete Interview Preparation Course. The course has been designed by our expert mentors to help students crack the coding interview of top product or service-based organizations . You get access to premium lectures, 200+ coding questions bank, resume building tips, and lifetime access to the course content. So to make sure that your next programming interview doesn’t feel like an interrogation, enroll in Complete Interview Preparation and give a boost to your placement preparation.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Linked List | Set 2 (Inserting a node)

We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.

C++

// A linked list node class Node { public: int data; Node *next; }; // This code is contributed by rathbhupendra

C

// A linked list node struct Node { int data; struct Node *next; };

Java

// Linked List Class class LinkedList { Node head; // head of list /* Node Class */ class Node { int data; Node next; // Constructor to create a new node Node(int d) {data = d; next = null; } } }

Python

# Node class class Node: # Function to initialize the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked List class class LinkedList: # Function to initialize the Linked List object def __init__(self): self.head = None

C#

/* Linked list Node*/ public class Node { public int data; public Node next; public Node(int d) {data = d; next = null; } }

Javascript

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.

Traverse a Linked List

Accessing the nodes of a linked list in order to process it is called traversing a linked list. Normally we use the traverse operation to display the contents or to search for an element in the linked list. The algorithm for traversing a linked list is given below.

Algorithm: Traverse

Step 1: [INITIALIZE] SET PTR = HEAD Step 2: Repeat Steps 3 and 4 while PTR != NULL Step 3: Apply process to PTR -> DATA Step 4: SET PTR = PTR->NEXT [END OF LOOP] Step 5: EXIT

• We first initialize PTR with the address of HEAD. Now the PTR points to the first node of the linked list.
• A while loop is executed, and the operation is continued until PTR reaches the last node (PTR = NULL).
• Apply the process(display) to the current node.
• Move to the next node by making the value of PTR to the address of next node.

The following block of code prints all elements in a linked list in C.

struct node *ptr = head; printf("Elements in the linked list are : "); while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; }

Inserting Elements to a Linked List

We will see how a new node can be added to an existing linked list in the following cases.

1. The new node is inserted at the beginning.
2. The new node is inserted at the end.
3. The new node is inserted after a given node.

Insert a Node at the beginning of a Linked list

Consider the linked list shown in the figure. Suppose we want to create a new node with data 24 and add it as the first node of the list. The linked list will be modified as follows.

• Allocate memory for new node and initialize its DATA part to 24.
• Add the new node as the first node of the list by pointing the NEXT part of the new node to HEAD.
• Make HEAD to point to the first node of the list.

Algorithm: InsertAtBeginning

Step 1: IF AVAIL = NULL Write OVERFLOW Go to Step 7 [END OF IF] Step 2: SET NEW_NODE = AVAIL Step 3: SET AVAIL = AVAIL -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET NEW_NODE -> NEXT = HEAD Step 6: SET HEAD = NEW_NODE Step 7: EXIT

Note that the first step of the algorithm checks if there is enough memory available to create a new node. The second, and third steps allocate memory for the new node.

This algorithm can be implemented in C as follows:

struct node *new_node; new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = 24; new_node->next = head; head = new_node;

Insert a Node at the end of a Linked list

Take a look at the linked list in the figure. Suppose we want to add a new node with data 24 as the last node of the list. Then the linked list will be modified as follows.

• Allocate memory for new node and initialize its DATA part to 24.
• Traverse to last node.
• Point the NEXT part of the last node to the newly created node.
• Make the value of next part of last node to NULL.

Algorithm: InsertAtEnd

Step 1: IF AVAIL = NULL Write OVERFLOW Go to Step 10 [END OF IF] Step 2: SET NEW_NODE = AVAIL Step 3: SET AVAIL = AVAIL -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET NEW_NODE -> NEXT = NULL Step 6: SET PTR = HEAD Step 7: Repeat Step 8 while PTR -> NEXT != NULL Step 8: SET PTR = PTR -> NEXT [END OF LOOP] Step 9: SET PTR -> NEXT = NEW_NODE Step 10: EXIT

This can be implemented in C as follows,

struct node *new_node; new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = 24; new_node->next = NULL; struct node *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new_node;

Insert a Node after a given Node in a Linked list

The last case is when we want to add a new node after a given node. Suppose we want to add a new node with value 24 after the node having data 9. These changes will be done in the linked list.

• Allocate memory for new node and initialize its DATA part to 24.
• Traverse the list until the specified node is reached.
• Change NEXT pointers accordingly.

Algorithm: InsertAfterAnElement

Step 1: IF AVAIL = NULL Write OVERFLOW Go to Step 12 [END OF IF] Step 2: SET NEW_NODE = AVAIL Step 3: SET AVAIL = AVAIL -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET PTR = HEAD Step 6: SET PREPTR = PTR Step 7: Repeat Steps 8 and 9 while PREPTR -> DATA != NUM Step 8: SET PREPTR = PTR Step 9: SET PTR = PTR -> NEXT [END OF LOOP] Step 1 : PREPTR -> NEXT = NEW_NODE Step 11: SET NEW_NODE -> NEXT = PTR Step 12: EXIT

Inserting a node at the beginning of a linked list

The new node will be added at the beginning of a linked list.

Example

Assume that the linked list has elements: 20 30 40 NULL

If we insert 100, it will be added at the beginning of a linked list.

After insertion, the new linked list will be

100 20 30 40 NULL

---