To append a node to a list means to

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.

Table of Contents Show

Linked List | Set 2 (Inserting a node)
Append the last M nodes to the beginning of the given linked list.
Singly Linked List : Inserting, Appending and Freeing nodes.
inserting a node at the end of a 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

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

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.

Append the last M nodes to the beginning of the given linked list.

Given a linked list and an integer M, the task is to append the last M nodes of the linked list to the front.
Examples:

Input: List = 4 -> 5 -> 6 -> 1 -> 2 -> 3 -> NULL, M = 3
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Input: List = 8 -> 7 -> 0 -> 4 -> 1 -> NULL, M = 2
Output: 4 -> 1 -> 8 -> 7 -> 0 -> NULL

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Find the first node of the last M nodes in the list, this node will be the new head node so make the next pointer of the previous node as NULL and point the last node of the original list to the head of the original list. Finally, print the updated list.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>

using namespace std;
// Class for a node of
// the linked list

struct Node {

// Data and the pointer

// to the next node

int data;

Node* next;

Node(int data)

{

this->data = data;

this->next = NULL;

}
};
// Function to print the linked list

void printList(Node* node)
{

while (node != NULL) {

cout << (node->data) << " -> ";

node = node->next;

}

cout << "NULL";
}
// Recursive function to return the
// count of nodes in the linked list

int cntNodes(Node* node)
{

if (node == NULL)

return 0;

return (1 + cntNodes(node->next));
}
// Function to update and print
// the updated list nodes

void updateList(Node* head, int m)
{

// Total nodes in the list

int cnt = cntNodes(head);

if (cnt != m && m < cnt) {

// Count of nodes to be skipped

// from the beginning

int skip = cnt - m;

Node* prev = NULL;

Node* curr = head;

// Skip the nodes

while (skip > 0) {

prev = curr;

curr = curr->next;

skip--;

}

// Change the pointers

prev->next = NULL;

Node* tempHead = head;

head = curr;

// Find the last node

while (curr->next != NULL)

curr = curr->next;

// Connect it to the head

// of the sub list

curr->next = tempHead;

}

// Print the updated list

printList(head);
}
// Driver code

int main()
{

// Create the list

Node* head = new Node(4);

head->next = new Node(5);

head->next->next = new Node(6);

head->next->next->next = new Node(1);

head->next->next->next->next = new Node(2);

head->next->next->next->next->next = new Node(3);

int m = 3;

updateList(head, m);

return 0;
}
// This code is contributed by rutvik_56

Java

// Java implementation of the approach

class GFG {

// Class for a node of

// the linked list

static class Node {

// Data and the pointer

// to the next node

int data;

Node next;

Node(int data)

{

this.data = data;

this.next = null;

}

}

// Function to print the linked list

static void printList(Node node)

{

while (node != null) {

System.out.print(node.data + " -> ");

node = node.next;

}

System.out.print("NULL");

}

// Recursive function to return the

// count of nodes in the linked list

static int cntNodes(Node node)

{

if (node == null)

return 0;

return (1 + cntNodes(node.next));

}

// Function to update and print

// the updated list nodes

static void updateList(Node head, int m)

{

// Total nodes in the list

int cnt = cntNodes(head);

if (cnt != m && m < cnt) {

// Count of nodes to be skipped

// from the beginning

int skip = cnt - m;

Node prev = null;

Node curr = head;

// Skip the nodes

while (skip > 0) {

prev = curr;

curr = curr.next;

skip--;

}

// Change the pointers

prev.next = null;

Node tempHead = head;

head = curr;

// Find the last node

while (curr.next != null)

curr = curr.next;

// Connect it to the head

// of the sub list

curr.next = tempHead;

}

// Print the updated list

printList(head);

}

// Driver code

public static void main(String[] args)

{

// Create the list

Node head = new Node(4);

head.next = new Node(5);

head.next.next = new Node(6);

head.next.next.next = new Node(1);

head.next.next.next.next = new Node(2);

head.next.next.next.next.next = new Node(3);

int m = 3;

updateList(head, m);

}
}

Python3

# Python3 implementation of the approach
# Class for a node of
# the linked list

class newNode:

# Constructor to initialize the node object

def __init__(self, data):

self.data = data

self.next = None
# Function to print the linked list

def printList(node):

while (node != None):

print(node.data, "->", end=" ")

node = node.next

print("NULL")
# Recursive function to return the
# count of nodes in the linked list

def cntNodes(node):

if (node == None):

return 0

return (1 + cntNodes(node.next))
# Function to update and print
# the updated list nodes

def updateList(head, m):

# Total nodes in the list

cnt = cntNodes(head)

if (cnt != m and m < cnt):

# Count of nodes to be skipped

# from the beginning

skip = cnt - m

prev = None

curr = head

# Skip the nodes

while (skip > 0):

prev = curr

curr = curr.next

skip -= 1

