Singly linked list assignment


Steps:

1.      Codes for singly linked list is given below

2.      Write a method insert_after_x(node head, int x, int d). It will insert a new node with data d after the node x and returns the new head. Your code should consider all cases as follows:

a.      List empty

b.      x is the first node

c.      x is the last node

d.      x is not present in the list

e.      x is somewhere inside the list in between first and last node 

general case: insert_after_x(head, -1, 9)          // insert d=9 after x=-1

3.      Write a method delete_x(node head, int x). It will delete the node x. Your code should consider all cases as follows:

a.      List empty

b.      x is the first node

c.      x is the last node

d.      x is not present in the list

e.      x is somewhere inside the list in between first and last node

f.       if more than one x, then delete the first occurrence of x only

general case: delet_x(head, -1)            // delete node x=-1

4.      Run your program for all cases of insert and delete as mentioned above. Then for all cases, give the screen shots

Given code:

package cs211.sll;

class node      // the node data type
{
    int data;
    node next;
}  

public class CS211SLL 
{
    static node insert_first(node head, int d)
    {
        node e = new node();    // create a new node and intialize
        e.next = null;
        e.data = d;
        
        e.next = head;      // insert and update head
        head = e;
        return head;
    }

    static node insert_last(node head, int d)
    {
        node e = new node();       // create a new node and intialize
        e.data = d;
        e.next = null;
        
        if (head == null)       // list empty, now only one element
        {
            head = e;
            return head;
        }
        
        node prev;      // more than one node
        prev = head;
        while(prev.next != null)
            prev = prev.next;
        prev.next = e;
        return head;
    }
    
    static node delete_first(node head)
    {
        if (head == null)       // list empty
        {
            System.out.println("List Empty");
            return head;
        }
        head = head.next;   // one or more node, move head to the next node
        return head;
    }
    
    static node delete_last_student(node head)
    {
        node e;
        e = head;
        
        if(head == null)    // special case list empty
        {
            System.out.println("List Empty");
            return head;
        }
        
        if (e.next == null) // 
        {
            head = null;
            return head;
        }
            
        while(e.next.next != null)
            e = e.next;
        e.next = null;
        return head;
    }
    
    
    static node delete_last(node head)
    {
        node e, prev;
        
        if (head == null)   //list empty
        {
            System.out.println("List Empty");
            return head;
        }
        
        if (head.next == null)  // only one node
        {
            head = null;
            return head;
        }
        
        prev = head;    // more than one node
        e = head.next;
                                // go to the last node by e
        while(e.next != null)   // and its previous node by prev
        {
            prev = e;
            e = e.next;
        }
        prev.next = e.next;
        return head;
    }
    
    static void traverse_print(node head)
    {
        node e; // create a temporary variable
        e = head;   // start frm head
        while (e != null)   //  move until null
        {
            System.out.print(e.data + " ");
            e = e.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) 
    {
        node head;      // create the list head and initialize it to null
        head = null;
        
        //create first node manually
        node e1 = new node();
        e1.data = 15;
        e1.next = null;
        head = e1;
        
        traverse_print(head);
        
        //create first node manually
        node e2 = new node();
        e2.data = 7;
        e1.next = e2;
        
        traverse_print(head);
        
        node e3 = new node();
        e3.data = -1;
        e3.next = null;
        
        e1.next = e3;
        e3.next = e2;
        
        traverse_print(head);
        
        //head = e3; // delete first node
        //traverse_print(head);
        
        //create new nodes by insert first and insert last
        head = insert_first(head, 4);
        head = insert_first(head, 9);
        
        head = insert_last(head, 19);
        traverse_print(head);
        
        head = insert_last(head, -19);
        traverse_print(head);
        
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        
        
        /*head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        */
        
        
        //head = delete_last(head);
        //traverse_print(head);
        //head = delete_last(head);
        //traverse_print(head);
        //head = delete_last(head);
        //traverse_print(head);
        //head = insert_last(head, 19);*/
    }
}

الأجوبة

ابحث عن مسائل برمجة جافا | Java programming بالانجليزي

package cs211.sll;

class node      // the node data type
{
    int data;
    node next;
}  

public class CS211SLL {
        static node insert_first(node head, int d/*the data*/)
    {
        node e = new node();    // create a new node and intialize
        //e.next = null;
        e.data = d;
        
        e.next = head;      // insert and update head
        head = e;
        return head;
    }

    static node insert_last(node head, int d)
    {   
        node e = new node();       // create a new node and intialize
        e.data = d;
        e.next = null;
        
        if (head == null)       // list empty, now only one element
        {
            head = e;
            return head;
        }
        
        node prev;      // more than one node
        prev = head;
        while(prev.next != null)
            prev = prev.next;
        
        prev.next = e;
        return head;
    }
    
    static node delete_first(node head)
    {
        if (head == null)       // list empty
        {
            System.out.println("List Empty");
            return head;
        }
        head = head.next;   // one or more node, move head to the next node
        return head;
    }
    
