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 following the given node.

- Write a method deleteKth that takes an int argument k and deletes the kth element in a linked list, if it exists.

Notice: Please do not modify the other methods in SLList class, just add the methods above.

public class SLList {
   private Node first;
   private Node last;
   private int n; // size of the list

   // helper node class
   private class Node {
      Item item;
      Node next;
   }

   // constructor: initializes an empty list
   public SLList() {
      first = last = null;
      n = 0;
   }

   public boolean isEmpty() {
      return first == null;
   }

   // return the size of the list
   public int size() {
      return n;
   }

   // insert an item at the front of the list
   public void addFirst(Item item) {
      if (isEmpty()) { // first & last refer to the same node
         first = last = new Node();
         first.item = last.item = item;
      } else {  //first refers to the new node
         Node oldFirst = first;
         first = new Node();
         first.item = item;
         first.next = oldFirst;
      }
      n++; // increment size after insertion
   }

   // insert item at the end of the list
   public void addLast(Item item) {
      if (isEmpty()) { // first & last refer to the same node
         first = last = new Node();
         first.item = last.item = item;
      } else { // last.next refers to the new node
         last = last.next = new Node();
         last.item = item;
      }
      n++; // increment size after insertion
   }

   // remove & return the first item in the list
   public Item removeFirst() {
      if (isEmpty()) {
         throw new RuntimeException("Empty List");
      }
      Item removedItem = first.item;  // retrieve the data item being removed
      if (first == last) {             // if there's only one node in the list
         // update both first & last references
         first = last = null;
      }
      else   { // otherwise, update first only
         first = first.next;
      }
      n--; // decrement size after removal
      return removedItem;
   }


   // remove & return the last item in the list
   public Item removeLast() {
      if (isEmpty()) throw new RuntimeException("empty list");
      Item removedItem = last.item;   // retrieve the data item being removed
      if (first == last) { // if there's only one node in the list,
         // update both first & last references
         first = last = null;
      }
      else {  // iterate through the list to locate the last node
         Node current = first;
         while (current.next != last) {
            current = current.next;
         }
         last = current;
         current.next = null;
         // ...  current is the new last node
         //

      } // end else
      n--; // decrement size after removal
      return removedItem;
   }

   // A String representation of this list, so that clients can print it
   // (There's no need to change it, but you can, if you'd like.)
   @Override
   public String toString() {
      StringBuilder s = new StringBuilder();
      Node current = first;
      while (current != null) {
         s.append(current.item + " -> ");
         // s.append(current.item + " ");
         current = current.next;
      }
      s.append("null");
      //s.append("\n");
      return s.toString();
   }
   private Node getNode(int index) {
      Node current = first;
      for (int i = 0; i < index; i++) {
         current = current.next;
      }
      return current;
   }

   public Item get(int index) {
      if (index < 0 || index >= n) {
         throw new IndexOutOfBoundsException("out of bounds");
      }
   return getNode(index).item;
   }

   public Item set(int index, Item item) {
      if (index < 0 || index >= n) {
         throw new IndexOutOfBoundsException("out of bounds");
      }
      Node target = getNode(index);
      Item oldItem = target.item;
      target.item = item;
      return oldItem;
   }

}

Solutions

Expert Solution

public class SLList {
   private Node first;
   private Node last;
   private int n; // size of the list

   // helper node class
   private class Node {
      Item item;
      Node next;
   }

   // constructor: initializes an empty list
   public SLList() {
      first = last = null;
      n = 0;
   }

   public boolean isEmpty() {
      return first == null;
   }

   // return the size of the list
   public int size() {
      return n;
   }

   // insert an item at the front of the list
   public void addFirst(Item item) {
      if (isEmpty()) { // first & last refer to the same node
         first = last = new Node();
         first.item = last.item = item;
      } else {  //first refers to the new node
         Node oldFirst = first;
         first = new Node();
         first.item = item;
         first.next = oldFirst;
      }
      n++; // increment size after insertion
   }

   // insert item at the end of the list
   public void addLast(Item item) {
      if (isEmpty()) { // first & last refer to the same node
         first = last = new Node();
         first.item = last.item = item;
      } else { // last.next refers to the new node
         last = last.next = new Node();
         last.item = item;
      }
      n++; // increment size after insertion
   }

   // remove & return the first item in the list
   public Item removeFirst() {
      if (isEmpty()) {
         throw new RuntimeException("Empty List");
      }
      Item removedItem = first.item;  // retrieve the data item being removed
      if (first == last) {             // if there's only one node in the list
         // update both first & last references
         first = last = null;
      }
      else   { // otherwise, update first only
         first = first.next;
      }
      n--; // decrement size after removal
      return removedItem;
   }


   // remove & return the last item in the list
   public Item removeLast() {
      if (isEmpty()) throw new RuntimeException("empty list");
      Item removedItem = last.item;   // retrieve the data item being removed
      if (first == last) { // if there's only one node in the list,
         // update both first & last references
         first = last = null;
      }
      else {  // iterate through the list to locate the last node
         Node current = first;
         while (current.next != last) {
            current = current.next;
         }
         last = current;
         current.next = null;
         // ...  current is the new last node
         //

      } // end else
      n--; // decrement size after removal
      return removedItem;
   }

