Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- GENERAL TASK DESCRIPTION
- Implement barebones (meaning - no getters/setters, or anything extraneous
- In task descriptions after data structure name the required interface (list of public methods) is in parentheses
- Use proper formatting. Implement each data structure in a separate class. For Node classes use inner classes.
- For brevity use primitive integer as value type (no generics).
- */
- // Task 1 - singly-linked list (add, get, remove) add(), get(i), remove(i), remove(O)
- // Task 2 - stack (push, pop)
- // Task 3 - queue (offer, poll)
- // Task 4 - flexible-size list (using arrays - think of ArrayList) - (add, get, remove, insert)
- class LinkedList {
- private int size;
- private Node baseNode, last;
- public void add(Integer value) {
- Node node = new Node(value, null);
- if (baseNode == null) {
- baseNode = node;
- }
- else {
- last.next = node;
- }
- last = node;
- ++size;
- }
- public Integer get(int idx) { // get should return the value, not the node
- if (idx < 0 || idx >= size)
- throw new IndexOutOfBoundsException();
- if (idx == size - 1)
- return last.value;
- Node node = baseNode;
- for (int i = 0; i < idx; i++)
- node = node.next;
- return node.value;
- }
- public void remove(int idx) {
- if (idx < 0 || idx >= size)
- throw new IndexOutOfBoundsException();
- if (idx == 0)
- {
- baseNode = baseNode.next;
- size--;
- return;
- }
- Node node = baseNode;
- for (int i = 1; i < idx; i++)
- {
- node = node.next;
- }
- if (idx == size - 1)
- last = node;
- node.next = node.next.next;
- size--;
- }
- // My mistake - use Integer for values, so there'll be no collision in case of remove
- public void remove(Integer value) {
- if (baseNode == null)
- return;
- if (Objects.equals(baseNode.value, value)) {
- baseNode = baseNode.next;
- if (baseNode == null)
- last = null;
- size--;
- return;
- }
- Node node = baseNode;
- while (node.next != null && !Objects.equals(node.next.value, value)) { // Our values are objects now
- node = node.next;
- }
- if (node.next != null) {
- node.next = node.next.next;
- if (node.next == null)
- last = node;
- }
- }
- public void reverseAndPrint() {
- if (head == null)
- return;
- Node next = null, prev;
- Node curr = head;
- while (curr != null) {
- prev = curr.next;
- curr.next = next;
- next = curr;
- curr = prev;
- }
- Node temp = head;
- head = last;
- last = temp;
- Node tempNode = head;
- while (tempNode != null) {
- System.out.println(tempNode.value);
- tempNode = tempNode.next;
- }
- }
- static class Node {
- public Integer value;
- public Node next;
- Node(Integer value, Node next) {
- this.value = value;
- this.next = next;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement