Use a Doubly Linked List to implement a Deque a. Define a Deque interface. b. Define a LinkedDeque class (Node class).. c. Define a Test class to test all methods help me make test class first code package Deque; public class DLinkedList { private Node header = null; private Node trailer = null; private int size = 0; public DLinkedList() { header = new Node<>(null, null,null); trailer = new Node<>(null,header,null); header.setNext(trailer); size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size ==0; } public E getFirst(){ if(isEmpty()) { return null; } return header.getNext().getElement(); } public E getLast(){ if(isEmpty()) { return null; } return trailer.getPrev().getElement(); } public void addFirst(E e) { addBetween(e,header,header.getNext()); } public void addLast(E e) { addBetween(e,trailer.getPrev(), trailer); } public E removeFirst() { if (isEmpty()) { return null; } return remove(header.getNext( )); } public E removeLast() { if(isEmpty()) { return null; } return remove(trailer.getPrev()); } private void addBetween (E e, Node predecessor, Node successor) { Nodenewest = new Node<>(e , predecessor, successor); predecessor.setNext(newest); successor.setPrev(newest); size++; } private E remove(Node node) { Node predecessor = node.getPrev( ); Node successor = node.getNext( ); predecessor.setNext(successor); successor.setPrev(predecessor); size--; return node.getElement( ); } } secound code package Deque; public interface Deque { int size( ); boolean isEmpty( ); E first( ); E last( ); void addFirst(E e); void addLast(E e); E removeFirst( ); E removeLast( ); }
Use a Doubly Linked List to implement a Deque a. Define a Deque interface. b. Define a LinkedDeque class (Node class).. c. Define a Test class to test all methods help me make test class first code package Deque; public class DLinkedList { private Node header = null; private Node trailer = null; private int size = 0; public DLinkedList() { header = new Node<>(null, null,null); trailer = new Node<>(null,header,null); header.setNext(trailer); size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size ==0; } public E getFirst(){ if(isEmpty()) { return null; } return header.getNext().getElement(); } public E getLast(){ if(isEmpty()) { return null; } return trailer.getPrev().getElement(); } public void addFirst(E e) { addBetween(e,header,header.getNext()); } public void addLast(E e) { addBetween(e,trailer.getPrev(), trailer); } public E removeFirst() { if (isEmpty()) { return null; } return remove(header.getNext( )); } public E removeLast() { if(isEmpty()) { return null; } return remove(trailer.getPrev()); } private void addBetween (E e, Node predecessor, Node successor) { Nodenewest = new Node<>(e , predecessor, successor); predecessor.setNext(newest); successor.setPrev(newest); size++; } private E remove(Node node) { Node predecessor = node.getPrev( ); Node successor = node.getNext( ); predecessor.setNext(successor); successor.setPrev(predecessor); size--; return node.getElement( ); } } secound code package Deque; public interface Deque { int size( ); boolean isEmpty( ); E first( ); E last( ); void addFirst(E e); void addLast(E e); E removeFirst( ); E removeLast( ); }
Related questions
Question
Use a Doubly Linked List to implement a Deque
a. Define a Deque interface.
b. Define a LinkedDeque class (Node class)..
c. Define a Test class to test all methods
a. Define a Deque interface.
b. Define a LinkedDeque class (Node class)..
c. Define a Test class to test all methods
help me make test class
first code
package Deque;
public class DLinkedList<E> {
private Node<E> header = null;
private Node<E> trailer = null;
private int size = 0;
public DLinkedList() {
header = new Node<>(null, null,null);
trailer = new Node<>(null,header,null);
header.setNext(trailer);
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size ==0;
}
public E getFirst(){
if(isEmpty()) {
return null;
}
return header.getNext().getElement();
}
public E getLast(){
if(isEmpty()) {
return null;
}
return trailer.getPrev().getElement();
}
public void addFirst(E e) {
addBetween(e,header,header.getNext());
}
public void addLast(E e) {
addBetween(e,trailer.getPrev(), trailer);
}
public E removeFirst() {
if (isEmpty()) {
return null;
}
return remove(header.getNext( ));
}
public E removeLast() {
if(isEmpty()) {
return null;
}
return remove(trailer.getPrev());
}
private void addBetween (E e, Node<E> predecessor, Node<E> successor) {
Node<E>newest = new Node<>(e , predecessor, successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
}
private E remove(Node<E> node) {
Node<E> predecessor = node.getPrev( );
Node<E> successor = node.getNext( );
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return node.getElement( );
}
}
secound code
package Deque;
public interface Deque<E> {
int size( );
boolean isEmpty( );
E first( );
E last( );
void addFirst(E e);
void addLast(E e);
E removeFirst( );
E removeLast( );
}
Transcribed Image Text:The image contains a Java class implementation for a doubly linked deque. Here is a transcription of the code:
```java
package Deque;
public class LinkedDeque<E> implements Deque<E> {
private DLinkedList<E> list = new DLinkedList<>();
public LinkedDeque() {}
public int size() {
return list.getSize();
}
public boolean isEmpty() {
return list.isEmpty();
}
public E first() {
return list.getFirst();
}
public E last() {
return list.getLast();
}
public void addFirst(E element) {
list.addFirst(element);
}
public void addLast(E element) {
list.addLast(element);
}
public E removeFirst() {
return list.removeFirst();
}
public E removeLast() {
return list.removeLast();
}
}
```
### Explanation
- **Package Declaration**: The code belongs to the `Deque` package.
- **Class Declaration**: `LinkedDeque<E>` is a generic class implementing the `Deque<E>` interface.
- **Instance Variable**: Contains a private instance of `DLinkedList<E>` named `list`.
- **Constructor**: A default constructor `LinkedDeque()` which initializes the deque.
- **Methods**:
- `size()`: Returns the size of the deque by calling `list.getSize()`.
- `isEmpty()`: Checks if the deque is empty using `list.isEmpty()`.
- `first()`: Returns the first element using `list.getFirst()`.
- `last()`: Returns the last element using `list.getLast()`.
- `addFirst(E element)`: Adds an element to the front using `list.addFirst(element)`.
- `addLast(E element)`: Adds an element to the back using `list.addLast(element)`.
- `removeFirst()`: Removes and returns the first element using `list.removeFirst()`.
- `removeLast()`: Removes and returns the last element using `list.removeLast()`.
There are no graphs or diagrams in this image.
Transcribed Image Text:```java
package Deque;
public class Node<E> {
private E element;
private Node<E> next;
private Node<E> prev;
public Node(E e, Node<E> p, Node<E> n) {
element = e;
prev = p;
next = n;
}
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
public void setElement(E e) {
element = e;
}
public void setNext(Node<E> n) {
next = n;
}
public void setPrev(Node<E> p) {
prev = p;
}
}
```
**Explanation:**
This code defines a generic `Node` class that is used in a doubly linked list structure in Java. It handles any type of element through Java Generics (`<E>`).
1. **Attributes:**
- `element`: Stores the value of the node.
- `next`: Points to the next node in the list.
- `prev`: Points to the previous node in the list.
2. **Constructor:**
- Initializes a node with an element, a previous node, and a next node.
3. **Methods:**
- `getElement()`: Returns the value stored in the node.
- `getNext()`: Returns the next node.
- `getPrev()`: Returns the previous node.
- `setElement(E e)`: Updates the element stored in the node.
- `setNext(Node<E> n)`: Updates the reference to the next node.
- `setPrev(Node<E> p)`: Updates the reference to the previous node.
This class is useful for implementing data structures like deques, where elements can be added or removed from both ends.
Expert Solution
Step 1: Deque
A deque, short for "double-ended queue," is a data structure that allows you to insert and remove elements from both ends with O(1) time complexity. It combines the features of both stacks (where elements are added and removed from one end) and queues (where elements are added at one end and removed from the other end).
In a deque, you can perform the following operations:
1. `addFirst(E e)`: Adds an element to the front of the deque.
2. `addLast(E e)`: Adds an element to the back of the deque.
3. `removeFirst()`: Removes and returns the element at the front of the deque.
4. `removeLast()`: Removes and returns the element at the back of the deque.
5. `first()`: Returns the element at the front of the deque without removing it.
6. `last()`: Returns the element at the back of the deque without removing it.
7. `size()`: Returns the number of elements in the deque.
8. `isEmpty()`: Checks if the deque is empty.
Deques are useful in various situations where you need efficient access to elements at both ends of a collection, such as implementing algorithms involving sliding windows, reversing elements, or managing tasks with different priorities.
Step by step
Solved in 3 steps with 1 images