   // A String representation of this list, so that clients can print it
   // (There's no need to change it, but you can, if you'd like.)
   @Override
   public String toString() {
      StringBuilder s = new StringBuilder();
      Node current = first;
      while (current != null) {
         s.append(current.item + " -> ");
         // s.append(current.item + " ");
         current = current.next;
      }
      s.append("null");
      //s.append("\n");
      return s.toString();
   }
   private Node getNode(int index) {
      Node current = first;
      for (int i = 0; i < index; i++) {
         current = current.next;
      }
      return current;
   }

    private addAfter(int k,Item item)
        {
        Item head = headItem; 
    if (k < 1) 
        System.out.print("Invalid"); 
    if (k == 1) { 
        Item newItem = new Item(data); 
        newItem.nextItem = headItem; 
        head = newItem; 
    } else { 
        while (k-- != 0) { 
            if (k == 1) { 
                Item newItem = GetItem(data); 
                newItem.nextItem = headItem.nextItem; 
                headItem.nextItem = newItem; 
            } 
            headItem = headItem.nextItem; 
        } 
        if (k!= 1) 
            System.out.print("Out of range"); 
    } 
    return head; 
        }

   public Item get(int index) {
      if (index < 0 || index >= n) {
         throw new IndexOutOfBoundsException("out of bounds");
      }
   return getNode(index).item;
   }

   private deleteAfter(Node node)
   {
                if (headNode == null) 
                        return; 
            Node tempNode = headNode; 
            if (position == 0) 
            { 
                headNode = tempNode.next;
                return; 
            } 
            for (int i=0; tempNode!=null && i<position-1; i++) 
                tempNode = tempNode.next; 
            if (tempNode == null || tempNode.next == null) 
                return; 
            Node next = tempNode.next.next; 
            tempNode.next = next;
   } 

    void deleteKth(int k) 
    { 
        if (headNode == null) 
            return; 
        Node tempNode = headNode; 
        if (k == 0) 
        { 
            headNode = tempNode.next;   
            return; 
        } 
        for (int i=0; tempNode!=null && i<k-1; i++) 
                tempNode = tempNode.next; 
        if (tempNode == null || tempNode.next == null) 
            return; 
        Node nextNode = tempNode.next.next; 
        tempNode.next = nextNode;  
    } 

   public Item set(int index, Item item) {
      if (index < 0 || index >= n) {
         throw new IndexOutOfBoundsException("out of bounds");
      }
      Node target = getNode(index);
      Item oldItem = target.item;
      target.item = item;
      return oldItem;
   }

}

venereology answered 6 months ago

Next > < Previous

Related Solutions

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...

Data Structures Homework – Singly Linked Lists Create a singly linked that represents a school. The...

Data Structures Homework – Singly Linked Lists Create a singly linked that represents a school. The school has multiple classes. Each class has a different number of students. class student { Long ID; string Name; string Address; float grades[3]; student *below; }; class Node // the node represents a class in school { int ID; int NoOfStudents; int NoOfQuizes; student *t;// a linked list of students is allocated dynamically Node *Next; }; class school { string Name; Node *Head; int...

Data Structures on Java Basic Linked List exercises a. Suppose x is a linked-list node and...

Data Structures on Java Basic Linked List exercises a. Suppose x is a linked-list node and not the last node on the list. What is the effect of the following code fragment? x.next = x.next.next b. Singly Linked List has two private instance variables first and last as that point to the first and the last nodes in the list, respectively. Write a fragment of code that removes the last node in a linked list whose first node is first....

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).

Exercise 1: Write a program in Java to manipulate a Singly Linked List: 1. Create Singly...

Exercise 1: Write a program in Java to manipulate a Singly Linked List: 1. Create Singly Linked List 2. Display the list 3. Count the number of nodes 4. Insert a new node at the beginning of a Singly Linked List. 5. Insert a new node at the end of a Singly Linked List 6. Insert a new node after the value 5 of Singly Linked List 7. Delete the node with value 6. 8. Search an existing element in...

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...

c. You are given the following Java files: SLL.java that implements generic Singly Linked List, with...

c. You are given the following Java files: SLL.java that implements generic Singly Linked List, with class SLLNode listed as inner class. TestIntegerSLL.java that tests the SLL class by using a linked list of Integer. In SLL class add the following method: public void moveToEnd (int i) It will move the element at the i -th position to the end of the list. You can assume i to be within the list, and that the first element has the...

Array-Based Linked List Implementation: JAVA Decide how to write the methods with items being stored in...

Array-Based Linked List Implementation: JAVA Decide how to write the methods with items being stored in an array. NOT in linked List. Implement an array-based Linked List in your language. Use double as the item. You need to create a driver includes several items and inserts them in order in a list. Identify the necessary methods in a List Linked implementation. Look at previous Data Structures (stack or queue) and be sure to include all necessary methods. DO NOT USE...

Subjects