Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Jace Zavarelli
- // 4/7/2020
- // This is the Linked List Program that is used throughout many of the other assignments: such as Stacks and Queue's
- class LinkedList
- {
- //reference to the head node.
- private Node head;
- private int listCount;
- //LinkedList constructor
- public LinkedList()
- {
- //this is an empty list, so the reference to the head node is set to a new node with no data
- head = new Node(null);
- listCount = 0;
- }
- public void add(Object data)
- {
- //appends the specified element to the end of this list.
- Node temp = new Node(data);
- Node current = head;
- //starting at the head node, crawl to the end of the list,
- while(current.getNext() != null)
- {
- current = current.getNext();
- }
- //The last node's "next" reference set to our new node
- current.setNext(temp);
- //increment the number of elements variable
- listCount++;
- }
- public void add(Object data, int index)
- {
- //inserts the specified element at the specified position in this list.
- Node temp = new Node(data);
- Node current = head;
- //crawl to the requested index or the last element in the list, whichever comes first
- for(int i = 1; i < index && current.getNext() != null; ++i)
- {
- current = current.getNext();
- }
- //Set the new node's next-node reference to this node's next-node reference
- temp.setNext(current.getNext());
- //Now set this node's next-node reference to the new node
- current.setNext(temp);
- //increment the number of elements variable
- listCount++;
- }
- public Object get(int index)
- {
- //returns the element at the specified position in this list.
- //index must be 1 or higher
- if(index <= 0)
- return null;
- Node current = head.getNext();
- for(int i = 1; i < index; i++)
- {
- if(current.getNext() == null)
- return null;
- current = current.getNext();
- }
- return current.getData();
- }
- public boolean remove(int index)
- {
- //removes element at specified position in list.
- //if index out of range, exit
- if(index < 1 || index > size())
- return false;
- Node current = head;
- for(int i = 1; i < index; ++i)
- {
- if(current.getNext() == null)
- return false;
- current = current.getNext();
- }
- current.setNext(current.getNext().getNext());
- //decrement the number of elements variable
- listCount--;
- return true;
- }
- public int size()
- {
- return listCount;
- }
- public String toString()
- {
- Node current = head.getNext();
- String output = "";
- while(current != null)
- {
- output += "[" + current.getData().toString() + "]";
- current = current.getNext();
- }
- return output;
- }
- private class Node
- {
- //reference to the next Node in the chain, or null if there isn't one.
- Node next;
- //Data carried by this node could be of any type you need.
- Object data;
- //Node Constructor
- public Node(Object _data)
- {
- next = null;
- data = _data;
- }
- @SuppressWarnings("unused")
- public Node(Object _data, Node _next)
- {
- next = _next;
- data = _data;
- }
- public Object getData()
- {
- return data;
- }
- @SuppressWarnings("unused")
- public void setData(Object _data)
- {
- data = _data;
- }
- public Node getNext()
- {
- return next;
- }
- public void setNext(Node _next)
- {
- next = _next;
- }
- }
- }
- // This is the QUEUE class and assignment for Queue's@h@
- public class Queue
- {
- private LinkedList list;
- //Queue Constructor
- public Queue()
- {
- //Create a new LinkedList;
- list = new LinkedList();
- }
- public boolean isEmpty()
- {
- //Post: Returns true if the queue is empty. Otherwise it is false.
- return(list.size() == 0);
- }
- public void enqueue(Object item)
- {
- //Post: An item is added to the back of the queue.
- //Append the item to the end of our linked list.
- list.add(item);
- }
- public Object dequeue()
- {
- //Preview: this.isEmpty() == false
- //Post: The item at the front of the queue is returned and deleted from the queue.
- // Returns null if precondition not met.
- //Store a reference to the item at the front of the queue so that it does not get garbage
- // collected when we remove it from the list.
- //Note: list.get(...) returns null if item not found at specified index. See postcondition.
- Object item = list.get(1);
- //Remove the item from the list. My implementation of the linked list is based on the J2SE API
- // reference. In both, elements start at 1, unlike arrays which start at 0.
- list.remove(1);
- //return item
- return item;
- }
- public Object peek()
- {
- //Preview: this.isEmpty() == false
- //Post: The item at the front of the queue is returned and deleted from the queue.
- // Returns null if precondition not met.
- //This method is very similar to dequeue(). See Queue.dequeue() for comments.
- return list.get(1);
- }
- }
- // This goes along with the QUEUE class and is used to accompany the Queue's assignment@h@
- public class Person
- {
- String name;
- //Person Constructor
- public Person(String _name)
- {
- //Post: An instance of Person is initialized.
- //Set the name of this person object to the name passed into the constructor.
- name = _name;
- }
- public String getName()
- {
- //Post: The name of this person is returned.
- return name;
- }
- //End of Person Class
- }
- // This is the code for STACKS or for the Stack Assignment@h@
- import java.util.LinkedList;
- public class Stack
- {
- private LinkedList<Object> list;
- //Stack Constructor
- public Stack()
- {
- //Create a new LinkedList
- list = new LinkedList<Object>();
- }
- public boolean isEmpty()
- {
- //Post: Returns true if the stack is empty. Otherwise it is false;
- return(list.size() == 0);
- }
- public void push(Object item)
- {
- //Post: An item is added to the back of the stack
- //Append the item to the end of our linked list.
- list.add(item);
- }
- public Object pop()
- {
- //Pre: this.isEmpthy() == false
- //Post:The item at the front of the stack is returned and deleted from the stack.
- // Returns null if precondition not met.
- //Store a reference to the item at the front of the stack so that it does not get garbage
- // collected when we remove it from the list.
- //Note: list.get(...) returns null if item not found at specified index. See Postconditions.
- Object item = list.get(list.size());
- //Remove the item from the list.
- //My implementation of the linked list is based on the J2SE API reference. In both, elements
- // start at 1, unlike arrays which start at 0.
- list.remove(list.size());
- //return item
- return item;
- }
- public Object peek()
- {
- //Pre: this.isEmpthy() == false
- //Post:The item at the front of the stack is returned and deleted from the stack.
- // Returns null if precondition not met.
- //This method is very similar to pop(). See Stack.pop() for comments.
- return list.get(list.size());
- }
- }
- // This is Indexed List, an Interface, which is used in SLIndexed List@h@
- public interface IndexedList
- {
- public void add(int index, Object obj);
- public Object get(int index);
- public boolean isEmpty();
- public boolean isFull();
- public Object remove(int index);
- public Object set(int index, Object obj);
- public int size();
- public String toString();
- }
- // This is SLIndexed List@h@
- import java.io.*; //for Serialization
- import javax.swing.*;
- import java.util.*; //for ListIterator
- @SuppressWarnings("unused")
- public class SLIndexedListCode implements IndexedList, Serializable
- {
- private static final long serialVersionUID = 1L;
- private Node head; //pointer to first node
- private int listSize; //list size
- private Node nodeAtIndex; //The node at index position or null if past the end of the list
- private Node nodeBefore; //The node before index position or null if before the beginning of the list
- @SuppressWarnings("unused")
- private static Node pointer;
- public SLIndexedListCode()
- {
- head = new Node("!", null);
- head = new Node("ball", head);
- head = new Node("the", head);
- head = new Node("Throw", head);
- listSize = 4;
- }
- public void add(int index, Object obj)
- {
- if(index < 0 || index >= listSize)
- {
- throw new RuntimeException("Index =" + index + " is out of the list bounds");
- }
- if(index == 0)
- {
- head = new Node(obj, head);
- }
- else
- {
- locateNode(index);
- nodeBefore.next = new Node(obj, nodeAtIndex);
- }
- listSize++;
- }
- public boolean isEmpty()
- {
- return listSize == 0;
- }
- public boolean isFull()
- {
- return false;
- }
- public Object get(int index)
- {
- if(index < 0 || index >= listSize)
- {
- throw new RuntimeException("Index = " + index + " is out of the list bounds");
- }
- locateNode(index);
- return nodeAtIndex.value;
- }
- public Object remove(int index)
- {
- if(index < 0 || index >= listSize)
- {
- throw new RuntimeException("Index = " + index + " is out of the list bounds");
- }
- Object removedObj = null;
- if(index == 0)
- {
- removedObj = head.value;
- head = head.next;
- }
- else
- {
- locateNode(index);
- nodeBefore.next = nodeAtIndex.next;
- removedObj = nodeAtIndex.value;
- }
- listSize--;
- return removedObj;
- }
- public Object set(int index, Object obj)
- {
- Object replacedObj = null;
- try
- {
- if(index == 0)
- {
- replacedObj = head.value;
- head.value = obj;
- }
- else
- {
- locateNode(index);
- replacedObj = nodeAtIndex.value;
- nodeAtIndex.value = obj;
- }
- }
- catch(RuntimeException e)
- {
- JOptionPane.showMessageDialog(null, "Index = " + index + " is out of the list bounds",
- "Out of Bounds Error", JOptionPane.ERROR_MESSAGE);
- }
- return replacedObj;
- }
- public int size()
- {
- return listSize;
- }
- public String toString()
- {
- String message = "";
- for(Node pointer = head; pointer != null; pointer = pointer.next)
- {
- message += pointer.value + " ";
- }
- return message;
- }
- private void locateNode(int index)
- {
- nodeBefore = null;
- nodeAtIndex = head;
- for(int i = 1; i < listSize && i <= index; i++)
- {
- nodeBefore = nodeAtIndex;
- nodeAtIndex = nodeAtIndex.next;
- }
- if(index == listSize)
- {
- nodeBefore = nodeAtIndex;
- nodeAtIndex = null;
- }
- }
- private class Node
- {
- private Object value;
- private Node next;
- private Node()
- {
- value = null;
- next = null;
- }
- private Node(Object value, Node next)
- {
- this.value = value;
- this.next = next;
- }
- }
- public static void main(String[] args)
- {
- SLIndexedListCode list = new SLIndexedListCode(); // 1) Singly Linked List
- pointer = list.head; // 2) Sets point to the head of list
- list.add(2, "yellow"); // 4.1) Sets the 3rd node( 2nd Index ) to the string yellow
- list.set(2, "blue"); // 5) Changes 3rd node to blue
- list.remove(3); // 6) removed 4th node ( 3rd Index ) of the list
- list.set(4, "Football"); // 8.2) Should return as error when active. The If statement will show list size in the program.
- if(list.size() < 5)
- {
- System.out.println("The List Size is " + list.size());
- System.out.println();
- }
- for(int i = 0; i < 4; i++) // 3.1) For Loop that shows the list
- {
- list.toString(); // 4.2) Uses to string to add the yellow string to the phrase
- System.out.println(list.get(i)); // 3.2) String prints out each part of looped list
- }
- if(list.isEmpty()) // 8.1) If the list is empty it will show in this if statement
- {
- System.out.println();
- System.out.println("The List is Empty");
- }
- else
- {
- System.out.println();
- System.out.println("The List is Not Empty");
- }
- }
- }
- // This is the program DLPositionalListCode@h@
- import java.util.*; //for ListIterator
- import java.io.*; //for Serialization
- import javax.swing.*; //for JOptionPane
- public class DLPositionalListCode implements ListIterator<Object>, Serializable
- {
- private static final long serialVersionUID = 1L;
- private Node head;
- private Node curPos;
- private Node lastItemPos;
- private int listSize;
- private String removeItem;
- public DLPositionalListCode()
- {
- head = new Node(null, null, null);
- head.next = head;
- head.previous = head;
- curPos = head;
- lastItemPos = null;
- listSize = 0;
- }
- //LIST ITERATOR METHODS
- //Inserts the specified element into the list (Optional Operation).
- public void add(Object obj)
- {
- //create new node for object
- Node newNode = new Node(obj, curPos.previous, curPos);
- //sets newNode.previous to last item in list and newNode.next to head that points at first item
- curPos.previous.next = newNode; //sets last item's next to newNode
- curPos.previous = newNode; //sets head's previous to new node
- listSize++;
- lastItemPos = null;
- }
- //curPos points at head each time
- public void addAfter(Object obj)
- {
- //adds at end of linked list
- //create new node for object
- Node newNode = new Node(obj, curPos.previous, curPos);
- //sets newNode.previous to last item in list and newNode.next to head that points at first item
- curPos.previous.next = newNode; //sets last item's next to newNode
- curPos.previous = newNode; //sets head's previous to new node
- listSize++;
- lastItemPos = null;
- }
- //moves curPos to newest added node
- public void addAfter2(Object obj)
- {
- //adds at end of linked list
- //create new node for object
- Node newNode = new Node(obj, curPos, curPos.next);
- //sets newNode.previous to head and newNode.next to new 2nd item in list
- curPos.next = newNode; //sets next of node curPos is pointing to new Node
- newNode.next.previous = newNode; //sets head's previous to new node
- curPos = curPos.next;
- listSize++;
- lastItemPos = null;
- }
- //curPos points at head each time
- public void addBefore(Object obj)
- {
- //add at beginning of the list
- //create new node for object
- Node newNode = new Node(obj, curPos, curPos.next);
- //sets newNode.previous to head and newNode.next to new 2nd item in list
- curPos.next.previous = newNode; //sets 2nd item previous to newNode
- curPos.next = newNode; //points head.next to newNode
- listSize++;
- lastItemPos = null;
- }
- //curPos points to newest added node
- public void addBefore2(Object obj)
- {
- //add at beginning of the list
- //create new node for object
- Node newNode = new Node(obj, curPos.previous, curPos);
- //sets newNode.previous to left of curPos and newNode.next to curPos
- curPos.previous = newNode; //sets 2nd item in previous to newNode
- newNode.next.previous = newNode; //points the head.next to newNode
- curPos = curPos.previous;
- listSize++;
- lastItemPos = null;
- }
- //Returns true if this list iterator has more elements when traversing the list in the forward direction
- public boolean hasNext()
- {
- if(curPos.next == head)
- {
- return false;
- }
- else
- {
- return true;
- }
- }
- //Returns true if this list iterator has more elements when traversing the list in the reverse direction
- public boolean hasPrevious()
- {
- if(curPos.previous == head)
- {
- return false;
- }
- else
- {
- return true;
- }
- }
- //Returns the next element in the list
- public Object next()
- {
- if(!hasNext())
- {
- System.out.println("You are at the end of the list. The first item will be returned:");
- }
- curPos = curPos.next;
- return curPos.previous.value;
- }
- //Returns the index of the element that would be returned by a subsequent call to next
- public int nextIndex()
- {
- //(+1) to account for next
- return currentIndex() + 1;
- }
- //Returns the previous element in the list
- public Object previous()
- {
- if(!hasPrevious())
- {
- System.out.println("You are at the beginning of the list. The last item will be returned:");
- }
- //moves current position
- curPos = curPos.previous;
- return curPos.value;
- }
- //Returns the index of the element that would be returned by a subsequent call to previous
- public int previousIndex()
- {
- //(-1) to account for previous
- return currentIndex() - 1;
- }
- //Removes what curPos is point to and moves curPos to previous
- public void remove()
- {
- lastItemPos = curPos;
- curPos = curPos.previous;
- curPos.next = lastItemPos.next;
- lastItemPos.next.previous = curPos;
- listSize--;
- }
- //prompts user for the value to be removed
- public void remove2()
- {
- removeItem = JOptionPane.showInputDialog("Input the object you would like to remove.");
- curPos = head.next;
- while(curPos != head && !curPos.value.toString().equals(removeItem))
- {
- if(curPos.next == head)
- {
- System.out.println("The item couldn't be found.\n");
- curPos = head;
- }
- else
- {
- next();
- }
- }
- if(curPos != head)
- {
- remove();
- }
- }
- //Replaces what curPos is pointing to
- public void set(Object obj)
- {
- if(curPos == null)
- {
- throw new RuntimeException("There is no established item to set.");
- }
- curPos.value = obj;
- }
- //LIST ITERATOR METHOD END
- //Returns the current index of the element
- public int currentIndex()
- {
- int counter = 0;
- Node tempCurPos = new Node();
- if(!hasNext())
- {
- return -1;
- }
- else
- {
- tempCurPos.next = curPos;
- curPos = head.next;
- while(curPos != tempCurPos.next)
- {
- next();
- counter++;
- }
- curPos = tempCurPos.next;
- return counter;
- }
- }
- //returns number of elements in list
- public int size()
- {
- return listSize;
- }
- //creates a string from the contents of the list
- public String toString()
- {
- String str = " ";
- for(Node node = head.next; node != head; node = node.next)
- {
- str += node.value + " ";
- }
- return str;
- }
- //creates a string from something that was at the beginning of the list
- public String toBackwardString()
- {
- String str = "";
- for(Node node = head.previous; node != head; node = node.previous)
- {
- str += node.value + " ";
- }
- return str;
- }
- //private inner class for Node
- private class Node implements Serializable
- {
- private static final long serialVersionUID = 1L;
- private Object value;
- private Node next;
- private Node previous;
- private Node()
- {
- value = null;
- previous = null;
- next = null;
- }
- private Node(Object value)
- {
- this.value = value;
- previous = null;
- next = null;
- }
- private Node(Object value, Node previous, Node next)
- {
- this.value = value;
- this.previous = previous;
- this.next = next;
- }
- }
- public static void main(String[] args)
- {
- // 9) Doubly Linked List (Works)
- DLPositionalListCode list = new DLPositionalListCode();
- // 10) Printing previous, next, and size (Works)
- // System.out.println(list.listSize);
- // System.out.println(list.hasNext());
- // System.out.println(list.hasPrevious());
- //
- // System.out.println();
- //
- // 11) Sets the List to the letters of the alphabet
- char letter = 'a';
- for(int i = 0; i < 26; ++i)
- {
- String newStr = Character.toString(letter + i);
- list.add(newStr);
- }
- System.out.print(list.toString());
- System.out.println();
- System.out.println();
- // 12) Repeat step ten with filled list (Works)
- // System.out.println(list.listSize);
- // System.out.println(list.hasNext());
- // System.out.println(list.hasPrevious());
- // System.out.println();
- //
- // 13) Moving curPos to the previous node and return its value (Works)
- // list.previous();
- // System.out.println(list.previous());
- //
- // System.out.println();
- //
- // 14) Changing position to $ and printing (Works)
- // list.set("$");
- // System.out.println(list.toString());
- //
- //
- // System.out.println();
- //
- // 15) Print current value, current index, previous index, next index five elements back from position z\
- list.next();
- list.next();
- //Current Position = Z
- System.out.println(list.previous());
- list.previous();
- list.previous();
- list.previous();
- list.previous();
- list.previous();
- System.out.println();
- list.next();
- System.out.println(list.previous());
- System.out.println(list.currentIndex());
- System.out.println(list.previousIndex());
- System.out.println(list.nextIndex());
- //16) Removes Node at current position, the prints the list, list from end to start, size, and current value
- System.out.println();
- list.next();
- System.out.println(list.previous());
- list.remove();
- System.out.println(list.previous());
- System.out.println(list.toString());
- System.out.println();
- while(list.currentIndex() != 0)
- {
- list.previous();
- }
- //I wanted to check is there a reason for not just having a method that just calls the current position,
- //Or why do we not have something to call the list at a specific index.
- for(int i = 0; i < 26; ++i)
- {
- System.out.print(list.previous() + "|");
- }
- //17) Repeats 16 but ask what is wanted to be removed (Works)
- // System.out.println();
- //
- // System.out.println();
- // list.next();
- // System.out.println(list.previous());
- // list.remove2();
- // System.out.println(list.previous());
- // System.out.println(list.toString());
- // System.out.println();
- //
- // while(list.currentIndex() != 0)
- // {
- // list.next();
- // }
- //
- // for(int i = 0; i < 26; ++i)
- // {
- // System.out.print(list.previous());
- // System.out.println();
- // }
- //
- System.out.println();
- //18) Start at the beginning of the list and set all values to "*" then print
- System.out.println();
- for(int i = 0; i < 26; ++i)
- {
- list.set("*");
- list.next();
- }
- System.out.print(list.toString());
- System.out.println();
- System.out.println();
- //19) Spells Happy Birthday to you in the list
- list.addAfter2("Happy ");
- list.addAfter2("Birthday ");
- list.addAfter2("to ");
- list.addAfter2("you ");
- System.out.println(list.toString());
- System.out.println(list.toBackwardString());
- System.out.println();
- System.out.println();
- //20) Repeat 19 with addAfter 2 , addBefore2, and addBefore
- list.addAfter2("Happy ");
- list.addAfter2("Birthday ");
- list.addAfter2("to ");
- list.addAfter2("you ");
- System.out.println(list.toString());
- System.out.println(list.toBackwardString());
- System.out.println();
- System.out.println();
- list.addBefore("Happy ");
- list.addBefore("Birthday ");
- list.addBefore("to ");
- list.addBefore("you ");
- System.out.println(list.toString());
- System.out.println(list.toBackwardString());
- System.out.println();
- System.out.println();
- list.addBefore2("Happy ");
- list.addBefore2("Birthday ");
- list.addBefore2("to ");
- list.addBefore2("you ");
- System.out.println(list.toString());
- System.out.println(list.toBackwardString());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement