Question

In: Computer Science

Q1) In the implementation of Singly linked list we had an integer variable called size that...

Q1) In the implementation of Singly linked list we had an integer variable called size that keeps track of how many elements in the list. Also, we have a reference “tail” that points to the last node in the list. You are asked to re-implement the concept of singly linked list without using variable size, and without using reference “tail”.

a) What are the methods of the main operation of singly linked list that need to be changed? Rewrite them according to this change (only the methods that need to be changed).

b) Will that affect the performance of any one of the main operations( size, isEmpty, first, last, addFirst, addLast, removeFirst, removeLast)? Explain.

Please answer based in the following codes:

public class Node <E>{

private E data;

private Node<E> next;

public Node(E d, Node<E> n)

{  data=d;

next=n; }

public E getData() { return data; }

public Node<E> getNext(){ return next; }

public void setNext(Node<E> n) { next=n; } }

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

public class SinglyLinkedList <E>{

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.getData();

}

public E last() // last()

{

if (isEmpty()) return null;

return head.getData();

}

public void addFirst(E e) // addFirst()

{

head=new Node<>(e,head);

if(size==0)

tail=head;

size++;

}

public void addLast(E e) //addLast()

{

Node<E> newest=new Node<>(e,null);

if(isEmpty())

head=newest;

else

tail.setNext(newest);

tail=newest;

size++;

}

public E removeFirst() // removeFirst()

{

if(isEmpty()) return null;

E answer=head.getData();

head=head.getNext();

size--;

if (size==0)

tail=null;

return answer;

}

public E removeLast() // removeLast()

{

if(isEmpty()) return null;

E answer=tail.getData();

if (head==tail)

head=tail=null;

else

{ Node<E> tmp=head;

while (tmp.getNext()!=tail)

tmp=tmp.getNext();

tmp.setNext(null);

tail=tmp;

}

size--;

return answer;

}

}

Solutions

Expert Solution

note: plzzz don't give dislike.....plzzz comment if you have any problem i will try to solve your problem.....plzzz give thumbs up i am in need....


Related Solutions

You are provided with a partial implementation of a templated singly-linked list in LinkedList.h, with some...
You are provided with a partial implementation of a templated singly-linked list in LinkedList.h, with some missing functionality. It contains a templated Node class and a templated LinkedList class. Do not modify the class definitions. The linked list class contains the following methods: • LinkedList – Constructor of a linked list with a head pointing to null (implemented). • ~LinkedList – Destructor of a linked list. • deleteFromHead – Removes and returns content of the first node of the list....
Give a complete implementation of the queue ADT using a singly linked list that includes a...
Give a complete implementation of the queue ADT using a singly linked list that includes a header sentinel (in Python).
Data Structures in Java In the following Singly Linked List implementation, add the following methods, and...
Data Structures in Java In the following Singly Linked List implementation, add the following methods, and write test cases in another java file to make sure these methods work. - Write a private method addAfter(int k, Item item) that takes two arguments, an int argument k and a data item, and inserts the item into the list after the K-th list item. - Write a method removeAfter(Node node) that takes a linked-list Node as an argument and removes the node...
class SLinkedList: """Singly linked list with access to front and end, and with stored size. """...
class SLinkedList: """Singly linked list with access to front and end, and with stored size. """ #-------------------------- nested _Node class -------------------------- class _Node: __slots__ = '_element', '_next' # streamline memory usage def __init__(self, element, next): self._element = element self._next = next #------------------------------- queue methods ------------------------------- def __init__(self): """Create an empty list.""" self._head = None self._tail = None self._size = 0 def __len__(self): """Return the number of elements in the list.""" return self._size def isEmpty(self): """Return True if the list is...
Add the following methods to the singly list implementation below. int size(); // Returns the number...
Add the following methods to the singly list implementation below. int size(); // Returns the number of nodes in the linked list bool search(string query); // Returns if the query is present in the list void add(List& l); // // Adds elements of input list to front of "this" list (the list that calls the add method) ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- // slist.cpp #include <string> #include "slist.h" using namespace std; Node::Node(string element) : data{element}, next{nullptr} {} List::List() : first{nullptr} {} // Adds to...
Add the following methods to the singly list implementation below. int size(); // Returns the number...
Add the following methods to the singly list implementation below. int size(); // Returns the number of nodes in the linked list bool search(string query); // Returns if the query is present in the list void add(List& l); // // Adds elements of input list to front of "this" list (the list that calls the add method) #include <string> #include "slist.h" using namespace std; Node::Node(string element) : data{element}, next{nullptr} {} List::List() : first{nullptr} {} // Adds to the front of...
In C++: Provide a linked implementation of a deque and name it LinkedDeque (use singly linked...
In C++: Provide a linked implementation of a deque and name it LinkedDeque (use singly linked list). It can be a template/generic class or you can set it up with a certain data type. Use a test driver to try out your LinkedDeque by adding and removing values from both ends.
I was supposed to conver a singly linked list to a doubly linked list and everytime...
I was supposed to conver a singly linked list to a doubly linked list and everytime I run my program the output prints a bunch of random numbers constantly until I close the console. Here is the code. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> struct node { int data; struct node *next; struct node *prev; }; //this always points to first link struct node *head = NULL; //this always points to last link struct node *tail = NULL;...
You are given a singly linked list. Write a function to find if the linked list...
You are given a singly linked list. Write a function to find if the linked list contains a cycle or not. A linked list may contain a cycle anywhere. A cycle means that some nodes are connected in the linked list. It doesn't necessarily mean that all nodes in the linked list have to be connected in a cycle starting and ending at the head. You may want to examine Floyd's Cycle Detection algorithm. /*This function returns true if given...
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT