Full disk problem on Ubuntu 16.04 (Xenial Xerus)

You have a lot of kernels installed, they take up a lot of space (300 MiB per kernel). You also have a good number of other packages that were installed as dependencies and, for various reasons, are not needed anymore.

You can safely clean all that with the following command:

sudo apt autoremove

So, as you explained in comments, after doing just that, you got the following error:

The following packages have unmet dependencies:
 linux-headers-generic : Depends: linux-headers-4.4.0-57-generic but it is not installed
E: Unmet dependencies. Try using -f.

You are in a tight spot! Before cleaning packages, APT wants to repair the current ones, that is, install the missing packages. But there is no space for that!

What needs to be done in that case it to free disk space by others means. Maybe you have old files and temporary files you can remove. But since your command above helpfully listed many packages that are not needed anymore, we can remove some of them manually, using the dpkg command.

Note that using dpkg without thinking it through can be dangerous.

The linux-image and linux-image-extra take a lot of space, so let's take some from the list of not needed anymore and remove them with dpkg:

sudo dpkg --remove linux-image-extra-4.4.0-36-generic
sudo dpkg --remove linux-image-4.4.0-36-generic
sudo dpkg --remove linux-image-extra-4.4.0-37-generic
sudo dpkg --remove linux-image-4.4.0-37-generic
sudo dpkg --remove linux-image-extra-4.4.0-38-generic
sudo dpkg --remove linux-image-4.4.0-38-generic

Edit: It turns out that this did not solve the problem. After discussing in chat, and as suggested by others here, you ran df -i and discovered your partition can "only" store 1.2 million files, and all the slots were used.

The linux-headers packages are not as big as linux-image, but they contain a lot of files. So lets take some from the list of not needed anymore and remove them with dpkg:

sudo dpkg --remove linux-headers-4.4.0-36 linux-headers-4.4.0-36-generic
sudo dpkg --remove linux-headers-4.4.0-37 linux-headers-4.4.0-37-generic
sudo dpkg --remove linux-headers-4.4.0-38 linux-headers-4.4.0-38-generic

Now that disk space and inodes have been freed, the missing packages can be installed:

sudo apt install linux-headers-4.4.0-57 linux-headers-4.4.0-57-generic

And now that APT is happy that all package dependencies are installed and everything is well on the machine, we can tell it to automatically remove all packages that are not needed anymore:

sudo apt autoremove

You need to free up some space somehow.

Unfortunately with apt you have a bit of a catch 22, you can't use most apt features until "apt-get -f install" succeeds and "apt-get -f install" won't succeed until you free up some disk space. So despite what serveral other answers here say trying to remove packages with apt is a non-starter.

First try "apt-get clean". This will clean up the downloaded package files and it may free up enough space to make apt-get -f install succeed.

If that is not enough I would suggest removing some of the old kernels with dpkg e.g.

dpkg -r --force-depends linux-image-3.11.0-19-generic

Once you get "apt-get -f install" to run successfully you can then run "apt-get autoremove" as other people have suggested before continuing with your upgrade.

I will suggest you to install bleachbit. It will help you a great deal of space recovery.