Advertisement
ibragimova_mariam

singly-linked list + reverse

Dec 14th, 2020 (edited)
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.18 KB | None | 0 0
  1. /*
  2. GENERAL TASK DESCRIPTION
  3.  
  4. Implement barebones (meaning - no getters/setters, or anything extraneous
  5. In task descriptions after data structure name the required interface (list of public methods) is in parentheses
  6. Use proper formatting. Implement each data structure in a separate class. For Node classes use inner classes.
  7. For brevity use primitive integer as value type (no generics).
  8. */
  9.  
  10. // Task 1 - singly-linked list (add, get, remove) add(), get(i), remove(i), remove(O)
  11.  
  12. // Task 2 - stack (push, pop)
  13.  
  14. // Task 3 - queue (offer, poll)
  15.  
  16. // Task 4 - flexible-size list (using arrays - think of ArrayList) - (add, get, remove, insert)
  17.  
  18.  
  19. class LinkedList {
  20. private int size;
  21. private Node baseNode, last;
  22.  
  23. public void add(Integer value) {
  24. Node node = new Node(value, null);
  25. if (baseNode == null) {
  26. baseNode = node;
  27. }
  28. else {
  29. last.next = node;
  30. }
  31.  
  32. last = node;
  33. ++size;
  34. }
  35.  
  36. public Integer get(int idx) { // get should return the value, not the node
  37. if (idx < 0 || idx >= size)
  38. throw new IndexOutOfBoundsException();
  39.  
  40. if (idx == size - 1)
  41. return last.value;
  42.  
  43. Node node = baseNode;
  44. for (int i = 0; i < idx; i++)
  45. node = node.next;
  46.  
  47. return node.value;
  48. }
  49.  
  50. public void remove(int idx) {
  51. if (idx < 0 || idx >= size)
  52. throw new IndexOutOfBoundsException();
  53.  
  54. if (idx == 0)
  55. {
  56. baseNode = baseNode.next;
  57. size--;
  58. return;
  59. }
  60.  
  61. Node node = baseNode;
  62. for (int i = 1; i < idx; i++)
  63. {
  64. node = node.next;
  65. }
  66.  
  67. if (idx == size - 1)
  68. last = node;
  69.  
  70. node.next = node.next.next;
  71. size--;
  72. }
  73.  
  74. // My mistake - use Integer for values, so there'll be no collision in case of remove
  75. public void remove(Integer value) {
  76.  
  77. if (baseNode == null)
  78. return;
  79.  
  80. if (Objects.equals(baseNode.value, value)) {
  81. baseNode = baseNode.next;
  82. if (baseNode == null)
  83. last = null;
  84. size--;
  85. return;
  86. }
  87.  
  88. Node node = baseNode;
  89. while (node.next != null && !Objects.equals(node.next.value, value)) { // Our values are objects now
  90. node = node.next;
  91. }
  92.  
  93. if (node.next != null) {
  94. node.next = node.next.next;
  95. if (node.next == null)
  96. last = node;
  97. }
  98. }
  99.  
  100.  
  101. public void reverseAndPrint() {
  102. if (head == null)
  103. return;
  104.  
  105. Node next = null, prev;
  106. Node curr = head;
  107. while (curr != null) {
  108. prev = curr.next;
  109. curr.next = next;
  110. next = curr;
  111. curr = prev;
  112. }
  113.  
  114. Node temp = head;
  115. head = last;
  116. last = temp;
  117.  
  118. Node tempNode = head;
  119. while (tempNode != null) {
  120. System.out.println(tempNode.value);
  121. tempNode = tempNode.next;
  122. }
  123. }
  124.  
  125. static class Node {
  126. public Integer value;
  127. public Node next;
  128.  
  129. Node(Integer value, Node next) {
  130. this.value = value;
  131. this.next = next;
  132. }
  133. }
  134.  
  135. }
  136.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement