/** * This class will use Nodes to form a linked list. It implements the LIFO * (Last In First Out) methodology to reverse the input string. * **/ public class LLStack { private Node head; // Constructor with no parameters for outer class public LLStack( ) { // to do } // This is an inner class specifically utilized for LLStack class, // thus no setter or getters are needed private class Node { private Object data; private Node next; // Constructor with no parameters for inner class public Node(){ // to do // to do } // Parametrized constructor for inner class public Node (Object newData, Node nextLink) { // to do: Data part of Node is an Object // to do: Link to next node is a type Node } } // Adds a node as the first node element at the start of the list with the specified data. public void addToStart(Object itemData) { // to do // NOTE: the logic here could be implemented in a single line, // but not required to be a one liner. } // Removes the head node and returns the data Object being // deleted. // Returns null if the list is empty. public Object deleteHead( ) { // to do } // Returns the size of linked list by traversing the list public int size( ) { // to do } return count; } // Finds if there is match for the given object public boolean contains(Object item) { // to do } // Finds the first node containing the target item, and returns a // reference to that node. Return null if target not found. private Node findData(Object target) { Node current = head; Object itemAtPosition; while (current != null) { itemAtPosition = current.data; if (itemAtPosition.equals(target)) return current; current = current.next; } return null; // Target not found! } public void outputList( ) { Node current = head; while (current != null) { System.out.println(current.data); current = current.next; } } public String toString() { String retValue = ""; Node current = head; while(current != null) { retValue += current.data.toString() + " "; current = current.next; } return retValue; } public boolean isEmpty( ) { // to do } public void clear( ) { // to do } // For two lists to be equal they must contain the same data items in // the same order. The equals method of T is used to compare data items. public boolean equals(Object otherObject) { if (otherObject == null) return false; else if(!(otherObject instanceof LLStack)) return false; else { LLStack otherList = (LLStack)otherObject; if (size( )!= otherList.size( )) return false; Node position = head; Node otherPosition = otherList.head; while (position != null) { if (!(position.data.equals(otherPosition.data))) return false; position = position.next; otherPosition = otherPosition.next; } return true; // objects are the same } }
Types of Linked List
A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.
Linked List
When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).
/**
* This class will use Nodes to form a linked list. It implements the LIFO
* (Last In First Out) methodology to reverse the input string.
*
**/
public class LLStack {
private Node head;
// Constructor with no parameters for outer class
public LLStack( ) {
// to do
}
// This is an inner class specifically utilized for LLStack class,
// thus no setter or getters are needed
private class Node {
private Object data;
private Node next;
// Constructor with no parameters for inner class
public Node(){
// to do
// to do
}
// Parametrized constructor for inner class
public Node (Object newData, Node nextLink) {
// to do: Data part of Node is an Object
// to do: Link to next node is a type Node
}
}
// Adds a node as the first node element at the start of the list with the specified data.
public void addToStart(Object itemData) {
// to do
// NOTE: the logic here could be implemented in a single line,
// but not required to be a one liner.
}
// Removes the head node and returns the data Object being
// deleted.
// Returns null if the list is empty.
public Object deleteHead( ) {
// to do
}
// Returns the size of linked list by traversing the list
public int size( ) {
// to do
}
return count;
}
// Finds if there is match for the given object
public boolean contains(Object item) {
// to do
}
// Finds the first node containing the target item, and returns a
// reference to that node. Return null if target not found.
private Node findData(Object target) {
Node current = head;
Object itemAtPosition;
while (current != null) {
itemAtPosition = current.data;
if (itemAtPosition.equals(target))
return current;
current = current.next;
}
return null; // Target not found!
}
public void outputList( ) {
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
public String toString() {
String retValue = "";
Node current = head;
while(current != null) {
retValue += current.data.toString() + " ";
current = current.next;
}
return retValue;
}
public boolean isEmpty( ) {
// to do
}
public void clear( ) {
// to do
}
// For two lists to be equal they must contain the same data items in
// the same order. The equals method of T is used to compare data items.
public boolean equals(Object otherObject) {
if (otherObject == null)
return false;
else if(!(otherObject instanceof LLStack))
return false;
else {
LLStack otherList = (LLStack)otherObject;
if (size( )!= otherList.size( ))
return false;
Node position = head;
Node otherPosition = otherList.head;
while (position != null) {
if (!(position.data.equals(otherPosition.data)))
return false;
position = position.next;
otherPosition = otherPosition.next;
}
return true; // objects are the same
}
}
Here, I have to provide a complete solution to the above-given program.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
