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);*/
    }
}

الأجوبة

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

 

هل كان المحتوى مفيد؟

أسئلة مشابهة

القوائم الدراسية التي ينتمي لها السؤال

تبحث عن مدرس اونلاين؟

محتاج مساعدة باختيار المدرس الافضل؟ تواصل مع فريقنا الان لمساعدتك بتأمين افضل مدرس
ماهو التخصص الذي تبحث عنه؟
اكتب هنا...