That's where the toList method comes in. When called, this method returns a List representation of the Deque]. For example, if the Deque] has had addLast (5), called on it, then the result of addLast (9) addLast (10), then addFirst (3) 9 toList() should be a List with 3 at the front, then 5, then 9, then 10. If printed in Java, it'd show up as [3, 5, 9, 10]. Write the toList method. The first line of the method should be something like List returnList = new ArrayList<>()]. This is one location where you are allowed to use a Java data structure.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
You may have found it somewhat tedious and unpleasant to use the debugger and
visualizer to verify the correctness of your addFirst and addLast methods. There is
also the problem that such manual verification becomes stale as soon as you change your
code. Imagine that you made some minor but uncertain change to addLast]. To verify that
you didn't break anything you'd have to go back and do that whole process again. Yuck.
What we really want are some automated tests. But unfortunately there's no easy way to
verify correctness of addFirst and addLast] if those are the only two methods we've
implemented. That is, there's currently no way to iterate over our list and get bad its
values and see that they are correct.
That's where the toList method comes in. When called, this method returns a List
representation of the Deque. For example, if the Deque has had addLast (5)
addLast (9) addLast (10), then addFirst (3) called on it, then the result of
toList() should be a List with 3 at the front, then 5, then 9, then 10. If printed in
Java, it'd show up as [3, 5, 9, 10]
J
Write the toList method. The first line of the method should be something like
List<T> returnList = new ArrayList<>(). This is one location where you are
allowed to use a Java data structure.
Transcribed Image Text:You may have found it somewhat tedious and unpleasant to use the debugger and visualizer to verify the correctness of your addFirst and addLast methods. There is also the problem that such manual verification becomes stale as soon as you change your code. Imagine that you made some minor but uncertain change to addLast]. To verify that you didn't break anything you'd have to go back and do that whole process again. Yuck. What we really want are some automated tests. But unfortunately there's no easy way to verify correctness of addFirst and addLast] if those are the only two methods we've implemented. That is, there's currently no way to iterate over our list and get bad its values and see that they are correct. That's where the toList method comes in. When called, this method returns a List representation of the Deque. For example, if the Deque has had addLast (5) addLast (9) addLast (10), then addFirst (3) called on it, then the result of toList() should be a List with 3 at the front, then 5, then 9, then 10. If printed in Java, it'd show up as [3, 5, 9, 10] J Write the toList method. The first line of the method should be something like List<T> returnList = new ArrayList<>(). This is one location where you are allowed to use a Java data structure.
5 usages new.
@Override
public void addFirst (T x) {
ListNode newNode = new ListNode(v: 'x', sentinel, sentinel.next);
sentinel.next.prev= newNode;
sentinel.next = newNode;
size++;
}
6 usages new
@Override
public void addLast (T x) {
ListNode newNode = new ListNode(v: 'x', sentinel.prev, sentinel);
}
sentinel.prev.next = newNode;
sentinel.prev= newNode;
}
size++;
5 usages new
@Override
public List<T> toList() {
List<T> returnList = new ArrayList<>();
I
Transcribed Image Text:5 usages new. @Override public void addFirst (T x) { ListNode newNode = new ListNode(v: 'x', sentinel, sentinel.next); sentinel.next.prev= newNode; sentinel.next = newNode; size++; } 6 usages new @Override public void addLast (T x) { ListNode newNode = new ListNode(v: 'x', sentinel.prev, sentinel); } sentinel.prev.next = newNode; sentinel.prev= newNode; } size++; 5 usages new @Override public List<T> toList() { List<T> returnList = new ArrayList<>(); I
Expert Solution
Step 1 : Code (Explained with comment)

Copy function's internal part

 

import java.util.List;
import java.util.ArrayList;

public class Deque<T> {
    class ListNode<T> {
        T v;
        ListNode<T> next;
        ListNode<T> prev;

        ListNode(T v) {
            this.v = v;
        }

        ListNode(T v, ListNode<T> next, ListNode<T> prev) {
            this.v = v;
            this.next = next;
            this.prev = prev;
        }
    }

    int size;
    ListNode<T> sentinel;

    Deque() {
        sentinel = new ListNode<T>(null);
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
        size = 0;
    }

    public void addFirst(T x) {
        ListNode<T> newNode = new ListNode<T>(x, sentinel.next, sentinel);
        sentinel.next.prev = newNode;
        sentinel.next = newNode;
        size++;
    }

    public void addLast(T x) {
        ListNode<T> newNode = new ListNode<T>(x, sentinel, sentinel.prev);
        sentinel.prev.next = newNode;
        sentinel.prev = newNode;
        size++;
    }

    public List<T> toList() {
        // COPY CODE FROM HERE------------------------------
        List<T> returnList = new ArrayList<>();
        ListNode<T> p = sentinel.next; // sentinel.next is the first node
        while (p != sentinel) { // sentinel is the last node
            returnList.add(returnList.size(), p.v); // add to the end of the list
            p = p.next; // move to the next node
        }
        return returnList; // return the list
        // TO HERE-------------------------------------------
    }

    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<Integer>();
        deque.addLast(5);
        deque.addLast(9);
        deque.addLast(10);
        deque.addFirst(3);
        System.out.println(deque.toList());
    }
}
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 2 images

Blurred answer
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education