    static node delete_last_student(node head)
    {
        node e;
        e = head;
        
        if(head == null)    // special case list empty
        {
            System.out.println("List Empty");
            return head;
        }
        
        if (e.next == null) // 
        {
            head = null;
            return head;
        }
            
        while(e.next.next != null)
            e = e.next;
        e.next = null;
        return head;
    }
    
    
    static node delete_last(node head)
    {
        node e, prev;
        
        if (head == null)   //list empty
        {
            System.out.println("List Empty");
            return head;
        }
        
        if (head.next == null)  // only one node
        {
            head = null;
            return head;
        }
        
        prev = head;    // more than one node
        e = head.next;
                                // go to the last node by e
        while(e.next != null)   // and its previous node by prev
        {
            prev = e;
            e = e.next;
        }
        prev.next = e.next;
        return head;
    }
    
    static void traverse_print(node head)
    {
        node e; // create a temporary variable
        e = head;   // start frm head
        while (e != null)   //  move until null
        {
            System.out.print(e.data + " ");
            e = e.next;
        }
        System.out.println();
    }

    static node insert_after_x(node head, int x, int d)//It will insert a new node with data d after the node x and returns the new head
    {   
        node e = new node();       // create a new node and intialize
        e.data = d;
        e.next = null;
        
        if (head == null)       // list empty, now only one element
        {
            System.out.println("linekedlist is empty!");
            return head;
        }
        
        node prev;      // more than one node
        prev = head;
        boolean found_x=false;
        while(prev != null)
        {
            if(prev.data==x)
            {
                e.next=prev.next;
                prev.next=e;
                found_x=true;
                break;
            }
            prev = prev.next;
        }
        if(found_x==false)
            System.out.println("node with value: "+x+" is not exists!");
        return head;
    }
    
    static node delete_x(node head, int x)//It will delete the node x
    {
        node e, prev;
        
        if (head == null)   //list empty
        {
            System.out.println("List Empty");
            return head;
        }
        
        if (head.next == null)  // only one node
        {
            if(head.data==x)
            head = null;
            return head;
        }
        
        prev = head;    // more than one node
        e = head.next;
                                // go to the last node by e
        while(e != null)   // and its previous node by prev
        {
            if(e.data==x)
            {
                prev.next=e.next;//removing the node e from linkedlist
                return head;
            }
            prev = e;
            e = e.next;
        }
        System.out.println("node with data:"+x+" is not exists !");
        return head;
    }
        
    public static void main(String[] args) 
    {
        node head;      // create the list head and initialize it to null
        head = null;
             
         //create first node manually
        node e1 = new node();
        e1.data = 3;
        e1.next = null;
        head = e1;
        
        insert_after_x(head, 3 , 10);
        insert_after_x(head, 10 , 2);
        insert_after_x(head, 10 , 5); 
        insert_after_x(head, 5 , 10); 
        
        System.out.println("----------------------------");
        System.out.println("linked list before deleting:");
        traverse_print(head);//to print linkedlist contents
        
        head=delete_x(head, 10);
        
        System.out.println("----------------------------");
        System.out.println("linked list after deleting:");
        traverse_print(head);//to print linkedlist contents
        
         /*
        insert_after_x(head, 3 , 10);
        insert_after_x(head, 10 , 2); //case: x is the last node
        insert_after_x(head, 5 , 9); //Case: x is not present in the list
        insert_after_x(head, 10 , 5); //Case: x is somewhere inside the list in between first and last node
        System.out.println("----------------------------");
        System.out.println("linked list after inserting:");
        traverse_print(head);//to print linkedlist contents
        */
        
        
        //create first node manually
        /*node e1 = new node();
        e1.data = 15;
        e1.next = null;
        head = e1;
        */
        
        
        
        
       /* traverse_print(head);
        
        //create first node manually
        node e2 = new node();
        e2.data = 7;
        e1.next = e2;
        
        traverse_print(head);
        
        node e3 = new node();
        e3.data = -1;
        e3.next = null;
        
        e1.next = e3;
        e3.next = e2;
        
        traverse_print(head);
        
        //head = e3; // delete first node
        //traverse_print(head);
        
        //create new nodes by insert first and insert last
        head = insert_first(head, 4);
        head = insert_first(head, 9);
        
        head = insert_last(head, 19);
        traverse_print(head);
        
        head = insert_last(head, -19);
        traverse_print(head);
        
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        head = delete_last_student(head);
        traverse_print(head);
        */
        
        /*head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        traverse_print(head);
        head = delete_first(head);
        */
        
        
        //head = delete_last(head);
        //traverse_print(head);
        //head = delete_last(head);
        //traverse_print(head);
        //head = delete_last(head);
        //traverse_print(head);
        //head = insert_last(head, 19);*/
    }
}

Case list is empty-method insert_after_x:

 

Case: x is the first node – method insert_after_x

 

أسئلة مشابهة

محتاج مساعدة؟ تواصل مع مدرس اونلاين الان!