Question

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.

2. 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;
}
}

2. [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;
}
}

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.