Могу ли я go назад и вперед в списке только с помощью алгебры указателей и удалить указатели на предыдущий / следующий?

Question

Допустим, у меня есть такой узел списка:

struct node{
    data_t data;
    struct node* prev;
    struct node* next;
};

Я обычно перемещался по списку, используя предыдущие / следующие адреса, хранящиеся в списке.

Если я ' m не ошибаюсь, когда у меня есть type_t *cursor и просто cursor++ он указывает на следующую область данных своего типа;

, поэтому мне было интересно, могу ли я просто удалить указатели на предыдущий / следующий из структуры и перемещаться по списку, добавляя / вычитая до struct node *cursor, чтобы сэкономить на выделенной памяти.

Возможно, если я удалю указанные указатели, не гарантируется, что узлы будут рядом друг с другом в том порядке, в котором они были выделены? Или есть что-то еще в этом рассуждении, которое может привести к ошибкам? получить седьмой узел списка, а может я ошибаюсь и так не работает?

Answer 1

если ваш узел выделяется один за другим, вы не можете go перейти к следующему / предыдущему с помощью incr / decr указателя на один из них, потому что вы не можете предположить, что они являются смежными в памяти

Я надеюсь, что если я выделю c десять структур, а затем возьму курсор структуры * на адрес заголовка списка и сделаю cursor = cursor + 7, я получу 7-й узел списка, но, возможно, я я ошибаюсь и не работает так?

вы можете это сделать, преимущество в том, что вам не нужен указатель на предыдущий / следующий, поэтому вы запоминаете только данные место сохранения, время для доступа к элементу также немедленно, а не на O (n), недостатком является то, что вы хотите добавить / удалить элемент (ы), потому что вам нужно переместить те, которые находятся после.

Обратите внимание, что массив, вы также можете получить доступ к элементу с индексом, а не иметь указатель на этот элемент.

Функция realloc позволяет изменять размер вашего динамического c массива, как для добавления, так и для удаления элементы с его конца

Answer 2

" Могу ли я go вперед и назад в списке только с помощью алгебры указателей и удалить указатели на предыдущий / следующий? "

" Возможно, если я удалю указанным указателям не гарантируется, что узлы будут смежными друг с другом в том порядке, в котором они были размещены?"

Вы можете go туда и обратно, если у вас есть stati c или динамически выделяемый массив struct node. Тогда гарантируется, что каждый элемент сохраняется в последующем порядке, и вы можете использовать arithmeti указателя c.

К сожалению, в большинстве случаев при использовании связанных списков это не так, поскольку каждый узел выделяется отдельно.

" Поэтому мне было интересно, могу ли я просто удалить указатели на предыдущий / следующий из структуры и перемещаться по списку, добавляя / вычитая к struct node *cursor, чтобы сэкономить на выделенном память."

Как сказано выше, только когда вы выделили массив node. Иначе, если каждый node выделяется отдельно, то вы не можете или лучше сказать, что это неопределенное поведение при любой попытке.

Стандарт C запрещает приращение указателя после того, как он прошел агрегат или скалярный объект.

Не говоря уже о том, что, конечно, разыменование указателя, который указывает после агрегированного или скалярного объекта, также не допускается.

" Я надеюсь, что что если я malloc() десять структур, а затем возьму struct node* курсор на адрес заголовка списка и сделаю cursor = cursor + 7, я получу 7-й узел списка, но, может быть, я ошибаюсь и так не работаю?"

Работает только если вы malloc() все десять структур за один вызов malloc. Затем структуры сохраняются рядом в памяти, и арифметические значения указателя c гарантированно работают.

Также обратите внимание, что вам нужно использовать cursor = cursor + 6;, чтобы добраться до 7 -го узла, а не cursor = cursor + 7; в качестве индексации начинается с 0, а не с 1.