Являются ли узлы в связанном списке отдельными структурами или частью одной структуры?

Question

У меня есть связанный список в C следующим образом:

typedef struct intSet *link;

typedef struct intSet {
    int num;
    link next;
} intSet;

Когда я напечатал размер различных членов структуры, я получил следующее:

sizeof(List) = 8 bytes  //List is a newly created list
sizeof(curr->num) = 4 bytes  // curr is just a node within the list
sizeof(curr->next) = 8 bytes

Мой вопрос: всегда ли сама структура имеет размер 8 байтов независимо от того, сколько элементов у нас в списке, или эти 8 байтов относятся только к первому узлу и отличаются от следующих узлов в списке экземпляры той же структуры?

Причина, по которой я спрашиваю, состоит в том, что, поскольку я планирую реализовать это как определяемый пользователем тип данных в PostgreSQL, и поэтому мне необходимо объявить, является ли длина типа данных постоянной или переменной:

CREATE TYPE list (
    internallength = 8? or internallength = variable
    input = ..., output = ... );

Если это переменная, я должен изменить свое представление структуры на:

typedef struct intSet {
    int size;
    int num;
    link next;
} intSet;

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

Answer 1

Ваш тип link является указателем, что было бы более очевидно, если бы вы не запутывали его с помощью typedef. Указанная вещь - это отдельная struct (которая также имеет собственную точку next и т. Д.), Для которой требуется собственное хранилище.

Теперь sizeof(curr->next) и sizeof(List) - это размер указателя на структуру , а не struct intSet. sizeof(*(curr->next)) и sizeof(struct intSet) будут размером самой структуры, т. Е. Объемом пространства, которое вам нужно выделить для одиночной структуры.

Никогда sizeof не пересекает указатели, чтобы узнать размер всего списка. Если вам нужно выяснить весь размер списка, вам нужно пройти его самостоятельно и сосчитать элементы, тогда общий размер составляет count * sizeof(struct intSet). Однако вряд ли вам понадобится эта информация для связанного списка, поскольку, если вы выделите весь список сразу, вы можете просто использовать массив без next ссылок…

Answer 2

Забота о sizeof не является основной проблемой, особенно в том, что в 32 битах sizeof (intSet) будет 8, а в 64 битах sizeof (intSet) будет 32 бита.

Что касается PostgreSQL, объект, который вы хотите сохранить, представляет собой контейнер int и, следовательно, переменной длины. Поэтому объект, который вы хотите обработать, - это не intSet, а структура, содержащая размер и первый элемент вашего списка.

typedef struct intSet *link;

typedef struct intSet {
    int num;
    link next;
};

struct intSetSized
{
    int size;
    intSet begin;
};

Это intSetSized, который вы хотите объявить как пользовательские типы, как в udt .

И каждый, кого вы добавляете или удаляете из списка, настраивает size.

Будьте осторожны с реализацией функций ввода и вывода для вашего объекта. intSetSized он более хитрый, чем пример, приведенный в udt .

Answer 3

sizeof для указателя такой же в системе. В вашем случае это всегда будет 4 байта, независимо от того, на что он указывает (будь то int, char, struct и т. Д.). Это будет 4 байта в вашем случае. Следовательно, размер вашей структуры будет всегда 8 байтов (4 байта для int + 4 байта для указателя).