Is this system linear?
For linearity it is irrelevant if the output depends on future values. This only affects the system's causality. For linearity you just need to check whether the response to the signal

$$ax_1[n] + bx_2[n]$$

equals

$$ay_1[n] + by_2[n]$$

where $y_1[n]$ and $y_2[n]$ are the individual responses to inputs $x_1[n]$ and $x_2[n]$, respectively.

And of course you can write the input/output relation as

$$y[n+1] = -\frac12 x[n+2] - y[n]\tag{1}$$

I will now characterize all sequences that satisfy the recursion (1) for the specific input signal $x[n]=\delta[n]$. Applying the $\mathcal{Z}$-transform to (1) we get (with $X(z)=1$)

$$Y(z)=-\frac12\frac{z^2}{1+z}\tag{2}$$

The function $Y(z)$ corresponds to one left-sided sequence and to one right-sided sequence. Note that left-sided and right-sided doesn't necessarily mean anti-causal and causal, but it only means that $y(n)=0$ for $n&gt;N$ or for $n&lt;N$, respectively, for some positive or negative integer $N$. These two sequences are given by

$$y_{p1}[n]=\frac12 (-1)^{n}u(n+1)\tag{3}$$
and
$$y_{p2}[n]=-\frac12 (-1)^n u(-n-2)\tag{4}$$

Note that neither (3) nor (4) is causal. The sequences $y_{p1}[n]$ and $y_{p2}[n]$ are particular solutions of the difference equation (1) for $x[n]=\delta[n]$. They are in fact impulse responses of two different linear time-invariant (LTI) systems described by the difference equation (1). The impulse response $y_{p1}[n]$ was mentioned by Dilip Sarwate in a comment below, and something similar to $y_{p2}[n]$ was mentioned by Robert B.-J. I completely agree with them that the difference equation (1) describes an LTI system, if it is used to describe a system with either (3) or (4) as impulse response.

However, the sequences (3) and (4) are not the only sequences that satisfy (1). Looking at the homogeneous difference equation

$$y[n+1]=-y[n]\tag{5}$$

we see that

$$y_h[n]=c(-1)^n,\quad c\in\mathbf{R}\tag{6}$$

is a solution of (5). Consequently, the general solution of (1) (with $x[n]=\delta[n]$) can be written as

$$y[n]=y_{p1}[n]+y_h[n]=\frac12 (-1)^{n}u(n+1) + c(-1)^n\tag{7}$$

Of course we could as well have used $y_{p2}[n]$ to define the general solution. Note that $y_{p2}[n]$ is obtained from (7) by choosing $c=-1/2$.

Now assume that we scale the input signal and use $x[n]=2\delta[n]$ instead. Obviously, the solutions $y_{p1}[n]$ and $y_{p2}[n]$ will change accordingly, but the general solution (7) will not (unless $c=0$ or $c=-1/2$), because the homogeneous solution (6) does not depend on $x[n]$. This is why I claim that the difference equation (1) does not necessarily describe an LTI system. In our case, it describes exactly two LTI systems and an infinite number of systems which are neither linear nor time-invariant.