I put this much detail into this post because I am concerned about your weight, and dietary preferences beyond just the sugar from soda.
Lego's answer is quite comprehensive, but to me it sounds way too painful, unnecessary and unnatural. Unnatural because your metabolism will still be dealing with carbs, doesn't matter how complex or what glycemic index they have. Just like a lot of calorie-restriction low-fat diets are unnatural. As long as high levels of carbs are there, the instinct will remain, and you will have to deal with withdrawal for ages, It's torturous.
Lego's solution implies Personality-conditioning, Personality-conditioning in the face of your body generating withdrawal and longing. You can just condition your body, a very painless process.
Low-carb diets are the answer to your problems, Your metabolic processes change and your body's hunger mechanism is completely changed, one change is insulin and blood sugar is no longer in the loop, so your body literally forgets about sugar. You don't have to stick to the diet forever, 2 weeks would be enough to break the addiction I reckon. but you are a heavy dude like me), and are probably heading to type-2 diabetes, heart disease, and high blood pressure :(, so it be worth sticking to it for longer.
There will most likely be a gap in your life if you eliminate those things which you took great pleasure from. I recommend endurance exercise to fill this gap :D
The Atkins program is quite good a good way to start.
Here is What you do :
Stop eating carbs and sugar, 60% fat + 35% protein and 5% complex veggie carbs. No bread, no pasta, no fruit. Your addiction will literally fall through the floor 6 or so days in. You'll have 2 days or so of fogginess, after that your set. Add more salt to your food because you excrete more salt when you eat like this, if you don't you might start feeling faint, eat more salt especially during exercise.
- Hunger in general is countered by: Fat. Slow digesting, and the stream of fat entering the blood stream inhibits hunger.
- Longing for sugar/carbs is countered by: the elimination of insulin spikes, and the stable blood sugar levels brought about by ketones, and the adaption of most of your cells to fat metabolism.
- No, eating lots of fat is NOT BAD: (only misconception I will address). Once your body has adapted, there is actually a preferential order as to how your body consumes fat. The dangerous types of fats are burned before the healthier ones. This means that over time a person on this has SIGNIFICANTLY better bloodwork than those on a carb-based diet.
My Experience
I used to eat 1-2k worth of processed sugar almost every day. I would think about sugar when I wasn't eating it. It was almost an addiction. I switched to Atkins and started training on a bike, I have lost 9 kg in six weeks, and probably would have lost more if I hadn't been gaining muscle mass. I eat 1.8-2.5k calories a day.
Some Points:
- After the first 3-4 days I stopped thinking about sugar/complex carbs ENTIRELY.
- I can under eat to 1k calories (maintaining 100 g of protein) without feeling any hunger pangs.
- I drink a double glass of coffee with 3-4 tbsp of double cream and 2 tablespoons of Splenda in the morning, I doubt any soda ever tasted as good.
P.s., to those with stereotypical unscientific negative notions on carbless diets I refer here, and here.