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 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 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
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:Below is the transcription of a Java code snippet, which is a part of a package called `Deque`. It defines a generic class `Node<E>` with several methods and variables, showcasing basic operations typically associated with a node in a data structure like a doubly-linked list.
```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
- **Package Declaration:** `package Deque;` specifies that this class is part of the `Deque` package.
- **Class Definition:** `public class Node<E>` declares a generic class `Node` with a type parameter `E`.
- **Instance Variables:**
- `private E element;` — stores the data of the node.
- `private Node<E> next;` — reference to the next node in the structure.
- `private Node<E> prev;` — reference to the previous node in the structure.
- **Constructor:**
- `public Node(E e, Node<E> p, Node<E> n)` — initializes the node's element with `e`, the previous node with `p`, and the next node with `n`.
- **Methods:**
- `public E getElement()` — returns the element stored in the node.
- `public Node<E> getNext()` — returns the reference to the next node.
- `public Node<E> getPrev()` — returns the reference to the previous node.
- `public void setElement(E e)` — sets the element of the node.
- `public void setNext(Node<E> n)` — sets the reference to the next node.
- `public void setPrev(Node<E>
Transcribed Image Text:The image provides a Java implementation of a `LinkedDeque` class using a doubly-linked list as its underlying data structure. Below is the transcription and explanation of the code:
```java
package Deque;
public class LinkedDeque<E> implements Deque<E> {
private DLinkedList<E> list = new DLinkedList<E>();
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:
1. **Package Declaration**:
- The class is part of the `Deque` package.
2. **Class Definition**:
- `LinkedDeque<E>`: A generic class that implements the `Deque<E>` interface.
- It uses a private instance of `DLinkedList<E>`, which is a doubly-linked list to manage its elements.
3. **Constructor**:
- `LinkedDeque()`: A public constructor that initializes the deque.
4. **Methods**:
- `size()`: Returns the number of elements in the deque by calling `getSize()` of the linked list.
- `isEmpty()`: Checks if the deque is empty using `isEmpty()` of the linked list.
- `first()`: Retrieves, without removing, the first element using `getFirst()`.
- `last()`: Retrieves, without removing, the last element using `getLast()`.
- `addFirst(E element)`: Inserts an element at the front using `addFirst()`.
- `addLast(E element)`: Appends an element at the end using `addLast()`.
- `removeFirst()`: Removes and returns the first element.
- `removeLast()`: Removes and returns the last element.
This implementation provides a standard deque (double-ended queue) functionality, allowing elements to be added or removed from both ends of the data structure efficiently.
Expert Solution
Step 1: Program Approach
The code you provided looks like a complete and correct implementation of a Deque using a doubly linked list in Java. Here's the breakdown of the provided code:
The
Dequeinterface defines the methods for a double-ended queue.The
Nodeclass represents nodes in the doubly linked list. Each node has an element, a reference to the previous node (prev), and a reference to the next node (next).The
LinkedDequeclass implements theDequeinterface using a doubly linked list. It has ahead, atail, and asizeto maintain the state of the deque. The methods are implemented as follows:addFirstandaddLastadd elements to the front and back of the deque, respectively.removeFirstandremoveLastremove elements from the front and back of the deque, respectively.isEmptychecks if the deque is empty.firstandlastreturn the elements at the front and back of the deque, respectively.
The
Mainclass is used to test the functionality of theLinkedDequeclass. It creates aLinkedDequeof integers, adds elements, and removes elements to demonstrate how the deque works.
Step by step
Solved in 5 steps with 2 images
