Question

Q1; Write a method in class SLL called public SLL reverse() that produces a new linked...

Q1;

  1. Write a method in class SLL called public SLL reverse() that produces a new linked list with the contents of the original list reversed. Make sure not to use any methods like addToHead() or addToTail(). In addition, consider any special cases that might arise.

  1. What is the big-O complexity of your method in terms of the list size n

Supplementary Exercise for Programming (Coding)

  1. [Singly Linked Lists] Download and unpack (unzip) the file SinglyLinkedList.rar. Compile and execute the class LinkedListApplication.java. Use this file structure for completing Exercise 2.

public class LinkedListApplication {
   public static void main(String[] args) {
       SLL myList = new SLL();
       for(int i = 0; i < 5; i++)
           myList.addToHead("A" + i);
          
       myList.printAll();
   }
}

--------------------------------------------------------------------------------------------------------------------------------------------------------------

//************************ SLLNode.java *******************************
// node in a generic singly linked list class

public class SLLNode {
public T info;
public SLLNode next;
public SLLNode() {
this(null,null);
}
public SLLNode(T el) {
this(el,null);
}
public SLLNode(T el, SLLNode ptr) {
info = el; next = ptr;
}
}

------------------------------------------------------------------------------------------------------------------------------------------------

//************************** SLL.java *********************************
// a generic singly linked list class

public class SLL {
protected SLLNode head, tail;
public SLL() {
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
public void addToHead(T el) {
head = new SLLNode(el,head);
if (tail == null)
tail = head;
}
public void addToTail(T el) {
if (!isEmpty()) {
tail.next = new SLLNode(el);
tail = tail.next;
}
else head = tail = new SLLNode(el);
}
public T deleteFromHead() { // delete the head and return its info;
if (isEmpty())
return null;
T el = head.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else head = head.next;
return el;
}
public T deleteFromTail() { // delete the tail and return its info;
if (isEmpty())
return null;
T el = tail.info;
if (head == tail) // if only one node in the list;
head = tail = null;
else { // if more than one node in the list,
SLLNode tmp; // find the predecessor of tail;
for (tmp = head; tmp.next != tail; tmp = tmp.next);
tail = tmp; // the predecessor of tail becomes tail;
tail.next = null;
}
return el;
}
public void delete(T el) { // delete the node with an element el;
if (!isEmpty())
if (head == tail && el.equals(head.info)) // if only one
head = tail = null; // node on the list;
else if (el.equals(head.info)) // if more than one node on the list;
head = head.next; // and el is in the head node;
else { // if more than one node in the list
SLLNode pred, tmp;// and el is in a nonhead node;
for (pred = head, tmp = head.next;
tmp != null && !tmp.info.equals(el);
pred = pred.next, tmp = tmp.next);
if (tmp != null) { // if el was found;
pred.next = tmp.next;
if (tmp == tail) // if el is in the last node;
tail = pred;
}
}
}
public void printAll() {
for (SLLNode tmp = head; tmp != null; tmp = tmp.next)
System.out.print(tmp.info + " ");
}
public boolean isInList(T el) {
SLLNode tmp;
for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next);
return tmp != null;
}
}

  1. [Doubly Linked Lists] Download and unpack (unzip) the file DoublyLinkedList.rar. Compile and execute the class DLLTest.java.

public class DLLTest {
   public static void main(String[] args) {
       DLL test = new DLL();
       for(int i = 0; i < 5; i++)
           test.addToTail("a" + i);
       test.printAll();
   }
}

//**************************** DLLNode.java *******************************
// node of generic doubly linked list class

public class DLLNode {
public T info;
public DLLNode next, prev;
public DLLNode() {
next = null; prev = null;
}
public DLLNode(T el) {
info = el; next = null; prev = null;
}
public DLLNode(T el, DLLNode n, DLLNode p) {
info = el; next = n; prev = p;
}
}

//**************************** DLL.java *******************************
// generic doubly linked list class

public class DLL<T> {
private DLLNode<T> head, tail;
public DLL() {
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
public void setToNull() {
head = tail = null;
}
public T firstEl() {
if (head != null)
return head.info;
else return null;
}
public void addToHead(T el) {
if (head != null) {
head = new DLLNode<T>(el,head,null);
head.next.prev = head;
}
else head = tail = new DLLNode<T>(el);
}
public void addToTail(T el) {
if (tail != null) {
tail = new DLLNode<T>(el,null,tail);
tail.prev.next = tail;
}
else head = tail = new DLLNode<T>(el);
}
public T deleteFromHead() {
if (isEmpty())
return null;
T el = head.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else { // if more than one node in the list;
head = head.next;
head.prev = null;
}
return el;
}
public T deleteFromTail() {
if (isEmpty())
return null;
T el = tail.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else { // if more than one node in the list;
tail = tail.prev;
tail.next = null;
}
return el;
}
public void printAll() {
for (DLLNode<T> tmp = head; tmp != null; tmp = tmp.next)
System.out.print(tmp.info + " ");
}
public T find(T el) {
DLLNode<T> tmp;
for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next);
if (tmp == null)
return null;
else return tmp.info;
}
}

