TUTORIAL PLATFORM: Linked List

In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references.
A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
A CODE FOR LINKED LIST
/***************************************************************************
 * A Linked List class with a private static inner Node class.
 *
 *****************************************************************************/







import java.util.Scanner;

 

/*  Class Node  */

class Node

{

    protected int data;

    protected Node link;

 

    /*  Constructor  */

    public Node()

    {

        link = null;

        data = 0;

    }    

    /*  Constructor  */

    public Node(int d,Node n)

    {

        data = d;

        link = n;

    }    

    /*  Function to set link to next Node  */

    public void setLink(Node n)

    {

        link = n;

    }    

    /*  Function to set data to current Node  */

    public void setData(int d)

    {

        data = d;

    }    

    /*  Function to get link to next node  */

    public Node getLink()

    {

        return link;

    }    

    /*  Function to get data from current Node  */

    public int getData()

    {

        return data;

    }

}

 

/* Class linkedList */

class linkedList

{

    protected Node start;

    protected Node end ;

    public int size ;

 

    /*  Constructor  */

    public linkedList()

    {

        start = null;

        end = null;

        size = 0;

    }

    /*  Function to check if list is empty  */

    public boolean isEmpty()

    {

        return start == null;

    }

    /*  Function to get size of list  */

    public int getSize()

    {

        return size;

    }    

    /*  Function to insert an element at begining  */

    public void insertAtStart(int val)

    {

        Node nptr = new Node(val, null);    

        size++ ;    

        if(start == null) 

        {

            start = nptr;

            end = start;

        }

        else 

        {

            nptr.setLink(start);

            start = nptr;

        }

    }

    /*  Function to insert an element at end  */

    public void insertAtEnd(int val)

    {

        Node nptr = new Node(val,null);    

        size++ ;    

        if(start == null) 

        {

            start = nptr;

            end = start;

        }

        else 

        {

            end.setLink(nptr);

            end = nptr;

        }

    }

    /*  Function to insert an element at position  */

    public void insertAtPos(int val , int pos)

    {

        Node nptr = new Node(val, null);                

        Node ptr = start;

        pos = pos - 1 ;

        for (int i = 1; i < size; i++) 

        {

            if (i == pos) 

            {

                Node tmp = ptr.getLink() ;

                ptr.setLink(nptr);

                nptr.setLink(tmp);

                break;

            }

            ptr = ptr.getLink();

        }

        size++ ;

    }

    /*  Function to delete an element at position  */

    public void deleteAtPos(int pos)

    {        

        if (pos == 1) 

        {

            start = start.getLink();

            size--; 

            return ;

        }

        if (pos == size) 

        {

            Node s = start;

            Node t = start;

            while (s != end)

            {

                t = s;

                s = s.getLink();

            }

            end = t;

            end.setLink(null);

            size --;

            return;

        }

        Node ptr = start;

        pos = pos - 1 ;

        for (int i = 1; i < size - 1; i++) 

        {

            if (i == pos) 

            {

                Node tmp = ptr.getLink();

                tmp = tmp.getLink();

                ptr.setLink(tmp);

                break;

            }

            ptr = ptr.getLink();

        }

        size-- ;

    }    

    /*  Function to display elements  */

    public void display()

    {

        System.out.print("\nSingly Linked List = ");

        if (size == 0) 

        {

            System.out.print("empty\n");

            return;

        }    

        if (start.getLink() == null) 

        {

            System.out.println(start.getData() );

            return;

        }

        Node ptr = start;

        System.out.print(start.getData()+ "->");

        ptr = start.getLink();

        while (ptr.getLink() != null)

        {

            System.out.print(ptr.getData()+ "->");

            ptr = ptr.getLink();

        }

        System.out.print(ptr.getData()+ "\n");

    }

}

 

/*  Class SinglyLinkedList  */

public class SinglyLinkedList

{    

    public static void main(String[] args)

    {             

        Scanner scan = new Scanner(System.in);

        /* Creating object of class linkedList */

        linkedList list = new linkedList(); 

        System.out.println("Singly Linked List Test\n");          

        char ch;

        /*  Perform list operations  */

        do

        {

            System.out.println("\nSingly Linked List Operations\n");

            System.out.println("1. insert at begining");

            System.out.println("2. insert at end");

            System.out.println("3. insert at position");

            System.out.println("4. delete at position");

            System.out.println("5. check empty");

            System.out.println("6. get size");            

            int choice = scan.nextInt();            

            switch (choice)

            {

            case 1 : 

                System.out.println("Enter integer element to insert");

                list.insertAtStart( scan.nextInt() );                     

                break;                          

            case 2 : 

                System.out.println("Enter integer element to insert");

                list.insertAtEnd( scan.nextInt() );                     

                break;                         

            case 3 : 

                System.out.println("Enter integer element to insert");

                int num = scan.nextInt() ;

                System.out.println("Enter position");

                int pos = scan.nextInt() ;

                if (pos <= 1 || pos > list.getSize() )

                    System.out.println("Invalid position\n");

                else

                    list.insertAtPos(num, pos);

                break;                                          

            case 4 : 

                System.out.println("Enter position");

                int p = scan.nextInt() ;

                if (p < 1 || p > list.getSize() )

                    System.out.println("Invalid position\n");

                else

                    list.deleteAtPos(p);

                break;

            case 5 : 

                System.out.println("Empty status = "+ list.isEmpty());

                break;                   

            case 6 : 

                System.out.println("Size = "+ list.getSize() +" \n");

                break;                         

             default : 

                System.out.println("Wrong Entry \n ");

                break;   

            }

            /*  Display List  */ 

            list.display();

            System.out.println("\nDo you want to continue (Type y or n) \n");

            ch = scan.next().charAt(0);                        

        } while (ch == 'Y'|| ch == 'y');               

    }

}


















OUTPUT
Singly Linked List Test
 
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
5
Empty status = true
 
Singly Linked List = empty
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
1
Enter integer element to insert
5
 
Singly Linked List = 5
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
1
Enter integer element to insert
7
 
Singly Linked List = 7->5
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
2
Enter integer element to insert
4
 
Singly Linked List = 7->5->4
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
2
Enter integer element to insert
2
 
Singly Linked List = 7->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
1
Enter integer element to insert
9
 
Singly Linked List = 9->7->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
3
Enter integer element to insert
3
Enter position
3
 
Singly Linked List = 9->7->3->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
3
Enter integer element to insert
2
Enter position
2
 
Singly Linked List = 9->2->7->3->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
6
Size = 7
 
 
Singly Linked List = 9->2->7->3->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
4
 
Singly Linked List = 9->2->7->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
2
 
Singly Linked List = 9->7->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
1
 
Singly Linked List = 7->5->4->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
3
 
Singly Linked List = 7->5->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
1
 
Singly Linked List = 5->2
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
2
 
Singly Linked List = 5
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
4
Enter position
1
 
Singly Linked List = empty
 
Do you want to continue (Type y or n)
 
y
 
Singly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
5
Empty status = true
 
Singly Linked List = empty
 
Do you want to continue (Type y or n)
 
n
Bitcoin

Linked List

No comments:

Post a Comment

Facebook

Popular Posts