# Change the pointers

prev.next = None

tempHead = head

head = curr

# Find the last node

while (curr.next != None):

curr = curr.next

# Connect it to the head

# of the sub list

curr.next = tempHead

# Print the updated list

printList(head)
# Driver code
# Create the list

head = newNode(4)

head.next = newNode(5)

head.next.next = newNode(6)

head.next.next.next = newNode(1)

head.next.next.next.next = newNode(2)

head.next.next.next.next.next = newNode(3)

m = 3
updateList(head, m)
# This code is contributed by shubhamsingh20

// C# implementation of the approach

using System;

class GFG {

// Class for a node of

// the linked list

class Node {

// Data and the pointer

// to the next node

public int data;

public Node next;

public Node(int data)

{

this.data = data;

this.next = null;

}

}

// Function to print the linked list

static void printList(Node node)

{

while (node != null) {

Console.Write(node.data + " -> ");

node = node.next;

}

Console.Write("NULL");

}

// Recursive function to return the

// count of nodes in the linked list

static int cntNodes(Node node)

{

if (node == null)

return 0;

return (1 + cntNodes(node.next));

}

// Function to update and print

// the updated list nodes

static void updateList(Node head, int m)

{

// Total nodes in the list

int cnt = cntNodes(head);

if (cnt != m && m < cnt) {

// Count of nodes to be skipped

// from the beginning

int skip = cnt - m;

Node prev = null;

Node curr = head;

// Skip the nodes

while (skip > 0) {

prev = curr;

curr = curr.next;

skip--;

}

// Change the pointers

prev.next = null;

Node tempHead = head;

head = curr;

// Find the last node

while (curr.next != null)

curr = curr.next;

// Connect it to the head

// of the sub list

curr.next = tempHead;

}

// Print the updated list

printList(head);

}

// Driver code

public static void Main(String[] args)

{

// Create the list

Node head = new Node(4);

head.next = new Node(5);

head.next.next = new Node(6);

head.next.next.next = new Node(1);

head.next.next.next.next = new Node(2);

head.next.next.next.next.next = new Node(3);

int m = 3;

updateList(head, m);

}
}
// This code is contributed by PrinciRaj1992

Javascript

<script>

// JavaScript implementation of the approach

// Class for a node of

// the linked list

class Node {

// Data and the pointer

// to the next node

constructor(data) {

this.data = data;

this.next = null;

}

}

// Function to print the linked list

function printList(node) {

while (node != null) {

document.write(node.data + " -> ");

node = node.next;

}

document.write("NULL");

}

// Recursive function to return the

// count of nodes in the linked list

function cntNodes(node) {

if (node == null) return 0;

return 1 + cntNodes(node.next);

}

// Function to update and print

// the updated list nodes

function updateList(head, m) {

// Total nodes in the list

var cnt = cntNodes(head);

if (cnt != m && m < cnt) {

// Count of nodes to be skipped

// from the beginning

var skip = cnt - m;

var prev = null;

var curr = head;

// Skip the nodes

while (skip > 0) {

prev = curr;

curr = curr.next;

skip--;

}

// Change the pointers

prev.next = null;

var tempHead = head;

head = curr;

// Find the last node

while (curr.next != null) curr = curr.next;

// Connect it to the head

// of the sub list

curr.next = tempHead;

}

// Print the updated list

printList(head);

}

// Driver code

// Create the list

var head = new Node(4);

head.next = new Node(5);

head.next.next = new Node(6);

head.next.next.next = new Node(1);

head.next.next.next.next = new Node(2);

head.next.next.next.next.next = new Node(3);

var m = 3;

updateList(head, m);

// This code is contributed by rdtank.

</script>

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

METHOD 2:

We Will use modififcation of runner’s technique :-

1. find the kth node from end using runner technique and do the following modifications

2. now we have to update our pointers as

a) fast->next will be pointing to head,

b)slow->next will be new head,

c)last node will be the slow->next hence it should point to null

C++

#include <iostream>

using namespace std;

struct node {

int data;

node* next;

node(int x)

{

data = x;

next = NULL;

}
};

void insertAtTail(node*& head, int x)
{

if (head == NULL) {

head = new node(x);

return;

}

node* curr = head;

while (curr->next != NULL) {

curr = curr->next;

}

node* t = new node(x);

curr->next = t;
}

void print(node* head)
{

node* curr = head;

while (curr != NULL) {

cout << curr->data << " -> ";

curr = curr->next;

}

cout << "NULL\n";
}

node* appendK(node* head, int k)
{

node* fast = head;

node* slow = head;

for (int i = 0; i < k; i++) {

fast = fast->next;

}

while (fast->next != NULL) {

slow = slow->next;

fast = fast->next;

}

// cout<<"data"<<" "<<slow->data<<" "<<fast->data<<endl;

fast->next = head;

head = slow->next;

slow->next = NULL;

return head;
}