Homework Answers

Answer #1
public SLL reverse() {
        SLLNode prevHead = head;
        
        head = reverse(head);
        tail = prevHead;
        return this;
}

private SLLNode reverse(SLLNode start) {
        if (start == null)
                return null;

        SLLNode current = start;
        SLLNode prev = null;
        SLLNode next = null;

        while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
        }

        start = prev;
        return start;
}
**************************************************
The complexity is O(N), Since we visit each node once, and just re-arrange the pointers.. Hence, it is a linear algorithm.

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
(a)   Write a method in class SLL<T> called public SLL<T> reverse() that produces a new linked...
(a)   Write a method in class SLL<T> called public SLL<T> reverse() that produces a new linked list with the contents of the original list reversed. Make sure not to use any methods like addToHead() or addToTail(). In addition, consider any special cases that might arise. (b)   What is the big-O complexity of your method in terms of the list size n. ****** //************************ SLLNode.java ******************************* //           node in a generic singly linked list class public class SLLNode<T> {     public...
public class DoublyLinkedList { Node Head; // head of Doubly Linked List //Doubly Linked list Node...
public class DoublyLinkedList { Node Head; // head of Doubly Linked List //Doubly Linked list Node class Node { int value; Node prev; Node next; // Constructor to create a new node Node(int d) { value = d; } } // Inserting a node at the front of the list public void add(int newData) { // allocate node and put in the data Node newNode = new Node(newData); // Make the next of new node as head // and previous...
Write a method in class SLL<T> called public static SLL<T> reverse() that produces a new linked...
Write a method in class SLL<T> called public static SLL<T> reverse() that produces a new linked list with the contents of the original list reversed. Make sure not to use any methods like addToHead() or addToTail(). In addition, consider any special cases that might arise. (b) What is the big-O complexity of your method in terms of the list size n.
In this code, I build a single-linked list using a node class that has been created....
In this code, I build a single-linked list using a node class that has been created. How could I change this code to take data of type T, rather than int. (PS: ignore the fact that IOHelper.getInt won't work for the type T... ie second half of main). Here's my code right now: public class SLList { public SLNode head = null; public SLNode tail = null; public void add(int a) {// add() method present for testing purposes SLNode newNode...
This is based on LinkedLists. There is a type mismatch in my first method and I...
This is based on LinkedLists. There is a type mismatch in my first method and I dont know how to get around it. I've commented on the line with the type mismatch public class Node {    public T info; public Node link; public Node(T i, Node l) {    info = i; link = l;    } } class LinkedList> {    protected Node head = null; public LinkedList add(T el) { head = new Node(el, head); return this;...
Given this definition of a generic Linked List node: public class LLNode {     private T...
Given this definition of a generic Linked List node: public class LLNode {     private T data;     private LLNode next;     public LLNode(T data, LLNode next) {           this.data = data;           this.next = next;     }     public void setNext(LLNode newNext){ next = newNext; }     public LLNode getNext(){ return next; }     public T getData() {return data;} } Write the findMinimumNode method body. This method returns the linked list node that contains the minimum value in the...
You must alter the Queue class you created in L5 to make it a CIRCULAR Queue...
You must alter the Queue class you created in L5 to make it a CIRCULAR Queue class . Call your class Queue. it must be a template class. public class Queue { } I have put a driver program in the module . It is called CircularQueue.java This driver program should then run with your Queue class (no modifications allowed to the driver program). Your Queue class should have at least the following methods: one or more constructors, enqueue, dequeue,...
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete....
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete. Return true or false to indicate success or failure. Delete the memory the node was using The algorithm for deleting a Node to a Linked List (general case): ● Begin at the head. ● Compare the id to the current node. ● If search id > current id, stop. ● Detach the current Node ○ current->previous->next = current->next ○ current->next->previous = current->previous ● Deallocate...
1. Design and implement a CircularLinkedList, which is essentially a linked list in which the next...
1. Design and implement a CircularLinkedList, which is essentially a linked list in which the next reference of the tail node is set to refer back to the head of the list (rather than null) . Start from the SinglyLinkedList provided in the Lecture (not the built-in Java LinkedList class). 2. Starting from  SinglyLinkedList you will need to modify or complete methods: first(), last(), addFirst(), addLast(), removeFirst(), toString(), and also create a new rotate() method which will move the tail to...
i want to complete this code to insert a new node in the middle of list...
i want to complete this code to insert a new node in the middle of list (take a node data from user, search the node and insert new node after this node). this is the code #include <iostream> #include <stdlib.h> using namespace std ; struct Node{                int data;                Node *link ;}; struct Node *head=NULL, *tail=NULL; /* pointers to Node*/ void InsertFront(); void InsertRear(); void DeleteFront(); void DeleteRear(); int main(){                int choice;                do{                               cout << "1:...