--- a/src/vehicle.cpp
+++ b/src/vehicle.cpp
@@ -375,26 +375,16 @@
 
 	/* Remove from the old position in the hash table */
 	if (old_hash != NULL) {
-		Vehicle *last = NULL;
-		Vehicle *u = *old_hash;
-		while (u != v) {
-			last = u;
-			u = u->next_new_hash;
-			assert(u != NULL);
-		}
-
-		if (last == NULL) {
-			*old_hash = v->next_new_hash;
-		} else {
-			last->next_new_hash = v->next_new_hash;
-		}
+		if (v->next_new_hash != NULL) v->next_new_hash->prev_new_hash = v->prev_new_hash;
+		*v->prev_new_hash = v->next_new_hash;
 	}
 
 	/* Insert vehicle at beginning of the new position in the hash table */
 	if (new_hash != NULL) {
 		v->next_new_hash = *new_hash;
+		if (v->next_new_hash != NULL) v->next_new_hash->prev_new_hash = &v->next_new_hash;
+		v->prev_new_hash = new_hash;
 		*new_hash = v;
-		assert(v != v->next_new_hash);
 	}
 
 	/* Remember current hash position */
@@ -418,24 +408,15 @@
 
 	/* remove from hash table? */
 	if (old_hash != NULL) {
-		Vehicle *last = NULL;
-		Vehicle *u = *old_hash;
-		while (u != v) {
-			last = u;
-			u = u->next_hash;
-			assert(u != NULL);
-		}
-
-		if (last == NULL) {
-			*old_hash = v->next_hash;
-		} else {
-			last->next_hash = v->next_hash;
-		}
+		if (v->next_hash != NULL) v->next_hash->prev_hash = v->prev_hash;
+		*v->prev_hash = v->next_hash;
 	}
 
 	/* insert into hash table? */
 	if (new_hash != NULL) {
 		v->next_hash = *new_hash;
+		if (v->next_hash != NULL) v->next_hash->prev_hash = &v->next_hash;
+		v->prev_hash = new_hash;
 		*new_hash = v;
 	}
 }

--- a/src/vehicle_base.h
+++ b/src/vehicle_base.h
@@ -100,8 +100,8 @@
 	/* Boundaries for the current position in the world and a next hash link.
 	 * NOSAVE: All of those can be updated with VehiclePositionChanged() */
 	Rect coord;
-	Vehicle *next_hash;
-	Vehicle *next_new_hash;
+	Vehicle *next_hash, **prev_hash;
+	Vehicle *next_new_hash, **prev_new_hash;
 	Vehicle **old_new_hash;
 
 	SpriteID colourmap; // NOSAVE: cached colour mapping