Linked List - Introduction and Insertion

Introduction:
    Linked list is a linear data structure. It consists of nodes. Each node has data and pointer to the next node. Linked list is represented by it's head pointer.


 Representation of a node:


 class Node
{
      int data;
      //reference to the next node
      Node next;

       //constructor to initialize the node
      Node(int data){
          this.data = data;
          next = null;
      }
}

Insertion :

 (i) insertion at the head of the linked list:

 Steps:
1) Create a node with given data.
2) Make the next of the node to point to head , so that we are preserving the pointer to next node.
3) Make the head to point to new node.

 Code:

 void Insert(Node head,int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

 Illustration:

Insertion of 1 at the head of the list 2->3->4
    


(ii) Insertion of a node after a given node:

Steps:
1) Create a new node with given data.
2) Make the next of the new node to point to present node's next.
3) Make the next of the present node to point to new node.

 Code:

 void insert(Node presentNode, int data){
     Node newNode = new Node(data);
     newNode.next = presentNode.next;
     presentNode.next = newNode;
}

 Illustration:

 Insert 2 after 3 in the list 1->3->4


 (iii) Insertion of a node at the end:

 Steps:
1) Traverse the list till you reach the last node. ( a last node is one whose next pointer is null)
2) Insert new node at the next of the last node.

 Code:

 Node Insert(Node head,int data) {

    Node newNode = new Node(data);

    Node last = head;
    
    while(last.next!=null){
        last = last.next;
        
    }

     last.next = newNode;
    
    return head;

}

 Illustration:

 Insert 4 at the end of the list 1->2->3



       

       

Comments

Post a Comment

Popular posts from this blog

Tree traversals - Inorder Traversal

Image
        A binary tree can be traversed in two ways. i) Depth First Traversal: Inorder, preorder, postorder ii) Breadth First Traversal: Level Order Traversal Inorder traversal:        In inorder traversal root is visited in between left and right subtree traversals. Steps: 1.  Traverse the left subtree 2.  Visit the root 3. Traverse the right subtree Note: If binary search tree is traversed in inorder, the numbers will be sorted in ascending order. Code: void inOrder(Node root) { if(root==null) return; inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } Illustration: Inorder traversal of given tree is 3, 5, 4, 7, 8  Consider the left subtree of 7 (since 7 is the root ,we always start our traversal from root) Here we start form 5, the left subtree of 5 is 3. For 3 the left subtree is empty , So we visit the root. The right subtree of tree is also empty. At ...
Read more

Binary Search tree (Insertion)

Image
   A tree in which every node can have a maximum of two children is called a binary tree.       A binary search tree is a binary tree in which every node has lower values in the left sub tree and higher values in the right sub tree. Node of binary tree: class Node{      int data;      Node left, right;      Node(int data){         this.data = data;         right = left = null;      } } BST - Insertion:  static Node Insert(Node root,int data) {      if( root == null ){            root = new Node(data);            return root;      }      if( data < root.data)             root.left = Insert(root.left,data);      else             root.right = Insert(root.rig...
Read more

Stack implementation using array

Image
    Introduction:    Stack is a linear data structure which follows LIFO( Last In First Out ) order.   To represent stack consider books are placed in table for the teacher to correct. The note which is submitted last will be corrected first. The person who submits last is quite unlucky isn't it :P Operations: push: Inserts element at the top of the stack pop: Removes element from the top of the stack Stack implementation using array: Code: import java.util.*; import java.lang.*; import java.io.*; class Stack {     int SIZE = 10;     int arr[] = new int[SIZE];     int top = -1;          public int pop(){         if (top == -1){             System.out.println("stack is empty");             return 0;         }         int topelement ...
Read more