Insert node at beginning of linked list

In this post we are discussing about that how to created a linked list node. And how append this node at beginning of the linked list. That is interesting and because that are commonly asked question for implement heap and queue data structure using of linked list.

If you are know about how to make a linked list node and also know about how to append of this node in specific position. then it will helpful to solve complex problem of linked list in very effective manner.

Implementation process

1) First step create a dynamic linked list node and assign data and next pointer field value (when Assume that there are no memory overflow problem).

2) When linked list are empty so in this situation assign the reference of this create node to head pointer of linked list.

3) When linked list are not empty then do first steps. After that this created node pointer field are assigned the address of front node of linked list. And head pointer is assigned the address of newly create node.

This third step are work on most of cases. and time complexity of this process are O(1) constant. Suppose we are inserted the following (8, 7, 6, 5, 4, 3, 2, 1) node in a sequence.

insert node at beginning of linked list

Note that last inserted node is add first position. Here given code implementation process.

/*
    C program for
    Insert linked list node at beginning of linked list
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create memory of head and tail Nodes
    struct SingleLL *sll = (struct SingleLL *)
    malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
    }
    return sll;
}
// Handles the request of adding new node at beginning of linked list
void addNode(struct SingleLL *sll, int data)
{
    // Create dynamic node
    struct LinkNode *node = (struct LinkNode *)
    malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        printf("Memory overflow to Create LinkNode\n");
        return;
    }
    else
    {
        // Set initial node value
        node->data = data;
        node->next = sll->head;
    }
    sll->head = node;
}
// Display linked list element
void display(struct LinkNode *node)
{
    if (node == NULL)
    {
        return;
    }
    struct LinkNode *temp = node;
    // iterating linked list elements
    while (temp != NULL)
    {
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
int main(int argc, char const *argv[])
{
    struct SingleLL *sll = newLinkedList();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    addNode(sll, 8);
    addNode(sll, 7);
    addNode(sll, 6);
    addNode(sll, 5);
    addNode(sll, 4);
    addNode(sll, 3);
    addNode(sll, 2);
    addNode(sll, 1);
    printf(" Linked List \n");
    display(sll->head);
    return 0;
}
C add linked list node at beginning

Output

 Linked List
 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
/*
    Java program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public SingleLL()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    public void addNode(int data)
    {
        // Create new node
        LinkNode node = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            System.out.print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        System.out.print(" NULL\n");
    }
    public static void main(String[] args)
    {
        SingleLL sll = new SingleLL();
        // Linked list
        // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
        sll.addNode(8);
        sll.addNode(7);
        sll.addNode(6);
        sll.addNode(5);
        sll.addNode(4);
        sll.addNode(3);
        sll.addNode(2);
        sll.addNode(1);
        sll.display();
    }
}

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
Java add linked list node at beginning
// Include header file
#include <iostream>
using namespace std;
/*
    C++ program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode
{
    public: int data;
    LinkNode *next;
    LinkNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
class SingleLL
{
    public: LinkNode *head;
    SingleLL()
    {
        this->head = NULL;
    }
    // Adding new node at beginning of linked list
    void addNode(int data)
    {
        // Create new node
        LinkNode *node = new LinkNode(data);
        // Connect current node to previous head
        node->next = this->head;
        this->head = node;
    }
    // Display linked list element
    void display()
    {
        if (this->head == NULL)
        {
            return;
        }
        LinkNode *temp = this->head;
        // iterating linked list elements
        while (temp != NULL)
        {
            cout << " " << temp->data << " →";
            // Visit to next node
            temp = temp->next;
        }
        cout << " NULL\n";
    }
};
int main()
{
    SingleLL *sll = new SingleLL();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll->addNode(8);
    sll->addNode(7);
    sll->addNode(6);
    sll->addNode(5);
    sll->addNode(4);
    sll->addNode(3);
    sll->addNode(2);
    sll->addNode(1);
    sll->display();
    return 0;
}

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
package main
import "fmt"
/*
    Go program for
    Insert node at beginning of linked list
*/
// Linked list node
type LinkNode struct {
    data int
    next * LinkNode
}
func getLinkNode(data int) * LinkNode {
    var me *LinkNode = &LinkNode {}
    me.data = data
    me.next = nil
    return me
}
type SingleLL struct {
    head * LinkNode
}
func getSingleLL() * SingleLL {
    var me *SingleLL = &SingleLL {}
    me.head = nil
    return me
}
// Adding new node at beginning of linked list
func(this *SingleLL) addNode(data int) {
    // Create new node
    var node * LinkNode = getLinkNode(data)
    // Connect current node to previous head
    node.next = this.head
    this.head = node
}
// Display linked list element
func(this SingleLL) display() {
    if this.head == nil {
        return
    }
    var temp * LinkNode = this.head
    // iterating linked list elements
    for (temp != nil) {
        fmt.Print(" ", temp.data, " →")
        // Visit to next node
        temp = temp.next
    }
    fmt.Print(" NULL\n")
}
func main() {
    var sll * SingleLL = getSingleLL()
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll.addNode(8)
    sll.addNode(7)
    sll.addNode(6)
    sll.addNode(5)
    sll.addNode(4)
    sll.addNode(3)
    sll.addNode(2)
    sll.addNode(1)
    sll.display()
}

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
// Include namespace system
using System;
/*
    Csharp program for
    Insert node at beginning of linked list
*/
// Linked list node
public class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public SingleLL()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    public void addNode(int data)
    {
        // Create new node
        LinkNode node = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            Console.Write(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        Console.Write(" NULL\n");
    }
    public static void Main(String[] args)
    {
        SingleLL sll = new SingleLL();
        // Linked list
        // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
        sll.addNode(8);
        sll.addNode(7);
        sll.addNode(6);
        sll.addNode(5);
        sll.addNode(4);
        sll.addNode(3);
        sll.addNode(2);
        sll.addNode(1);
        sll.display();
    }
}

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
<?php
/*
    Php program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode
{
    public $data;
    public $next;
    public  function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}
class SingleLL
{
    public $head;
    public  function __construct()
    {
        $this->head = NULL;
    }
    // Adding new node at beginning of linked list
    public  function addNode($data)
    {
        // Create new node
        $node = new LinkNode($data);
        // Connect current node to previous head
        $node->next = $this->head;
        $this->head = $node;
    }
    // Display linked list element
    public  function display()
    {
        if ($this->head == NULL)
        {
            return;
        }
        $temp = $this->head;
        // iterating linked list elements
        while ($temp != NULL)
        {
            echo(" ".$temp->data.
                " →");
            // Visit to next node
            $temp = $temp->next;
        }
        echo(" NULL\n");
    }
}

function main()
{
    $sll = new SingleLL();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    $sll->addNode(8);
    $sll->addNode(7);
    $sll->addNode(6);
    $sll->addNode(5);
    $sll->addNode(4);
    $sll->addNode(3);
    $sll->addNode(2);
    $sll->addNode(1);
    $sll->display();
}
main();

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
/*
    Node JS program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode
{
    constructor(data)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    constructor()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    addNode(data)
    {
        // Create new node
        var node = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    display()
    {
        if (this.head == null)
        {
            return;
        }
        var temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            process.stdout.write(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        process.stdout.write(" NULL\n");
    }
}

function main()
{
    var sll = new SingleLL();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll.addNode(8);
    sll.addNode(7);
    sll.addNode(6);
    sll.addNode(5);
    sll.addNode(4);
    sll.addNode(3);
    sll.addNode(2);
    sll.addNode(1);
    sll.display();
}
main();

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
#    Python 3 program for
#    Insert node at beginning of linked list

#  Linked list node
class LinkNode :
    def __init__(self, data) :
        self.data = data
        self.next = None
    

class SingleLL :
    def __init__(self) :
        self.head = None
    
    #  Adding new node at beginning of linked list
    def addNode(self, data) :
        #  Create new node
        node = LinkNode(data)
        #  Connect current node to previous head
        node.next = self.head
        self.head = node
    
    #  Display linked list element
    def display(self) :
        if (self.head == None) :
            return
        
        temp = self.head
        #  iterating linked list elements
        while (temp != None) :
            print("", temp.data ,"→", end = "")
            #  Visit to next node
            temp = temp.next
        
        print(" NULL")
    

def main() :
    sll = SingleLL()
    #  Linked list
    #  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll.addNode(8)
    sll.addNode(7)
    sll.addNode(6)
    sll.addNode(5)
    sll.addNode(4)
    sll.addNode(3)
    sll.addNode(2)
    sll.addNode(1)
    sll.display()

if __name__ == "__main__": main()

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
#    Ruby program for
#    Insert node at beginning of linked list

#  Linked list node
class LinkNode 
    # Define the accessor and reader of class LinkNode
    attr_reader :data, :next
    attr_accessor :data, :next
    def initialize(data) 
        self.data = data
        self.next = nil
    end

end

class SingleLL 
    # Define the accessor and reader of class SingleLL
    attr_reader :head
    attr_accessor :head
    def initialize() 
        self.head = nil
    end

    #  Adding new node at beginning of linked list
    def addNode(data) 
        #  Create new node
        node = LinkNode.new(data)
        #  Connect current node to previous head
        node.next = self.head
        self.head = node
    end

    #  Display linked list element
    def display() 
        if (self.head == nil) 
            return
        end

        temp = self.head
        #  iterating linked list elements
        while (temp != nil) 
            print(" ", temp.data ," →")
            #  Visit to next node
            temp = temp.next
        end

        print(" NULL\n")
    end

end

def main() 
    sll = SingleLL.new()
    #  Linked list
    #  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll.addNode(8)
    sll.addNode(7)
    sll.addNode(6)
    sll.addNode(5)
    sll.addNode(4)
    sll.addNode(3)
    sll.addNode(2)
    sll.addNode(1)
    sll.display()
end

main()

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
/*
    Scala program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode(var data: Int,
    var next: LinkNode)
{
    def this(data: Int)
    {
        this(data, null);
    }
}
class SingleLL(var head: LinkNode)
{
    def this()
    {
        this(null);
    }
    // Adding new node at beginning of linked list
    def addNode(data: Int): Unit = {
        // Create new node
        var node: LinkNode = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    def display(): Unit = {
        if (this.head == null)
        {
            return;
        }
        var temp: LinkNode = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        print(" NULL\n");
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var sll: SingleLL = new SingleLL();
        // Linked list
        // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
        sll.addNode(8);
        sll.addNode(7);
        sll.addNode(6);
        sll.addNode(5);
        sll.addNode(4);
        sll.addNode(3);
        sll.addNode(2);
        sll.addNode(1);
        sll.display();
    }
}

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
/*
    Swift 4 program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.next = nil;
    }
}
class SingleLL
{
    var head: LinkNode? ;
    init()
    {
        self.head = nil;
    }
    // Adding new node at beginning of linked list
    func addNode(_ data: Int)
    {
        // Create new node
        let node: LinkNode = LinkNode(data);
        // Connect current node to previous head
        node.next = self.head;
        self.head = node;
    }
    // Display linked list element
    func display()
    {
        if (self.head == nil)
        {
            return;
        }
        var temp: LinkNode? = self.head;
        // iterating linked list elements
        while (temp  != nil)
        {
            print("", temp!.data ,"→", terminator: "");
            // Visit to next node
            temp = temp!.next;
        }
        print(" NULL");
    }
}
func main()
{
    let sll: SingleLL = SingleLL();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll.addNode(8);
    sll.addNode(7);
    sll.addNode(6);
    sll.addNode(5);
    sll.addNode(4);
    sll.addNode(3);
    sll.addNode(2);
    sll.addNode(1);
    sll.display();
}
main();

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
/*
    Kotlin program for
    Insert node at beginning of linked list
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    var head: LinkNode ? ;
    constructor()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    fun addNode(data: Int): Unit
    {
        // Create new node
        val node: LinkNode = LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    fun display(): Unit
    {
        if (this.head == null)
        {
            return;
        }
        var temp: LinkNode ? = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        print(" NULL\n");
    }
}
fun main(args: Array < String > ): Unit
{
    val sll: SingleLL = SingleLL();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    sll.addNode(8);
    sll.addNode(7);
    sll.addNode(6);
    sll.addNode(5);
    sll.addNode(4);
    sll.addNode(3);
    sll.addNode(2);
    sll.addNode(1);
    sll.display();
}

Output

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Time complexity of this program is O(1). When include new node firstly set new node pointer field is to head pointer. Firstly head linked list pointer is null, so newly create first node next pointer is also null. That is very useful to checking the end of linked list. After that include other node in similar manner.

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved