База указателя и верх для связанного списка в C

Question

Стек структуры данных на основе связанного списка имеет базовые и верхние указатели, которыеуказать на членов стека.

struct node
{
     struct node* next;
     int val;
};
struct stack
{
    struct node* base;
    struct node* top;
}

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

 struct listnode
    {
         struct listnode* next;
         int val;
    };
    struct linkedlist
    {
        struct listnode* base;
        struct listnode* top;
    }

Это уместно?

Answer 1

Для чистого стека потребуется только указатель top . Возможно, вы используете эту структуру данных как queue , добавляя в конце, беря с начала.

A связанный список нуждается только в head , но для добавления к концу tail было бы полезно.

struct linkedlist
{
    struct listnode* head;
    struct listnode* tail;
    int count; // Might be useful
}

(я использовал условные названия.)

Можно упомянуть двусвязный список с:

struct node
{
     struct node* previous;
     struct node* next;
     int val;
};

Что позволило бы полностью симметрично использовать голову и хвост.

Answer 2

Ничто не мешает вам создать структуру данных с любой из пар структур, которые вы определили выше. Однако связанный список, в котором вы можете добавлять и удалять элементы спереди или сзади, не пересекая список, больше похож на dequeue двустороннюю очередь. Точно так же стек, в котором вы можете добавлять или брать элементы с любого конца, также является тенденцией к тому, чтобы стать очередью.

Я думаю, что происходит то, что вы путаетесь между формальным интерфейсом и базовой структурой данных. Таким образом, если вы создали код с API, который позволяет добавлять или удалять элементы с любого конца связанного списка элементов, которые вы можете просматривать и вставлять / удалять, вы можете использовать его для представления стека, связанного списка или очереди в зависимости от какие части API вы используете и как их называете.