Data Structures and Algorithms in Java
6th Edition
ISBN: 9781118771334
Author: Michael T. Goodrich
Publisher: WILEY
expand_more
expand_more
format_list_bulleted
Expert Solution & Answer
Chapter 3, Problem 5R
Explanation of Solution
Consequences when delete the two lines from code:
Note: Refer Code Fragment 3.15 “SinglyLinkedList class definition” in the Text book.
The SinglyLinkedList class contains number of methods such as “size()”, “first()”, “last()”, “addFirst()”, “addLast()”, “removeLast()”, and “removeFirst()”.
In removeFirst() method,
- Remove the line number “51” and “52” in this method.
- That is, resetting the “tail” field to “null”.
Modified:
In the above code, just remove or delete the Line “51” and “52”. Then the code is given below:
//Method definition
public E removeFirst( ) //Line 46
{
//Check whether the linked list is empty
if (isEmpty( )) //Line 47
//Return null, there is no element to remove
return null;
/*Get the head node from linked list and assigned it. */
E answer = head.getElement( ); //Line 48
//Assign the head node as next node of head
head = head...
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
You are required to complete the LinkedList class. This class is used as a linked list that has many methods to perform operations on the linked list. To create a linked list, create an object of this class and use the addFirst or addLast or add(must be completed) to add nodes to this linked list. Your job is to complete the empty methods. For every method you have to complete, you are provided with a header, Do not modify those headers(method name, return type or parameters). You have to complete the body of the method.
package chapter02;
public class LinkedList
{
protected LLNode list;
public LinkedList()
{
list = null;
}
public void addFirst(T info)
{
LLNode node = new LLNode(info);
node.setLink(list);
list = node;
}
public void addLast(T info)
{
LLNode curr = list;
LLNode newNode = new LLNode(info);
if(curr == null)
{
list = newNode;
}
else
{
while(curr.getLink() !=…
Add a new public member function to the LinkedList class named reverse() which reverses the items in the list. You must take advantage of the doubly-linked list structure to do this efficiently as discussed in the videos/pdfs, i.e. swap each node’s prev/next pointers, and finally swap headPtr/tailPtr. Demonstrate your function works by creating a sample list of a few entries in main(), printing out the contents of the list, reversing the list, and then printing out the contents of the list again to show that the list has been reversed.
Note: your function must actually reverse the items in the doubly-linked list, not just print them out in reverse order!
Note: we won't use the copy constructor in this assignment, and as such you aren't required to update the copy constructor to work with a doubly-linked list.
This is what I have so far but its not working!
template<class ItemType>void LinkedList<ItemType>::reverse(){ Node<ItemType>*curPtr,*prev,*next;…
Important: Make all your implementation in the same attached file and submit only one file in the
submission link.
Given the linked list data structure discussed in the lecture, implement a sub-class
TSortedList that makes sure that elements are inserted and maintained in an ascending
order in the list. So, given the input sequence {1,7,3,11,5}, when printing the list after
inserting the last element it should print like 1, 3, 5, 7, 11. Note that with inheritance, you
have to only care about the insertion situation as deletion should still be handled by the
parent class.
In the basic implementation, assume that you only have head which is a pointer to the
head of the list. Now, if we have both head and tail pointers, what improvements can be
done to speed up the insertion?
Chapter 3 Solutions
Data Structures and Algorithms in Java
Ch. 3 - Prob. 1RCh. 3 - Write a Java method that repeatedly selects and...Ch. 3 - Prob. 3RCh. 3 - The TicTacToe class of Code Fragments 3.9 and 3.10...Ch. 3 - Prob. 5RCh. 3 - Prob. 6RCh. 3 - Prob. 7RCh. 3 - Prob. 8RCh. 3 - Prob. 9RCh. 3 - Prob. 10R
Ch. 3 - Prob. 11RCh. 3 - Prob. 12RCh. 3 - Prob. 13RCh. 3 - Prob. 14RCh. 3 - Prob. 15RCh. 3 - Prob. 16RCh. 3 - Prob. 17CCh. 3 - Prob. 18CCh. 3 - Prob. 19CCh. 3 - Give examples of values for a and b in the...Ch. 3 - Suppose you are given an array, A, containing 100...Ch. 3 - Write a method, shuffle(A), that rearranges the...Ch. 3 - Suppose you are designing a multiplayer game that...Ch. 3 - Write a Java method that takes two...Ch. 3 - Prob. 25CCh. 3 - Prob. 26CCh. 3 - Prob. 27CCh. 3 - Prob. 28CCh. 3 - Prob. 29CCh. 3 - Prob. 30CCh. 3 - Prob. 31CCh. 3 - Prob. 32CCh. 3 - Prob. 33CCh. 3 - Prob. 34CCh. 3 - Prob. 35CCh. 3 - Write a Java program for a matrix class that can...Ch. 3 - Write a class that maintains the top ten scores...Ch. 3 - Prob. 38PCh. 3 - Write a program that can perform the Caesar cipher...Ch. 3 - Prob. 40PCh. 3 - Prob. 41PCh. 3 - Prob. 42PCh. 3 - Prob. 43P
Knowledge Booster
Similar questions
- Design and implement a getLastHalf() method for the MyLinkedList class. The method should return the last half of the list as a new list leaving the original list intact. If the list has an uneven number of elements the extra one element must be in the list returned. Example : [1,3,5,4] return [5,4] and [1,6,9] return [6,9]. Follow the three step method for designing the method Develop the java code for the method Create a test program to test the method thoroughly using the Integer wrapper class.arrow_forwardDesign and implement a getLastHalf() method for the MyLinkedList class. The method should return the last half of the list as a new list leaving the original list intact. If the list has an uneven number of elements the extra one element must be in the list returned. Example : [1,3,5,4] return [5,4] and [1,6,9] return [6,9]. Follow the three step method for designing the method Develop the java code for the method Create a test program to test the method thoroughly using the Integer wrapper class. public class MyLinkedList<E> { private Node<E> head, tail; public MyLinkedList() { head = null; tail = null; } /** Return the head element in the list */ public E getFirst() { if (head == null) { return null; } else { return head.element; } } /** Return the last element in the list */ public E getLast() { if (head==null) { return null; } else { return tail.element; } } /** Add an element to the beginning of the list */ public void prepend(E e) { Node<E> newNode = new…arrow_forwardDesign and implement a getLastHalf() method for the MyLinkedList class. The method should return the last half of the list as a new list leaving the original list intact. If the list has an uneven number of elements the extra one element must be in the list returned. Example : [1,3,5,4] return [5,4] and [1,6,9] return [6,9]. Follow the three step method for designing the method Develop the java code for the method Create a test program to test the method thoroughly using the Integer wrapper class.arrow_forward
- You may find a doubly-linked list implementation below. Our first class is Node which we can make a new node with a given element. Its constructor also includes previous node reference prev and next node reference next. We have another class called DoublyLinkedList which has start_node attribute in its constructor as well as the methods such as: 1. insert_to_empty_list() 2. insert_to_end() 3. insert_at_index() Hints: Make a node object for the new element. Check if the index >= 0.If index is 0, make new node as head; else, make a temp node and iterate to the node previous to the index.If the previous node is not null, adjust the prev and next references. Print a message when the previous node is null. 4. delete_at_start() 5. delete_at_end() . 6. display() the task is to implement these 3 methods: insert_at_index(), delete_at_end(), display(). hint on how to start thee code # Initialize the Node class Node: def __init__(self, data): self.item = data…arrow_forwardWrite a method replace to be included in the class KWLinkedList (for doubly linked list) that accepts two parameters, searchItem and repItem of type E. The method searches for searchItem in the doubly linked list, if found then replace it with repItem and return true. If the searchItem is not found in the doubly linked list, then insert repItem at the end of the linked list and return false. Assume that the list is not empty. You can use ListIterator and its methods to search the searchItem in the list and replace it with repItem if found. Do not call any method of class KWLinkedList to add a new node at the end of the list. Method Heading: public boolean replace(E searchItem, E repItem) Example: searchItem: 15 repItem: 17 List (before method call): 9 10 15 20 4 5 6 List (after method call) : 9 10 17 20 4 5 6arrow_forwardplease follow instructions correctly. You are required to complete the LinkedList class. This class is used as a linked list that has many methods to perform operations on the linked list. To create a linked list, create an object of this class and use the addFirst or addLast or add(must be completed) to add nodes to this linked list. Your job is to complete the empty methods. For every method you have to complete, you are provided with a header, Do not modify those headers(method name, return type or parameters). You have to complete the body of the method. package chapter02; public class LinkedList { protected LLNode list; public LinkedList() { list = null; } public void addFirst(T info) { LLNode node = new LLNode(info); node.setLink(list); list = node; } public void addLast(T info) { LLNode curr = list; LLNode newNode = new LLNode(info); if(curr == null) { list = newNode; } else…arrow_forward
- Given the linked list data structure, implement a sub-class TSortedList that makes sure that elements are inserted and maintained in an ascending order in the list. So, given the input sequence {1,7,3,11,5}, when printing the list after inserting the last element it should print like 1, 3, 5, 7, 11. Note that with inheritance, you have to only care about the insertion situation as deletion should still be handled by the parent class.arrow_forwardImplement the insert function in SLList class to insert an item x at a particular position in the list indexed by i. For example, let L= [1,2,3]. A call toL.insert (4,1) will make L=[1,4,2,3]. You should not change the item of existing nodes. Below is a skeleton of the Node and SLList class: template class Node public: ItemType item; Node *next; Node (ItemIype i, Node *n = nullptr) { item - i; next = n; } ; template class SLList { private: /** Pointer pointing to the sentinel node. */ Node *sentinel; /** Stores the current size of the list. */ int count; public: // Other functions omitted... void insert (const Item &x, int i) { // Copy this function in the answer and write code below this line. } };arrow_forwardThere’s a somewhat imperfect analogy between a linked list and a railroad train, where individual cars represent links. Imagine how you would carry out various linked list operations, such as those implemented by the member functions insertFirst(), removeFirst(), and remove(int key) from the LinkList class in this hour. Also implement an insertAfter() function. You’ll need some sidings and switches. You can use a model train set if you have one. Otherwise, try drawing tracks on a piece of paper and using business cards for train cars.arrow_forward
- Add a method swapTwoNodes to SinglyLinkedList class from week 2 lecture examples. This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapTwoNodes method. Hint: You may need to traverse the list. Please give me the full code and share how it works thank you! I need java code, not C ++ or C#.arrow_forwardJava - Mileage for a Runnerarrow_forwardFor the AVLTree class, create a deletion function that makes use of lazy deletion.There are a number of methods you can employ, but one that is straightforward is to merely include a Boolean field in the Node class that indicates whether or not the node is designated for elimination. Then, your other approaches must take into consideration this field.arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
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)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education