Data Structures - Singly Linked Lists
You will add a method swapNodes to SinglyLinkedList class (below). 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 swapNodes method. You may need to traverse the list.
package linkedlists;
public class SinglyLinkedList<E> implements Cloneable {
// ---------------- nested Node class
----------------
/**
* Node of a singly linked list, which stores a
reference to its element and to
* the subsequent node in the list (or null if this is
the last node).
*/
private static class Node<E> {
/** The element stored at this
node */
private E element; // reference to
the element stored at this node
/** A reference to the
subsequent node in the list */
private Node<E> next; //
reference to the subsequent node in the list
/**
* Creates a node with the given
element and next node.
*
* @param e the element to be
stored
* @param n reference to a node that
should follow the new node
*/
public Node(E e, Node<E> n)
{
element =
e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the
node.
*
* @return the element stored at the
node
*/
public E getElement() {
return
element;
}
/**
* Returns the node that follows
this one (or null if no such node).
*
* @return the following node
*/
public Node<E> getNext()
{
return
next;
}
// Modifier methods
/**
* Sets the node's next reference to
point to Node n.
*
* @param n the node that should
follow this one
*/
public void setNext(Node<E>
n) {
next = n;
}
} // ----------- end of nested Node class -----------
// instance variables of the SinglyLinkedList
/** The head node of the list */
private Node<E> head = null; // head node of the
list (or null if empty)
/** The last node of the list */
private Node<E> tail = null; // last node of the
list (or null if empty)
/** Number of nodes in the list */
private int size = 0; // number of nodes in the
list
/** Constructs an initially empty list. */
public SinglyLinkedList() {
} // constructs an initially empty list
// access methods
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public E first() { // returns (but does not remove)
the first element
if (isEmpty())
return
null;
return head.getElement();
}
public E last() { // returns (but does not remove) the
last element
if (isEmpty())
return
null;
return tail.getElement();
}
// update methods
public void addFirst(E e) { // adds element e to the
front of the list
head = new Node<>(e, head);
// create and link a new node
if (size == 0)
tail = head; //
special case: new node becomes tail also
size++;
}
public void addLast(E e) { // adds element e to the
end of the list
Node<E> newest = new
Node<>(e, null); // node will eventually be the tail
if (isEmpty())
head = newest;
// special case: previously empty list
else
tail.setNext(newest); // new node after existing tail
tail = newest; // new node becomes
the tail
size++;
}
public E removeFirst() { // removes and returns the
first element
if (isEmpty())
return null; //
nothing to remove
E answer = head.getElement();
head = head.getNext(); // will
become null if list had only one node
size--;
if (size == 0)
tail = null; //
special case as list is now empty
return answer;
}
@SuppressWarnings({ "unchecked" })
public boolean equals(Object o) {
if (o == null)
return
false;
if (getClass() !=
o.getClass())
return
false;
SinglyLinkedList other =
(SinglyLinkedList) o; // use nonparameterized type
if (size != other.size)
return
false;
Node walkA = head; // traverse the
primary list
Node walkB = other.head; //
traverse the secondary list
while (walkA != null) {
if
(!walkA.getElement().equals(walkB.getElement()))
return false; // mismatch
walkA =
walkA.getNext();
walkB =
walkB.getNext();
}
return true; // if we reach this,
everything matched successfully
}
@SuppressWarnings({ "unchecked" })
public SinglyLinkedList<E> clone() throws
CloneNotSupportedException {
// always use inherited
Object.clone() to create the initial copy
SinglyLinkedList<E> other =
(SinglyLinkedList<E>) super.clone(); // safe cast
System.out.println(other.head.getElement());
if (size > 0) { // we need
independent chain of nodes
other.head = new
Node<>(head.getElement(), null);
Node<E>
walk = head.getNext(); // walk through remainder of original
list
Node<E>
otherTail = other.head; // remember most recently created
node
while (walk !=
null) { // make a new node storing same element
Node<E> newest = new
Node<>(walk.getElement(), null);
otherTail.setNext(newest); // link previous node
to this one
otherTail = newest;
walk = walk.getNext();
}
}
return other;
}
public int hashCode() {
int h = 0;
for (Node walk = head; walk !=
null; walk = walk.getNext()) {
h ^=
walk.getElement().hashCode(); // bitwise exclusive-or with
element's code
h = (h <<
5) | (h >>> 27); // 5-bit cyclic shift of composite
code
}
return h;
}
public String toString() {
StringBuilder sb = new
StringBuilder("(");
Node<E> walk = head;
while (walk != null) {
sb.append(walk.getElement());
if (walk !=
tail)
sb.append(", ");
walk =
walk.getNext();
}
sb.append(")");
return sb.toString();
}
public void reverse() {
Node<E> reversedPart =
null;
Node<E> curr = head;
tail = curr;
while (curr != null) {
Node<E>
next = curr.next;
curr.next =
reversedPart;
reversedPart =
curr;
curr = next;
}
head = reversedPart;
}
// main method
public static void main(String[] args) {
SinglyLinkedList<String>
list = new SinglyLinkedList<String>();
list.addFirst("MSP");
list.addLast("ATL");
list.addLast("BOS");
//
list.addFirst("LAX");
System.out.println("Original List: "+list);
//
list.reverse();
System.out.println("Reversed List:
"+list);
System.out.println("Swaped List:
"+list);
}
}
// ---------------- nested Node class ----------------
/**
* Node of a singly linked list, which stores a
reference to its element and to
* the subsequent node in the list (or null if this is
the last node).
*/
private static class Node<E> {
/** The element stored at this
node */
private E element; // reference to
the element stored at this node
/** A reference to the
subsequent node in the list */
private Node<E> next; //
reference to the subsequent node in the list
/**
* Creates a node with the given
element and next node.
*
* @param e the element to be
stored
* @param n reference to a node that
should follow the new node
*/
public Node(E e, Node<E> n)
{
element =
e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the
node.
*
* @return the element stored at the
node
*/
public E getElement() {
return
element;
}
/**
* Returns the node that follows
this one (or null if no such node).
*
* @return the following node
*/
public Node<E> getNext()
{
return
next;
}
// Modifier methods
/**
* Sets the node's next reference to
point to Node n.
*
* @param n the node that should
follow this one
*/
public void setNext(Node<E>
n) {
next = n;
}
} // ----------- end of nested Node class -----------
// instance variables of the SinglyLinkedList
/** The head node of the list */
private Node<E> head = null; // head node of the
list (or null if empty)
/** The last node of the list */
private Node<E> tail = null; // last node of the
list (or null if empty)
/** Number of nodes in the list */
private int size = 0; // number of nodes in the
list
/** Constructs an initially empty list. */
public SinglyLinkedList() {
} // constructs an initially empty list
// access methods
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public E first() { // returns (but does not remove)
the first element
if (isEmpty())
return
null;
return head.getElement();
}
public E last() { // returns (but does not remove) the
last element
if (isEmpty())
return
null;
return tail.getElement();
}
// update methods
public void addFirst(E e) { // adds element e to the
front of the list
head = new Node<>(e, head);
// create and link a new node
if (size == 0)
tail = head; //
special case: new node becomes tail also
size++;
}
public void addLast(E e) { // adds element e to the
end of the list
Node<E> newest = new
Node<>(e, null); // node will eventually be the tail
if (isEmpty())
head = newest;
// special case: previously empty list
else
tail.setNext(newest); // new node after existing tail
tail = newest; // new node becomes
the tail
size++;
}
public E removeFirst() { // removes and returns the
first element
if (isEmpty())
return null; //
nothing to remove
E answer = head.getElement();
head = head.getNext(); // will
become null if list had only one node
size--;
if (size == 0)
tail = null; //
special case as list is now empty
return answer;
}
@SuppressWarnings({ "unchecked" })
public boolean equals(Object o) {
if (o == null)
return
false;
if (getClass() !=
o.getClass())
return
false;
SinglyLinkedList other =
(SinglyLinkedList) o; // use nonparameterized type
if (size != other.size)
return
false;
Node walkA = head; // traverse the
primary list
Node walkB = other.head; //
traverse the secondary list
while (walkA != null) {
if
(!walkA.getElement().equals(walkB.getElement()))
return false; // mismatch
walkA =
walkA.getNext();
walkB =
walkB.getNext();
}
return true; // if we reach this,
everything matched successfully
}
@SuppressWarnings({ "unchecked" })
public SinglyLinkedList<E> clone() throws
CloneNotSupportedException {
// always use inherited
Object.clone() to create the initial copy
SinglyLinkedList<E> other =
(SinglyLinkedList<E>) super.clone(); // safe cast
System.out.println(other.head.getElement());
if (size > 0) { // we need
independent chain of nodes
other.head = new
Node<>(head.getElement(), null);
Node<E>
walk = head.getNext(); // walk through remainder of original
list
Node<E>
otherTail = other.head; // remember most recently created
node
while (walk !=
null) { // make a new node storing same element
Node<E> newest = new
Node<>(walk.getElement(), null);
otherTail.setNext(newest); // link previous node
to this one
otherTail = newest;
walk = walk.getNext();
}
}
return other;
}
public int hashCode() {
int h = 0;
for (Node walk = head; walk !=
null; walk = walk.getNext()) {
h ^=
walk.getElement().hashCode(); // bitwise exclusive-or with
element's code
h = (h <<
5) | (h >>> 27); // 5-bit cyclic shift of composite
code
}
return h;
}
public String toString() {
StringBuilder sb = new
StringBuilder("(");
Node<E> walk = head;
while (walk != null) {
sb.append(walk.getElement());
if (walk !=
tail)
sb.append(", ");
walk =
walk.getNext();
}
sb.append(")");
return sb.toString();
}
public void reverse() {
Node<E> reversedPart =
null;
Node<E> curr = head;
tail = curr;
while (curr != null) {
Node<E>
next = curr.next;
curr.next =
reversedPart;
reversedPart =
curr;
curr = next;
}
head = reversedPart;
}
// main method
public static void main(String[] args) {
SinglyLinkedList<String>
list = new SinglyLinkedList<String>();
list.addFirst("MSP");
list.addLast("ATL");
list.addLast("BOS");
//
list.addFirst("LAX");
System.out.println("Original List: "+list);
//
list.reverse();
System.out.println("Reversed List:
"+list);
System.out.println("Swaped List:
"+list);
}
}
Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given reference...
Q1: You can find a file that defines the CircularlyLinked List class similar to what we discussed in the class. Download the file and work on it. Your task is to: 1. Complete the missing methods in the file as discussed in the class. Search for the comment/" MISSING / in the file to see the methods that need to be completed. 2. Add the following methods to the class a. public Node getMin 1. Task: find the node with...
Here is the IntegerLinkedList_incomplete class: public class IntegerLinkedList { static class Node { /** The element stored at this node */ private int element; // reference to the element stored at this node /** A reference to the subsequent node in the list */ private Node next; // reference to the subsequent node in the list /** * Creates a node with the given element and next node. * * @param e the element to be stored * @param n...
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying nodes referenced by positions p and q to be exchanged for each other. Relink the existing nodes, do not create any new nodes. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- package lists; import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedPositionalList implements PositionalList { //---------------- nested Node class ---------------- /** * Node of a doubly linked list, which stores a reference to its * element and to both the previous and next...
Given a singly-linked list interface and linked list node class, implement the singly-linked list which has the following methods in Java: 1. Implement 3 add() methods. One will add to the front (must be O(1)), one will add to the back (must be O(1)), and one will add anywhere in the list according to given index (must be O(1) for index 0 and O(n) for all other indices). They are: void addAtIndex(int index, T data), void addToFront(T data), void addToBack(T...
Complete two of the List methods: SinglyLinkedList::size() and SinglyLinkedList::get(). import java.util.AbstractList; public class SinglyLinkedList<E> extends AbstractList<E> { /** Reference to the first node in our linked list. This will be null if the list is empty. */ private Entry head; /** * Creates an empty list. */ public SinglyLinkedList() { reset(); } /** * This method, which is only used within the SinglyLinkedList class, returns the instance to its initial state. This * call will reset the head to be...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to class SinglyLinkedList (defined here) that takes as input a “data” value and returns a pointer to a node. If the input data is present in the linked list, the returned pointer should point to that node; if not, the returned pointer is nullptr. Write the (single line) method declaration/specification. Write the method definition/implementation. Test by running the main() function below and capture the console...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Given a singly linked list contains 5 nodes, which simply shows as 5->4->3->2->1, what is the value that you can find in the second node of the remaining list if the following statements are applied? Assume head reference refers the first node of the list. Node prev = head; Node curr = head. next; while(curr.next!=null) { if(prev.element > 3) { prev = curr; curr = curr.next; } else break; } head = prev.next; Question 3 options: 3 2 4 1...
from __future__ import annotations from typing import Any, Optional class _Node: """A node in a linked list. Note that this is considered a "private class", one which is only meant to be used in this module by the LinkedList class, but not by client code. === Attributes === item: The data stored in this node. next: The next node in the list, or None if there are no more nodes. """ item: Any next: Optional[_Node] def __init__(self, item: Any) ->...
solve this Q in java languege Write a method that return DoublyLinkedList as reversed string For example: If the elements of a list is 1, 2, 3, 4, 5, 6 the reverse string should be 6, 5, 4, 3, 2, 1 implement reverse method you have two steps: 1- you should start traversing from the last element of DoublyLinkedList (the previous of the trailer) 2- you should add the element inside each node to string don't forget the space in...