Question

In: Computer Science

In JAVA: Create a circular doubly linked list. It need not be generic. Implement addToStart and...

In JAVA:

Create a circular doubly linked list. It need not be generic. Implement addToStart and addToEnd methods, as well as printList method. Implement delete(Node n) method that deletes a node n, if n is in the linked list. Make no assumptions about n. Test your linked list.

Solutions

Expert Solution

/*

This program will create a circular doubly linked list.

Intially the list is empty and user need to add elements to create the list

For that the program provided with 4 options as below :

1. insert at start
2. insert at end
3. delete at position(node)
4. print list

You need to select 1 or 2 options to add elements first and then you can perform operation 3 an 4 .

The program will also print list after every operation perform to see the output

*/


import java.util.Scanner;
      
   /* Class Node */
   class Node
   {
        protected int data;
        protected Node next, prev;
  
        /* Constructor */
        public Node()
        {
            next = null;
            prev = null;
            data = 0;
        }
        /* Constructor */
        public Node(int d, Node n, Node p)
        {
            data = d;
            next = n;
            prev = p;
        }
        /* Function to set link to next node */
        public void setLinkNext(Node n)
        {
            next = n;
        }
        /* Function to set link to previous node */
        public void setLinkPrev(Node p)
        {
            prev = p;
        }  
        /* Funtion to get link to next node */
        public Node getLinkNext()
        {
            return next;
        }
        /* Function to get link to previous node */
        public Node getLinkPrev()
        {
            return prev;
        }
        /* Function to set data to node */
        public void setData(int d)
        {
            data = d;
        }
        /* Function to get data from 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 element at begining */
        public void addToStart(int val)
        {
            Node nptr = new Node(val, null, null);  
            if (start == null)
            {          
                nptr.setLinkNext(nptr);
                nptr.setLinkPrev(nptr);
                start = nptr;
                end = start;          
            }
            else
            {
                nptr.setLinkPrev(end);
                end.setLinkNext(nptr);
                start.setLinkPrev(nptr);
                nptr.setLinkNext(start);
                start = nptr;      
            }
            size++ ;
        }
        /*Function to insert element at end */
        public void addToEnd(int val)
        {
            Node nptr = new Node(val, null, null);      
            if (start == null)
            {
                nptr.setLinkNext(nptr);
                nptr.setLinkPrev(nptr);
                start = nptr;
                end = start;
            }
            else
            {
                nptr.setLinkPrev(end);
                end.setLinkNext(nptr);
                start.setLinkPrev(nptr);
                nptr.setLinkNext(start);
                end = nptr;  
            }
            size++;
        }

        /* Function to delete node at position */
        public void deleteNode(int node)
        {      
            if (node == 1)
            {
                if (size == 1)
                {
                    start = null;
                    end = null;
                    size = 0;
                    return;
                }
                start = start.getLinkNext();
                start.setLinkPrev(end);
                end.setLinkNext(start);
                size--;
                return ;
            }
            if (node == size)
            {
                end = end.getLinkPrev();
                end.setLinkNext(start);
                start.setLinkPrev(end);
                size-- ;
            }
            Node ptr = start.getLinkNext();
            for (int i = 2; i <= size; i++)
            {
                if (i == node)
                {
                    Node p = ptr.getLinkPrev();
                    Node n = ptr.getLinkNext();
  
                    p.setLinkNext(n);
                    n.setLinkPrev(p);
                    size-- ;
                    return;
                }
                ptr = ptr.getLinkNext();
            }      
        }  
        /* Function to display status of list */
        public void display()
        {
            System.out.print("\nCircular Doubly Linked List = ");
            Node ptr = start;
            if (size == 0)
            {
                System.out.print("empty\n");
                return;
            }
            if (start.getLinkNext() == start)
            {
                System.out.print(start.getData()+ " <-> "+ptr.getData()+ "\n");
                return;
            }
            System.out.print(start.getData()+ " <-> ");
            ptr = start.getLinkNext();
            while (ptr.getLinkNext() != start)
            {
                System.out.print(ptr.getData()+ " <-> ");
                ptr = ptr.getLinkNext();
            }
            System.out.print(ptr.getData()+ " <-> ");
            ptr = ptr.getLinkNext();
            System.out.print(ptr.getData()+ "\n");
        }
   }
  
   /* Main Class to create CircularDoublyLinkedList */
   public class CircularDoublyLinkedList
   {  
        public static void main(String[] args)
        {          
            Scanner scan = new Scanner(System.in);
            /* Creating object of linkedList */
            linkedList list = new linkedList();
            System.out.println("Circular Doubly Linked List Test\n");        
            char ch;
            /* Perform list operations to add removed elements in linkedlist */
            do  
            {
               System.out.println("\nInitial List is empty ");
                System.out.println("\nPlease select below options to perform operation on Circular Doubly Linked List\n");
                System.out.println("1. insert at start");
                System.out.println("2. insert at end");
                System.out.println("3. delete at position(node)");
                System.out.println("4. print list");
  
                int choice = scan.nextInt();          
                switch (choice)
                {
                case 1 :
                    System.out.println("Enter integer element to add");
                    list.addToStart( scan.nextInt() );                   
                    break;                        
                case 2 :
                    System.out.println("Enter integer element to add");
                    list.addToEnd( scan.nextInt() );
                    break ;
                case 3 :
                    System.out.println("Enter position");
                    int p = scan.nextInt() ;
                    if (p < 1 || p > list.getSize() )
                        System.out.println("Invalid position\n");
                    else
                        list.deleteNode(p);
                    break;    
                case 4 :
                   System.out.println(list);
                   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

Circular Doubly Linked List Test


Initial List is empty

Please select below options to perform operation on Circular Doubly Linked List

1. insert at start
2. insert at end
3. delete at position(node)
4. print list
1
Enter integer element to add
22

Circular Doubly Linked List = 22 <-> 22

Do you want to continue (Type y or n)

y

Initial List is empty

Please select below options to perform operation on Circular Doubly Linked List

1. insert at start
2. insert at end
3. delete at position(node)
4. print list
2
Enter integer element to add
44

Circular Doubly Linked List = 22 <-> 44 <-> 22

Do you want to continue (Type y or n)

y

Initial List is empty

Please select below options to perform operation on Circular Doubly Linked List

1. insert at start
2. insert at end
3. delete at position(node)
4. print list
1
Enter integer element to add
3

Circular Doubly Linked List = 3 <-> 22 <-> 44 <-> 3

Do you want to continue (Type y or n)

y

Initial List is empty

Please select below options to perform operation on Circular Doubly Linked List

1. insert at start
2. insert at end
3. delete at position(node)
4. print list
3
Enter position
2

Circular Doubly Linked List = 3 <-> 44 <-> 3

Do you want to continue (Type y or n)

y

Initial List is empty

Please select below options to perform operation on Circular Doubly Linked List

1. insert at start
2. insert at end
3. delete at position(node)
4. print list
4
car.linkedList@42a57993

Circular Doubly Linked List = 3 <-> 44 <-> 3

Do you want to continue (Type y or n)

y

Initial List is empty

Please select below options to perform operation on Circular Doubly Linked List

1. insert at start
2. insert at end
3. delete at position(node)
4. print list
5
Wrong Entry

Circular Doubly Linked List = 3 <-> 44 <-> 3

Do you want to continue (Type y or n)

venereology answered 4 days ago
Next > < Previous

Related Solutions

A circular doubly-linked list .(a) In a circular doubly-linked list, there is no front or end;...
A circular doubly-linked list .(a) In a circular doubly-linked list, there is no front or end; the nodes form a full circle. Instead of keeping track of the node at the front, we keep track of a current node instead. Write a class for a circular doubly-linked list using the attached Job class as your node objects. It should have: • A private instance variable for the current node • A getCurrent() method that returns a reference to the current...
Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy...
Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy node. This challenge simulates an operating system’s window manager. Requirements Write the following struct struct Window { string appname; Window *next; Window *prev; }; Create a class called WindowManager. In this class, create a private variable Window * head. This will keep track of the location of the head node. Create private variables Window * current, * dummy. current will keep track of the...
Can you make this singular linked list to doubly linked list Create a Doubly Linked List....
Can you make this singular linked list to doubly linked list Create a Doubly Linked List. Use this to create a Sorted Linked List, Use this to create a prioritized list by use. Bring to front those links recently queried. -----link.h------ #ifndef LINK_H #define LINK_H struct Link{ int data; Link *lnkNxt; }; #endif /* LINK_H */ ----main.cpp---- //System Level Libraries #include <iostream> //I/O Library using namespace std; //Libraries compiled under std #include"Link.h" //Global Constants - Science/Math Related //Conversions, Higher Dimensions...
Create a generic Linked List that does NOT use the Java library linked list. Make sure...
Create a generic Linked List that does NOT use the Java library linked list. Make sure it contains or access a subclass named Node (also Generic). And has the methods: addFirst(), addLast(), add(), removeFirst(), removeLast() and getHead(). In a separate Java class provide a main that creates an instance of your LinkedList class that creates an instance of your LinkedList that contains String types. Add the five names (you pick them) to the list and then iterate through the list...
Write an efficient java program to implement an integer doubly linked list Dequeue which insertion and...
Write an efficient java program to implement an integer doubly linked list Dequeue which insertion and deletion can be than at either end. You have to write 6 methods: add front, delete front, add rear, delete rear, print forward (left to right) and print backward (right to left). After each addition or deletion dequeue elements are printed forward or backward respectively. Your main method should be as follow: public static void main(String args[]) { xxxxx dq = new xxxxx ();...
Using java: Implement a basic doubly-linked list that implements a priority system sorting the elements that...
Using java: Implement a basic doubly-linked list that implements a priority system sorting the elements that are inserted. Sort based on the speed of the warrior. Driver code: public class LinkedListDriver { public static void main(String[] args) { LinkedList list = new SortedDoublyLinkedList(); System.out.println(list); Warrior krogg = new Warrior("Krogg", 30, 50, 200); list.insert(krogg); System.out.println(list); Warrior gurkh = new Warrior("Gurkh", 40, 45, 180); list.insert(gurkh); System.out.println(list); Warrior brynn = new Warrior("Brynn", 45, 40, 190); list.insert(brynn); System.out.println(list); Warrior dolf = new Warrior("Dolf", 20,...
Introduction: In this project you will create a generic linked list using Java Generics. Description: Create...
Introduction: In this project you will create a generic linked list using Java Generics. Description: Create a generic class called GenLinkedList. GenLinkedList will use nodes that store a value of the generic type to store its contents. It should have the following methods. The methods should all operate on the object making the call (none are static). Perform checking of the parameters and throw exceptions where appropriate. The linked list should be singly-linked. It should not use sentinel nodes (empty...
by java Implement a linked list generic queue. Remember queues are first in first out (FIFO)....
by java Implement a linked list generic queue. Remember queues are first in first out (FIFO). Use the driver to then test each of the methods. Simply download it and place it with the other source files. Create a class GenLLQueue which has the following: Internal class ListNode which contains: Instance variable data of type T Instance variable link of type ListNode Default constructor that sets both instance variables to null Instance Variables head which is of type ListNode which...
One way to implement a queue is to use a circular linked list. In a circular...
One way to implement a queue is to use a circular linked list. In a circular linked list, the last node’s next pointer points at the first node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding to a node in the list. For which of the following representations can all basic queue operations be performed in constant worst time? Justify your answers. Maintain an iterator that corresponds to the first...
In this Java program you will implement your own doubly linked lists. Implement the following operations...
In this Java program you will implement your own doubly linked lists. Implement the following operations that Java7 LinkedLists have. 1. public DList() This creates the empty list 2. public void addFirst(String element) adds the element to the front of the list 3. public void addLast(String element) adds the element to the end of the list 4. public String getFirst() 5. public String getLast() 6. public String removeLast() removes & returns the last element of the list. 7. public String...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT