Top List List

Program to insert a node at the beginning at the end and in the middle of the given linked list

Required knowledge

Basic C programming, Functions, Singly linked list, Dynamic memory allocation

Algorithm to insert node at the middle of singly Linked List

Algorithm to insert node at the middle of Singly Linked List %% Input : n position to insert data in the list Begin: createSinglyLinkedList [head] alloc [newNode] If [newNode == NULL] then write ['Unable to allocate memory.'] End if Else then read [data] newNode.data ← data temp ← head For i ← 2 to n-1 temp ← temp.next If [temp == NULL] then break End if End for If [temp != NULL] then newNode.next ← temp.next temp.next ← newNode End if End else End

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

// 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

/* Linked list Node*/

public class Node

{

public int data;

public Node next;

public Node[int d] {data = d; next = null; }

}

Javascript

// Linked List Class

var head; // head of list

/* Node Class */

class Node {

// Constructor to create a new node

constructor[d] {

this.data = d;

this.next = null;

}

// This code is contributed by todaysgaurav

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.

Insert node into the middle of the linked list

Given a linked list containing n nodes. The problem is to insert a new node with data x at the middle of the list. If n is even, then insert the new node after the [n/2]th node, else insert the new node after the [n+1]/2th node.

Examples:

Input : list: 1->2->4->5 x = 3 Output : 1->2->3->4->5 Input : list: 5->10->4->32->16 x = 41 Output : 5->10->4->41->32->16

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

Program to insert a new node at the middle of the singly linked list

Explanation

In this program, we will create a singly linked list and add a new node at the middle of the list. To accomplish this task, we will calculate the size of the list and divide it by 2 to get the mid-point of the list where the new node needs to be inserted.

Consider the above diagram; node 1 represents the head of the original list. Let node New is the new node which needs to be added at the middle of the list. First, we calculate size which in this case is 4. So, to get the mid-point, we divide it by 2 and store it in a variable count. Node current will point to head. First, we iterate through the list till current points to mid position. Define another node temp which point to node next to current. Insert the New node between current and temp.

Algorithm

Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
Create another class InsertMid which has three attributes: head, tail, and size that keep tracks of a number of nodes present in the list.
addNode[] will add a new node to the list:
1. Create a new node.
2. It first checks, whether the head is equal to null which means the list is empty.
3. If the list is empty, both head and tail will point to a newly added node.
4. If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
addInMid[] will add a new node at the middle of the list:
1. It first checks, whether the head is equal to null which means the list is empty.
2. If the list is empty, both head and tail will point to a newly added node.
3. If the list is not empty, then calculate the size of the list and divide it by 2 to get mid-point of the list.
4. Define node current that will iterate through the list till current will point to mid node.
5. Define another node temp which will point to node next to current.
6. The new node will be inserted after current and before temp such that current will point to the new node and the new node will point to temp.
display[] will display the nodes present in the list:
1. Define a node current which will initially point to the head of the list.
2. Traverse through the list till current points to null.
3. Display each node by making current to point to node next to it in each iteration.