Mumbai University > Computer Engineering > Sem 3 > Data Structures

Marks: 10M

Years: Dec 2015

Linked List as an ADT:

• A linked list is a chain of nodes where each node in the list consists of two fields, a data field and a next address field.

• The data field holds the actual element on the list where the next address field contains the address of next node in the list. Hence, the next address field is simply a reference to the next node.

• The entire linked list is accessed from the reference variable first that points to the first node in the list.

• The next address field of the last node in the list contains a special value known as null, which is not a valid address. The value null is used to signal end of the list.

• The list with no nodes is called as empty list or null list. In such cases, the value of pointer first=null. Moreover, a linked list is initialized to empty list by the operation first=null.

• A linked list is a dynamic data structure. The number of nodes in the list may vary as elements are inserted or removed.

• Just like a stack or queue, a linked list in itself is a data structure. The data field of each node stores the actual information we can apply several operations on the list. Some of the most common operations include insertion of nodes, deletion of nodes, list traversal etc.

Function for deletion of a node from Doubly linked list:

  import java.io.*;
    class Node
    {
        public in data;
        public Node next, prev; 
        public Node(int x)
        {
            data=x;
            next=null;
            prev=null;
        }
    }
    Class DLL
    {
        private Node first,last;
        public DLL()
        {
            first=last=null;
        }
        public void insertFirst(int x)
        {
            Node ptr=new Node(x);
            if (ptr=null)
            {
                System.out.println("Memory overflow. Unable to create.");
                return;
            }
            first=last=ptr;
        }
        public void insertAfter(int x, int k)
        {
            Node p;
            Node ptr=new Node(x);
            if(ptr==null)
            {
                System.out.println("Memory overflow. Unable to create.");
                return;
            }
            p=first;
            while(p!=null)
            {
                if(p.data==k)
                    break;
                p=p.next;
            }
            if(p==null)
                System.out.println("Required Node not found.");
            else
            {
                if(p==last)
                {
                    ptr.next=null;
                    ptr.prev=last;
                    last.next=ptr;
                    last=ptr;
                }
                else
                {
                    ptr.next=p.next;
                    ptr.prev=p;
                    p.next.prev=ptr;
                    p.next=ptr;
                }
            }
        }
        public void insertBefore(int x, int k)
        {
            if(p==null)
                System.out.println("Required Node not found.");
            else
            {
                if(p==first)
                {
                    ptr.prev=null;
                    ptr.next=first;
                    first.prev=ptr;
                    first=ptr;
                }
                else
                {
                    ptr.prev=p.prev;
                    ptr.next=p;
                    p.prev.next=ptr;
                    p.prev=ptr;
                }
            }
        }
        public void deleteNode
        {
            Node p;
            p=first;
            while(p!=null)
            {
                if(p.data==k)
                    break;
                p=p.next;
            }
            if(p==null)
                System.out.println("Required Node not found.");
            else
            {
                if(p==first && p==last)
                    first=last=null;
                else if(p=first)
                {
                    first=first.next;
                    first.prev=null;
                }
                else if(p==last)
                {
                    last=last.prev;
                    last.next=null;
                }
                else
                {
                    p.prev.next=p.next;
                    p.next.prev=p.prev;
                }
                first=last=null;
            }
        }
    }
    class DLLMain
    {
        public static void main(String args[]) throws IOException
        {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int x, ch;
            DLL d=new DLL();
            do
            {
                System.out.println("Menu:");
                System.out.println("1.Insert first");
                System.out.println("2.Insert After");
                System.out.println("3.Insert Before");
                System.out.println("4.Delete Node");
                System.out.println("5.Exit");
                System.out.println("Enter your choice:");
                ch=Integer.parseInt(br.readLine());
                switch(ch)
                {
                    case 1:
                    System.out.println("Enter the data value of very first node:");
                    x=Integer.parseInt(br.readLine());
                    d.insertFirst(x);
                    break;  
                    case 2:
                    System.out.println("Enter the data value of new node:");
                    x=Integer.parseInt(br.readLine());
                    System.out.println("Enter data value of that node after which the new node is to be inserted:")
                    k=Integer.parseInt(br.readLine());
                    d.insertAfter(x,k);
                    break;
                    case 3:
                    System.out.println("Enter the data value of new node:");
                    x=Integer.parseInt(br.readLine());
                    System.out.println("Enter data value of that node before which the new node is to be inserted:")
                    k=Integer.parseInt(br.readLine());
                    d.insertBefore(x,k);
                    break;
                    case 4:
                    System.out.println("Enter the data value of node to be deleted:");
                    k=Integer.parseInt(br.readLine());
                    d.deleteNode(k);
                    break;
                    case 5:
                    break;
                }
            }while(ch!=5)
        }
    }