int main()
{

node* head = NULL;

int n;

n = 6 ;

insertAtTail(head, 4);

insertAtTail(head, 5);

insertAtTail(head, 6);

insertAtTail(head, 1);

insertAtTail(head, 2);

insertAtTail(head, 3);

int k;

k = 3 ;

head = appendK(head, k % n);

print(head);

return 0;
}

Output 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Article Tags :

Data Structures

Linked List

Practice Tags :

Data Structures

Linked List

Read Full Article

Singly Linked List : Inserting, Appending and Freeing nodes.

Insert Operation

To insert into a singly-linked list, we need to know the node after which we need to insert a new_node.
1. Traverse the linked list and store the location of the node ( into current_node ) after which a new_node is to be inserted.
2. If the current_node is not Null then
Create a new_node that is to be inserted.
Store the location of the node that is next to the current_node i.e ( next_node = current . next )
Update the next link of the current_node by pointing it to the new_node.
Point the new_node’s next link to next_node.

Append Operation
To append to a singly-linked list, 1. Traverse the linked list till the end. Store the location of the last node into current_node. Create a new_node to be appended. Update the next link of the current_node by pointing it to the new_node.
Below is the example of an insert and append operation

Free Operation
To free the singly linked list, we start from the head node and do the below While the HEAD node of the singly linked list is not NULL. a) Store the node next to HEAD in a temporary node. b) Delete the HEAD node. c) Point the HEAD to the temporary node.

Time complexity for inserting a node : O ( N ), as the linked list has be to traversed to find the node after which a new node is to be inserted.
Time complexity for appending a node : O ( N ), as the linked list has be to traversed to reach the last node after which a new node is to be inserted.
Time complexity for freeing the linked list : O ( N ), as every node of the linked list has be to traversed before it is deleted.

Space complexity : O ( N ). N is the number of nodes in the linked list.

C++ program for inserting, appending and freeing the nodes of a singly linked list.

#include<iostream> using namespace std; class Node { public: int data; Node* next; Node (int arg_data) : data (arg_data), next (nullptr) {} }; class SingleLinkedList { public: SingleLinkedList() {} // Insert a new node into the single linked list after the first found node. void Insert (Node* head, int data, int after) { Node* current = head; // Traverse the link list till the node a node is found after // which the data is to be insert while (current->data != after) { current = current->next; } if (current != nullptr) { Node * new_node = new Node(data); // Save the location of node after current in next_node link Node * next_node = current->next; // Point current's link to the new node to be inserted. current->next = new_node; // Point new node's link to the next node location previously stored. new_node->next = next_node; } } // Append a node to the singly linked list void Append (Node* head, int data) { Node* current = head; while (current->next != nullptr) { current = current->next; } Node* new_node = new Node(data); current->next = new_node; } void Display (Node* head) { Node* current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } } // Free the linked list void Free (Node *head) { while (head != nullptr) { Node * temp = head->next; head->next = nullptr; delete head; head = temp; } } }; int main() { Node *head = new Node(2); Node *node_3 = new Node(3); Node *node_5 = new Node(5); Node *node_7 = new Node(7); Node *node_13 = new Node(13); head->next = node_3; node_3->next = node_5; node_5->next = node_7; node_7->next = node_13; SingleLinkedList s; int data, after, opt = 0; while (opt != 3) { cout << "\n\nOptions" << endl; cout << "1. Insert" << endl; cout << "2. Append" << endl; cout << "3. Exit" << endl; cout << "Enter Option : "; cin >> opt; switch (opt) { case 1: cout << "Linked list "; s.Display(head); cout << "\nEnter new node (data) : "; cin >> data; cout << "After node : "; cin >> after; s.Insert(head, data, after); s.Display(head); break; case 2: cout << "Linked list "; s.Display(head); cout << "\nEnter new node (data) : "; cin >> data; s.Append(head, data); s.Display(head); break; case 3: cout << "Freeing the linked list." << endl; s.Free(head); break; } } return 0; }

Output

Options 1. Insert 2. Append 3. Exit Enter Option : 1 Linked list 2 3 5 7 13 Enter new node (data) : 8 After node : 7 2 3 5 7 8 13 Options 1. Insert 2. Append 3. Exit Enter Option : 1 Linked list 2 3 5 7 8 13 Enter new node (data) : 20 After node : 8 2 3 5 7 8 20 13 Options 1. Insert 2. Append 3. Exit Enter Option : 2 Linked list 2 3 5 7 8 20 13 Enter new node (data) : 40 2 3 5 7 8 20 13 40 Options 1. Insert 2. Append 3. Exit Enter Option : 2 Linked list 2 3 5 7 8 20 13 40 Enter new node (data) : 100 2 3 5 7 8 20 13 40 100 Options 1. Insert 2. Append 3. Exit Enter Option : 3 Freeing the linked list.