Q1) To class SinglyList, add method removeBeforeLast() which removes the node be
ID: 3698863 • Letter: Q
Question
Q1) To class SinglyList, add method removeBeforeLast() which removes the node before the last node, consider all possible cases.
Q2) To class DoublyLinkedList, add method reverse which reverse the order of the elements in the list.
Q3) Our implementation of a doubly list relies on two sentinel nodes, header and trailer. Re-implement the DoublyLinkedList without using these nodes.
class SinglyList:
public class SinglyLinkedList<E>{
public static class Node<E>{
private E element;
private Node<E> next;
public Node(E e, Node<E> n){
element = e;
next = n;
}
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
}
private Node<E> head = null;
private Node<E> tail = null;
private int size = 0;
public SinglyLinkedList(){
}
public int size() {
return size;
}
public boolean isEmpty(){
return size ==0;
}
public E first(){
if(isEmpty())
return null;
return head.getElement();
}
public E last(){
if (isEmpty())
return null;
return tail.getElement();
}
}
class DoublyLinkedList:
public class DoublyLinkedList<E> {
public static class Node<E>{
private E element;
private Node<E> prev;
private Node<E> next;
public Node(E e, Node<E> p, Node<E> n){
element = e;
prev = p;
next = n;
}
public E getElement() {
return element;
}
public Node<E> getPrev() {
return prev;
}
public Node<E> getNext() {
return next;
}
public void setPrev(Node<E> p) {
next = p;
}
public void setNext(Node<E> n) {
next = n;
}
}
private Node<E> header;
private Node<E> trailer;
private int size = 0;
public DoublyLinkedList(){
header = new Node<>(null,null,null);
trailer = new Node<>(null, header, null);
header.setNext(trailer);
}
public int size(){
return size;
}
public boolean isEmpty(){
return size ==0;
}
public E first(){
if(isEmpty())
return null;
return header.getNext().getElement();
}
public E last(){
if(isEmpty())
return null;
return trailer.getPrev().getElement();
}
}
Explanation / Answer
Please find my code for Q1.
Please repost others in separate post.
public class SinglyLinkedList<E>{
public static class Node<E>{
private E element;
private Node<E> next;
public Node(E e, Node<E> n){
element = e;
next = n;
}
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
}
private Node<E> head = null;
private Node<E> tail = null;
private int size = 0;
public SinglyLinkedList(){
}
public int size() {
return size;
}
public boolean isEmpty(){
return size ==0;
}
public E first(){
if(isEmpty())
return null;
return head.getElement();
}
public E last(){
if (isEmpty())
return null;
return tail.getElement();
}
public void removeBeforeLast() {
// ignore if list is empty or only one elment is there
if(head == null || head.next == null)
return;
// if two element in the list
if(head.next == tail) {
head = head.next;
}
Node<E> t = head;
while(t.next.next != tail) {
t = t.next;
}
t.next = tail; // removing before last
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.