# Moving character efficiently on a row

Given input `(items = 6, position = 3)`

creates a row of `6 items` and a character positioned on `item 3` `{0,1,2,[3],4,5}`

A call to `left()` moves the character two positions to the left and the `item at position 3 is removed` `{0,[1],2,4,5}`

The next call to `right()` moves the character two positions to the right and the `item at position 1 is removed` `{0,2,[4],5}`

Then calling `position()` method now should return `4`.

The character will not move to the left or right if no items are present so no need to implement that.

```public class MyClass {
int position;
int[] items;
public MyClass(int n, int position) {
this.position = position;
items = new int[n];
for(int i=0; i<n; i++) {
items[i] = i;
}
}
}

public void left() {
int p = this.position;
items[p] = -1;
for(int z=0; z<2;) {
p--;
int value = arr[p];
if(value != -1) {
z++;
}
}
this.position = p;
}

public void right() {
int p = this.position;
items[p] = -1;
for(int z=0; z<2;) {
p++;
int value = arr[p];
if(value != -1) {
z++;
}
}
this.position = p;
}

public int position() {
return arr[position];
}
```

This code works perfectly for small inputs, but I am getting performance errors when the input is large.

How to implement this efficiently? I don’t have test case details for the error related to performance errors.

As it already has been pointed outed both in the comments and the answer by @AbhinavMathur, in order to improve performance you need to implement Doubly linked list data structure.

Note that it’s mandatory to create your own implementation that will maintain a reference to the current node. Attempt to utilize an implementation built-in in the JDK in place of the `items` array will not buy you anything because the advantage of the fast deletion will be nullified by the cost of iteration (in order to reach the element at position `n`, `LinkedList` needs to crawl through the `n` elements starting from the head, and this operation has a liner time complexity).

Methods `left()`, `right()` and `position()` will have the following outcome:

• `left()` – in case when the previous node (denoted as `prev` in the code) associated with `current` is not `null`, and in tern its previous node exists, the current node will be dereferenced (i.e. next and previous nodes associated with the `current` node will be linked with each other), and the variable `current` would be assigned to the `prev` of the previous node, i.e. `current.prev.prev`. Time complexity O(1).

• `right()` – in case when the next node (denoted as `next` in the code) associated with `current` is not `null`, and in tern its next node exists, the current node will be dereferenced in a way that has been described above, and the variable `current` would be assigned to the `next` of the next node, i.e. `current.next.next`. Time complexity O(1).

• `position()` – will return a value of the `current` node. Time complexity O(1).

That’s how it might look like:

```public class MyClass {
private Node current; // a replacement for both position and items fields

public MyClass(int n, int position) {
Node current = new Node(0, null, null); // initialing the head node
if (position == 0) {
this.current = current;
}

for (int i = 1; i < n; i++) { // initialing the rest past of the linked list
Node nextNode = new Node(i, current, null);
current.setNext(nextNode);
current = nextNode;

if (position == i) {
this.current = current;
}
}
}

public void left() { // removes the current node and sets the current to the node 2 position to the left (`prev` of the `prev` node)
if (current.prev == null || current.prev.prev == null) {
return;
}

Node prev = current.prev;
Node next = current.next;
prev.setNext(next);
next.setPrev(prev);
this.current = prev.prev;
}

public void right() { // removes the current node and sets the current to the node 2 position to the right (`next` of the `next` node)
if (current.next == null || current.next.next == null) {
return;
}

Node prev = current.prev;
Node next = current.next;
prev.setNext(next);
next.setPrev(prev);
this.current = next.next;
}

public int position() {
return current.getValue();
}

public static class Node {
private int value;
private Node prev;
private Node next;

public Node(int value, Node prev, Node next) {
this.value = value;
this.prev = prev;
this.next = next;
}

// getters and setters
}
}
```