JetBrains Academy: Doubly linked list in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Simple doubly linked list:
There are 5 types of commands given: add an element to the beginning and to the end, remove from the beginning and the end, and reverse the list. Your task is to print the resulting list.
Input: In the first line, N < 1000 is the number of commands. In the following N lines, there are commands:
- addFirst x;
- addLast x;
- removeFirst;
- removeLast;
- reverse.
It is guaranteed that removal operation is not called for an empty list.
Output: in the first line print the resulting list divided by spaces.
import java.util.NoSuchElementException;
import java.io.*;
class Main {
public static void main(String[] args) {
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
int lines = Integer.parseInt(reader.readLine());
for (int i = 0; i < lines; i++) {
String[] line = reader.readLine().split("\\s+");
String command = line[0];
String parameter = line.length > 1 ? line[1] : "";
switch (command) {
case "addFirst":
list.addFirst(Integer.parseInt(parameter));
break;
case "addLast":
list.addLast(Integer.parseInt(parameter));
break;
case "removeFirst":
list.removeFirst();
break;
case "removeLast":
list.removeLast();
break;
case "reverse":
list.reverse();
break;
default:
System.out.println("Wrong command provided. Provide:");
System.out.println("addFirst x;\n" +
"addLast x;\n" +
"removeFirst;\n" +
"removeLast;\n" +
"reverse");
break;
}
}
System.out.println(list.toString());
} catch (IOException e) {
e.printStackTrace();
}
}
}
class DoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public DoublyLinkedList() {
size = 0;
}
public Node<E> getHead() {
return head;
}
public Node<E> getTail() {
return tail;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* Method adds element at the head of doubly linked list.
*
* @param elem - element to be added
*/
public void addFirst(E elem) {
Node<E> tmp = new Node<>(elem, head, null);
if (head != null) {
head.prev = tmp;
}
head = tmp;
if (tail == null) {
tail = tmp;
}
size++;
}
/**
* Method adds element at the tail of doubly linked list.
*
* @param elem - element to be added
*/
public void addLast(E elem) {
Node<E> tmp = new Node<>(elem, null, tail);
if (tail != null) {
tail.next = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
}
/**
* Method adds element before defined node.
*
* @param elem - element to be added
* @param curr - current node before which we want to insert 'elem'
*/
public void add(E elem, Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
Node<E> tmp = new Node<>(elem, curr, null);
if (curr.prev == null) { // curr is the head
curr.prev = tmp;
tmp.next = curr;
head = tmp;
} else { // curr is not the head
curr.prev.next = tmp;
tmp.prev = curr.prev;
curr.prev = tmp;
}
size++;
}
/**
* Method removes first element of doubly linked list.
*/
public void removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = null;
}
size--;
}
/**
* Method removes last element of doubly linked list.
*/
public void removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = tail.prev;
if (tail == null) {
head = null;
} else {
tail.next = null;
}
size--;
}
/**
* Method removes indicated node.
*
* @param curr - node to be removed
*/
public void remove(Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
if (curr.prev == null) {
removeFirst();
return;
}
if (curr.next == null) {
removeLast();
return;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
size--;
}
@Override
public String toString() {
Node<E> tmp = head;
StringBuilder result = new StringBuilder();
while (tmp != null) {
result.append(tmp.value).append(" ");
tmp = tmp.next;
}
return result.toString();
}
/**
* Method reverse the order of doubly linked list.
* The list will be reversed after this call returns.
*/
public void reverse() {
Node<E> node;
Node<E> oldHead = head;
Node<E> oldTail = tail;
Node<E> current = head;
/* swap next and prev for all nodes of doubly linked list */
while (current != null) {
node = current.prev;
current.prev = current.next;
current.next = node;
current = current.prev;
}
/* swap first and last nodes of doubly linked list */
head = oldTail;
tail = oldHead;
}
public static class Node<E> {
private E value;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.value = element;
this.next = next;
this.prev = prev;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
}
}
or, without switch-case
:
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) {
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
int lines = Integer.parseInt(reader.readLine());
for (int i = 0; i < lines; i++) {
String[] line = reader.readLine().split("\\s+");
String command = line[0];
Integer value = line.length > 1 ? Integer.parseInt(line[1]) : null;
InputUtils.runFromString(command, value, list);
}
System.out.println(list.toString());
} catch (IOException e) {
e.printStackTrace();
}
}
}
class InputUtils {
public static <E> void runFromString(String command, E parameter, DoublyLinkedList<E> list) {
Command cmd = Command.getCommandFor(command);
run(Objects.requireNonNull(cmd), list, parameter);
}
private static <E> void run(Command command, DoublyLinkedList<E> list, E parameter) {
command.apply(list, parameter);
}
}
enum Command {
ADD_FIRST("addFirst") {
@Override
public <E> void apply(DoublyLinkedList<E> list, E parameter) {
list.addFirst(parameter);
}
}, ADD_LAST("addLast") {
@Override
public <E> void apply(DoublyLinkedList<E> list, E parameter) {
list.addLast(parameter);
}
}, REMOVE_FIRST("removeFirst") {
@Override
public <E> void apply(DoublyLinkedList<E> list, E parameter) {
list.removeFirst();
}
}, REMOVE_LAST("removeLast") {
@Override
public <E> void apply(DoublyLinkedList<E> list, E parameter) {
list.removeLast();
}
}, REVERSE("reverse") {
@Override
public <E> void apply(DoublyLinkedList<E> list, E parameter) {
list.reverse();
}
};
private final String command;
Command(String command) {
this.command = command;
}
public static Command getCommandFor(String value) {
for (Command name : values()) {
if (name.command.equals(value)) {
return name;
}
}
throw new IllegalArgumentException("Wrong command provided: " + value + "\n" +
"Please use following: addFirst / addLast / removeFirst / removeLast / reverse");
}
public abstract <E> void apply(DoublyLinkedList<E> list, E parameter);
}
class DoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public DoublyLinkedList() {
size = 0;
}
public Node<E> getHead() {
return head;
}
public Node<E> getTail() {
return tail;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* Method adds element at the head of doubly linked list.
*
* @param elem - element to be added
*/
public void addFirst(E elem) {
Node<E> tmp = new Node<>(elem, head, null);
if (head != null) {
head.prev = tmp;
}
head = tmp;
if (tail == null) {
tail = tmp;
}
size++;
}
/**
* Method adds element at the tail of doubly linked list.
*
* @param elem - element to be added
*/
public void addLast(E elem) {
Node<E> tmp = new Node<>(elem, null, tail);
if (tail != null) {
tail.next = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
}
/**
* Method adds element before defined node.
*
* @param elem - element to be added
* @param curr - current node before which we want to insert 'elem'
*/
public void add(E elem, Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
Node<E> tmp = new Node<>(elem, curr, null);
if (curr.prev == null) { // curr is the head
curr.prev = tmp;
tmp.next = curr;
head = tmp;
} else { // curr is not the head
curr.prev.next = tmp;
tmp.prev = curr.prev;
curr.prev = tmp;
}
size++;
}
/**
* Method removes first element of doubly linked list.
*/
public void removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = null;
}
size--;
}
/**
* Method removes last element of doubly linked list.
*/
public void removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = tail.prev;
if (tail == null) {
head = null;
} else {
tail.next = null;
}
size--;
}
/**
* Method removes indicated node.
*
* @param curr - node to be removed
*/
public void remove(Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
if (curr.prev == null) {
removeFirst();
return;
}
if (curr.next == null) {
removeLast();
return;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
size--;
}
@Override
public String toString() {
Node<E> tmp = head;
StringBuilder result = new StringBuilder();
while (tmp != null) {
result.append(tmp.value).append(" ");
tmp = tmp.next;
}
return result.toString();
}
/**
* Method reverse the order of doubly linked list.
* The list will be reversed after this call returns.
*/
public void reverse() {
Node<E> node;
Node<E> oldHead = head;
Node<E> oldTail = tail;
Node<E> current = head;
/* swap next and prev for all nodes of doubly linked list */
while (current != null) {
node = current.prev;
current.prev = current.next;
current.next = node;
current = current.prev;
}
/* swap first and last nodes of doubly linked list */
head = oldTail;
tail = oldHead;
}
public static class Node<E> {
private E value;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.value = element;
this.next = next;
this.prev = prev;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
}
}
Double addition:
You receive whole numbers with absolute value not greater than 1000. You are to construct a list from them. The algorithm for creating the list is: first two elements are joined sequentially. The rest will be added either at the beginning or the end of the list: if the value is closer to the first element than the last one, it is added at the beginning, otherwise at the end. After inserting all the elements, print the resulting list. If the difference between element and head is equal to the difference between element and tail, then add it to the end of the list.
Input: in the first line is N, the number of elements. They are written in the next line divided by spaces.
Output: in the first line print the resulting list divided by spaces.
import java.util.*;
class Main {
public static void main(String[] args) {
DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
Scanner scanner = new Scanner(System.in);
int elements = Integer.parseInt(scanner.nextLine());
for (int i = 0; i < elements; i++) {
int value = scanner.nextInt();
if (i < 2) {
list.addLast(value);
} else {
InputUtils.doubleAddition(value, list);
}
}
System.out.println(list.toString());
}
}
class InputUtils {
/**
* Method adds elements to the list;
* If the value of element is closer to the first element than the last one, it is added at the beginning,
* otherwise at the end;
* If the difference between element and head is equal to the difference between element and tail,
* then add it to the end of the list.
*
* @param value - element to be added to the list
* @param list - DoublyLinkedList to which element will be added
*/
public static void doubleAddition(int value, DoublyLinkedList<Integer> list) {
int head = list.getHead().getValue();
int tail = list.getTail().getValue();
if (Math.abs(head - value) < Math.abs(tail - value)) {
list.addFirst(value);
} else {
list.addLast(value);
}
}
}
class DoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public DoublyLinkedList() {
size = 0;
}
public Node<E> getHead() {
return head;
}
public Node<E> getTail() {
return tail;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* Method adds element at the head of doubly linked list.
*
* @param elem - element to be added
*/
public void addFirst(E elem) {
Node<E> tmp = new Node<>(elem, head, null);
if (head != null) {
head.prev = tmp;
}
head = tmp;
if (tail == null) {
tail = tmp;
}
size++;
}
/**
* Method adds element at the tail of doubly linked list.
*
* @param elem - element to be added
*/
public void addLast(E elem) {
Node<E> tmp = new Node<>(elem, null, tail);
if (tail != null) {
tail.next = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
}
/**
* Method adds element before defined node.
*
* @param elem - element to be added
* @param curr - current node before which we want to insert 'elem'
*/
public void add(E elem, Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
Node<E> tmp = new Node<>(elem, curr, null);
if (curr.prev == null) { // curr is the head
curr.prev = tmp;
tmp.next = curr;
head = tmp;
} else { // curr is not the head
curr.prev.next = tmp;
tmp.prev = curr.prev;
curr.prev = tmp;
}
size++;
}
/**
* Method removes first element of doubly linked list.
*/
public void removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = null;
}
size--;
}
/**
* Method removes last element of doubly linked list.
*/
public void removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = tail.prev;
if (tail == null) {
head = null;
} else {
tail.next = null;
}
size--;
}
/**
* Method removes indicated node.
*
* @param curr - node to be removed
*/
public void remove(Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
if (curr.prev == null) {
removeFirst();
return;
}
if (curr.next == null) {
removeLast();
return;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
size--;
}
@Override
public String toString() {
Node<E> tmp = head;
StringBuilder result = new StringBuilder();
while (tmp != null) {
result.append(tmp.value).append(" ");
tmp = tmp.next;
}
return result.toString();
}
/**
* Method reverse the order of doubly linked list.
* The list will be reversed after this call returns.
*/
public void reverse() {
Node<E> node;
Node<E> oldHead = head;
Node<E> oldTail = tail;
Node<E> current = head;
/* swap next and prev for all nodes of doubly linked list */
while (current != null) {
node = current.prev;
current.prev = current.next;
current.next = node;
current = current.prev;
}
/* swap first and last nodes of doubly linked list */
head = oldTail;
tail = oldHead;
}
public static class Node<E> {
private E value;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.value = element;
this.next = next;
this.prev = prev;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
public E getValue() {
return value;
}
}
}
Cycled list:
The aim of this task is to slightly modify a doubly linked list and make a circular doubly linked list. It means that the previous element for the head is the tail and the next element for the tail is the head.
You are given a circular list. Initially, the main pointer is on the first element. You receive commands for removing elements at different distances to the left or the right from the current one. Next commands count from the place where an element was removed.
Input: In the first line divided by spaces are two numbers N < 1000 and K < 1000 – the number of elements in the list and the number of commands. In the second line divided by spaces is the list. In the following K lines are commands of two types:
- removes the element, which is on the right by ‘value’ elements;
- removes the element, which is on the left by ‘value’ elements.
Output: In the first line, print the resulting list after all removals. The first element must be to the left of all other elements of the resulting list in the initial list.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String delimiter = "\\s+";
String[] params = scanner.nextLine().split(delimiter);
int k = Integer.parseInt(params[1]);
CycledDoublyLinkedList<Integer> list = new CycledDoublyLinkedList<>();
String[] elements = scanner.nextLine().split(delimiter);
for (String elem : elements) {
list.addLast(Integer.parseInt(elem));
}
CycledDoublyLinkedList.Node<Integer> pointer = list.getHead();
for (int i = 0; i < k; i++) {
String[] line = scanner.nextLine().split(delimiter);
String command = line[0];
int value = Integer.parseInt(line[1]);
switch (command) {
case "r":
for (int j = 0; j < value % list.getSize(); j++) {
pointer = pointer.getNext();
}
list.remove(pointer);
pointer = pointer.getNext();
break;
case "l":
for (int j = 0; j < value % list.getSize(); j++) {
pointer = pointer.getPrev();
}
list.remove(pointer);
pointer = pointer.getPrev();
break;
default:
System.out.println("Wrong input");
break;
}
}
System.out.println(list.toString());
}
}
class CycledDoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public CycledDoublyLinkedList() {
size = 0;
}
public Node<E> getHead() {
return head;
}
public Node<E> getTail() {
return tail;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* Method adds element at the tail of doubly linked list.
*
* @param elem - element to be added
*/
public void addLast(E elem) {
Node<E> tmp = new Node<>(elem, head, tail);
if (tail != null) {
tail.next = tmp;
head.prev = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
}
/**
* Method removes first element of doubly linked list.
*/
public void removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = tail;
tail.next = head;
}
size--;
}
/**
* Method removes last element of doubly linked list.
*/
public void removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = tail.prev;
if (tail == null) {
head = null;
} else {
tail.next = head;
head.prev = tail;
}
size--;
}
/**
* Method removes indicated node.
*
* @param curr - node to be removed
*/
public void remove(Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
if (curr.equals(head)) {
removeFirst();
return;
}
if (curr.equals(tail)) {
removeLast();
return;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
size--;
}
@Override
public String toString() {
Node<E> tmp = head;
StringBuilder result = new StringBuilder();
for (int i = 0; i < size; i++) {
result.append(tmp.value).append(" ");
tmp = tmp.next;
}
return result.toString();
}
public static class Node<E> {
private E value;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.value = element;
this.next = next;
this.prev = prev;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
public E getValue() {
return value;
}
}
}
or, without switch-case
:
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String delimiter = "\\s+";
String[] params = scanner.nextLine().split(delimiter);
int lines = Integer.parseInt(params[1]);
String[] elements = scanner.nextLine().split(delimiter);
CycledDoublyLinkedList<Integer> list = InputUtils.asIntegerList(elements);
CycledDoublyLinkedList.Node<Integer> pointer = list.getHead();
for (int i = 0; i < lines; i++) {
String[] line = scanner.nextLine().split(delimiter);
String command = line[0];
int value = Integer.parseInt(line[1]);
pointer = InputUtils.execute(command, value, list, pointer);
}
System.out.println(list.toString());
}
}
class InputUtils {
public static CycledDoublyLinkedList<Integer> asIntegerList(String[] array) {
CycledDoublyLinkedList<Integer> list = new CycledDoublyLinkedList<>();
for (String elem : array) {
list.addLast(Integer.parseInt(elem));
}
return list;
}
/**
* Method analyzes provided direction and executes iteration by given value of steps;
* Then method removes pointed element and returns new pointer on element in the list;
* New pointer is next element in the list in case of RIGHT iteration
* and previous element in case of LEFT iteration.
*
* @param direction of iteration movement
* @param value - amount of steps for iteration
* @param list - CycledDoublyLinkedList to iterate on
* @param pointer - current pointer on the node in the list
* @param <E> - type of elements in the list
* @return pointer after operation
*/
public static <E> CycledDoublyLinkedList.Node<E> execute(String direction, int value, CycledDoublyLinkedList<E> list, CycledDoublyLinkedList.Node<E> pointer) {
Direction dir = Direction.getDirection(direction);
return dir.apply(list, value, pointer);
}
}
enum Direction {
RIGHT("r") {
@Override
public <E> CycledDoublyLinkedList.Node<E> apply(CycledDoublyLinkedList<E> list, int value, CycledDoublyLinkedList.Node<E> pointer) {
for (int j = 0; j < value % list.getSize(); j++) {
pointer = pointer.getNext();
}
list.remove(pointer);
return pointer.getNext();
}
}, LEFT("l") {
@Override
public <E> CycledDoublyLinkedList.Node<E> apply(CycledDoublyLinkedList<E> list, int value, CycledDoublyLinkedList.Node<E> pointer) {
for (int j = 0; j < value % list.getSize(); j++) {
pointer = pointer.getPrev();
}
list.remove(pointer);
return pointer.getPrev();
}
};
private final String direction;
Direction(String direction) {
this.direction = direction;
}
public static Direction getDirection(String input) {
for (Direction dir : values()) {
if (dir.direction.equals(input)) {
return dir;
}
}
throw new IllegalArgumentException("Wrong command provided: " + input + "\n" +
"Please use following: <r> for right / <l> for left>");
}
public abstract <E> CycledDoublyLinkedList.Node<E> apply(CycledDoublyLinkedList<E> list, int value, CycledDoublyLinkedList.Node<E> pointer);
}
class CycledDoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public CycledDoublyLinkedList() {
size = 0;
}
public Node<E> getHead() {
return head;
}
public Node<E> getTail() {
return tail;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* Method adds element at the tail of doubly linked list.
*
* @param elem - element to be added
*/
public void addLast(E elem) {
Node<E> tmp = new Node<>(elem, head, tail);
if (tail != null) {
tail.next = tmp;
head.prev = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
}
/**
* Method removes first element of doubly linked list.
*/
public void removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = tail;
tail.next = head;
}
size--;
}
/**
* Method removes last element of doubly linked list.
*/
public void removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = tail.prev;
if (tail == null) {
head = null;
} else {
tail.next = head;
head.prev = tail;
}
size--;
}
/**
* Method removes indicated node.
*
* @param curr - node to be removed
*/
public void remove(Node<E> curr) {
if (curr == null) {
throw new NoSuchElementException();
}
if (curr.equals(head)) {
removeFirst();
return;
}
if (curr.equals(tail)) {
removeLast();
return;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
size--;
}
@Override
public String toString() {
Node<E> tmp = head;
StringBuilder result = new StringBuilder();
for (int i = 0; i < size; i++) {
result.append(tmp.value).append(" ");
tmp = tmp.next;
}
return result.toString();
}
public static class Node<E> {
private E value;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.value = element;
this.next = next;
this.prev = prev;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
public E getValue() {
return value;
}
}
}
Rope:
You’re given a string with no more than 1000 Latin characters and the commands of two types:
- cut the string by given index and merge it back together in a different order. For example, given the index is 2 and the string is "example", first it is broken into "ex" and "ample", and then glued back again as "ampleex";
- reverse the whole string. If we reverse "example", we get "elpmaxe".
These commands may be performed multiple times. Your task is to print the resulting string after performing all operations.
Input: The first line is the given string. The second line is N – the number of commands. In the following N lines are commands:
split index
– split the string by index ‘index’ and invert the pieces;reverse
– reverse the string.
Output: Print the resulting string after all operations.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String word = scanner.nextLine();
int amountOfCommands = Integer.parseInt(scanner.nextLine());
CycledDoublyLinkedList<String> letters = InputUtils.splitToList(word);
for (int i = 0; i < amountOfCommands; i++) {
String line = scanner.nextLine();
InputUtils.runFromString(line, letters);
}
System.out.println(letters.toString());
}
}
class InputUtils {
/**
* This static fabric methods creates CycledDoublyLinkedList of letters as Strings from given String word.
*
* @param word - provided word to be split into letters and inserted into the list
* @return CycledDoublyLInkedList of String letters from given word
*/
public static CycledDoublyLinkedList<String> splitToList(String word) {
CycledDoublyLinkedList<String> list = new CycledDoublyLinkedList<>();
String[] array = word.split("");
for (String elem : array) {
list.addLast(elem);
}
return list;
}
/**
* Method analyzes provided String line and spilts it into command and parameter;
* for given String command it gets CycledCommand and runs apply method for cmd, with list and parameter arguments.
*
* @param line - line with arguments
* @param list - CycledDoublyLinkedList to be modified
* @param <E> - type of elements in the list
* @throws IllegalArgumentException - if command is not found
*/
public static <E> void runFromString(String line, CycledDoublyLinkedList<E> list) {
String[] arguments = line.split("\\s+");
String command = arguments[0];
int emptyParameter = -1;
int parameter = arguments.length > 1 ? Integer.parseInt(arguments[1]) : emptyParameter;
CycledCommand cmd = CycledCommand.getCommandFor(command);
cmd.apply(list, parameter);
}
}
enum CycledCommand {
REVERSE("reverse") {
@Override
public <E> void apply(CycledDoublyLinkedList<E> list, int parameter) {
list.reverse();
}
}, SPLIT("split") {
@Override
public <E> void apply(CycledDoublyLinkedList<E> list, int parameter) {
list.split(parameter);
}
};
private final String command;
CycledCommand(String command) {
this.command = command;
}
public static CycledCommand getCommandFor(String value) {
for (CycledCommand name : values()) {
if (name.command.equals(value)) {
return name;
}
}
throw new IllegalArgumentException("Wrong command provided: " + value + "\n" +
"Please use following: split X / reverse");
}
public abstract <E> void apply(CycledDoublyLinkedList<E> list, int parameter);
}
class CycledDoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public CycledDoublyLinkedList() {
size = 0;
}
public Node<E> getHead() {
return head;
}
public Node<E> getTail() {
return tail;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* Method adds element at the tail of doubly linked list.
*
* @param elem - element to be added
*/
public void addLast(E elem) {
Node<E> tmp = new Node<>(elem, head, tail);
if (tail != null) {
tail.next = tmp;
head.prev = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
}
/**
* Method reverse the order of cycled doubly linked list;
* The list will be reversed after this call returns.
*/
public void reverse() {
Node<E> node;
Node<E> oldHead = head;
Node<E> oldTail = tail;
Node<E> current = head;
/* swap next and prev for all nodes of list */
for (int i = 0; i < size; i++) {
node = current.prev;
current.prev = current.next;
current.next = node;
current = current.prev;
}
/* swap first and last nodes of list */
head = oldTail;
tail = oldHead;
}
/**
* Method splits the list at given index and swaps the parts;
* For example: "example".split(2) => "ex" + ""ample" => "ampleex"
*
* @param index - index pointing new head of the list
*/
public void split(int index) {
Node<E> pointer = this.head;
for (int i = 0; i < index; i++) {
pointer = pointer.getNext();
}
tail = pointer.getPrev();
head = pointer;
}
@Override
public String toString() {
Node<E> tmp = head;
StringBuilder result = new StringBuilder();
for (int i = 0; i < size; i++) {
result.append(tmp.value);
tmp = tmp.next;
}
return result.toString();
}
public static class Node<E> {
private final E value;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.value = element;
this.next = next;
this.prev = prev;
}
public Node<E> getNext() {
return next;
}
public Node<E> getPrev() {
return prev;
}
public E getValue() {
return value;
}
}
}