Singly Linked List

 Single Linked List : In Single link list each node will have 2 parts , first part will have Data while next part will have a pointer which will keep the address of its next node, while node itself will not be aware of anything apart from its next node address.

Below is sample program without Tail. In this program appending an element to link list will have time complexity as O(n) as we need to travers till end of the link list to find out the last element in link list.

But if we will use Tail node along with Head then time complexity for adding an element will be O(n) but still insertion of a node after a specific node will be O(n).

Sample program without Tail node.

import java.io.IOException;
import java.util.Scanner;

class Node {

    Node next = null;
    int data;

    public Node(int val) {
        data = val;
    }
}

class LinkList {

    Node head = null;

    public void append(int val) {
        if (head == null) {
            head = new Node(val);
        } else {
            Node n = head;
            while (n.next != null) {
                n = n.next;
            }
            n.next = new Node(val);
        }
    }

    public void display(Node node) {
        while (node != null) {
            System.out.print(node.data+"  ");
            node = node.next;
        }
    }
}

public class LinkListImpl {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        LinkList linkList = new LinkList();

        while (true) {

            int choice = sc.nextInt();
            switch (choice) {
                case 1:
                    System.out.println("Eneter a element to add in link list");
                    int in = sc.nextInt();
                    linkList.append(in);
                    break;
                case 2:
                    linkList.display(linkList.head);
                    break;

                case 3:
                    System.out.println("BYE BYE");
                    System.exit(0);
                default:
                    System.out.println("Wrong input : please focus here");

            }
        }

    }

}

When we will have tail node then adding new element is very simple, just check if this is first node or not if this is first node then head and tail node will be same for first element, if not then just add new node to Tail next link part and move tail node from current node to newly added node.

Node head = null;
Node tail= null;

public void append(int val) {
    if (head == null) {
        head = new Node(val);
        tail=head;
    } else {
        tail.next = new Node(val);
        tail=tail.next;
    }
}

Compete Singly linked list Program :

import java.io.IOException;
import java.util.Scanner;

class Node2 {

    Node next = null;
    int data;

    public Node2(int val) {
        data = val;
    }
}

class LinkList2 {

    Node head = null;
    Node tail= null;

    public void append(int val) {
        if (head == null) {
            head = new Node(val);
            tail=head;
        } else {
            tail.next = new Node(val);
            tail=tail.next;
        }
    }

    public void delete(int val){

        if(head.data==val){
            head=null;
            tail=null;
        }
        Node temp=head.next;
        while(temp.next.data!=val){
            temp=temp.next;
        }
        temp.next=temp.next.next;


    }

    public void appendAfterNode(int searchVal, int val) {

        if (head == null) {
            head = new Node(val);
            tail = head;
        }
        Node temp =head;
        while(temp.data!=searchVal) {
            temp=temp.next;
        }
        Node temp2=temp.next;
        temp.next = new Node(val);
        temp.next.next=temp2;

    }
    public void display(Node node) {
        while (node != null) {
            System.out.print(node.data+"  ");
            node = node.next;
        }
    }
}

public class LinkListImplWithTail {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        LinkList2 linkList = new LinkList2();

        while (true) {

            int choice = sc.nextInt();
            switch (choice) {
                case 1:
                    System.out.println("Eneter a element to add in link list");
                    int in = sc.nextInt();
                    linkList.append(in);
                    break;
                case 2:
                    linkList.display(linkList.head);
                    break;
                case 3:
                    System.out.println("Eneter 2 element to add in link list after specific node");
                    int in2 = sc.nextInt();
                    int in3 = sc.nextInt();
                    linkList.appendAfterNode(in2,in3);
                    break;
                case 4:
                    System.out.println("Eneter a element to delete from link list");
                    int in4=sc.nextInt();
                    linkList.delete(in4);
                    break;

                case 5:
                    System.out.println("BYE BYE");
                    System.exit(0);
                default:
                    System.out.println("Wrong input : please focus here");

            }
        }

    }

}