Добавить элемент в конец двусвязного списка

Question

первая реализация работает, а вторая и третья реализация нет. Вторая выводит два последних элемента - 5 и 6. Третья вообще молчит.
Объясните пожалуйста в чем ошибка?

typedef struct node {
    int a;
    struct node *next;
    struct node *prev; 
} Node;


void AddElemEnd1(Node **Root, int i)
{
    Node *Head;
    //Node *List = Root;
    Head = malloc(sizeof(Node));
    assert(Head);
    Head->a = i;
    Head->next = NULL;
    if(!*Root)
    {
        Head->prev = NULL;
        *Root = Head;
    } 
    else 
    { 
        Node *List = *Root;
        while(List->next != NULL)
            List = List->next;
        Head->prev = List;
        List->next = Head;
    }
}

Node *AddElemEnd2(Node *Root, int i)
{
    Node *Head;
    Head = malloc(sizeof(Node));
    assert(Head);
    Head->a = i;
    Head->next = NULL;
    if(!Root)
    {
        Head->prev = NULL;
        Root = Head;
    } 
    else 
    { 
        //Node *List = Root;
        while(Root->next != NULL)
            Root = Root->next;
        Head->prev = Root;
        Root->next = Head; 
    }
    return Root;
}

Node *AddElemEnd3(Node *Root, int i)
{
    Node *Head;
    Head = malloc(sizeof(Node));
    assert(Head);
    Head->a = i;
    Head->prev = NULL;
    Head->next = NULL;
    /*if(!Root){
        Root = Head;
    } else*/
    if(Root) 
    { 
        Node *List = Root;
        while(List->next != NULL)
            List = List->next;
        Head->prev = List;
        List->next = Head;
        //Head->next = NULL;
        //List->prev = NULL; 
    }
    return Root;
} 

void NPrint(Node *Root)
{
    Node *p = Root;
    while(p != NULL)
    {
        printf("N-> %d\n", p->a);
        //p = p->right;
        p = p->next;
    }
} 

int main()
{
    Node *Root = NULL;
/*
    for(int i = 0; i < 7; i++) { 
    AddElemEnd1(&Root, i);
    }
    NPrint(Root);
    printf("-->>>\n");
    for(int i = 0; i < 7; i++) { 
    Root = AddElemEnd2(Root, i);
    }
    NPrint(Root);
    printf("-->>>\n");
*/
    for(int i = 0; i < 7; i++)
        Root = AddElemEnd3(Root, i);

    NPrint(Root);
    //NDel(Root); 
    
    return 0;
}

Answer 1

Ну тут есть недочеты.
Начнем с 3 реализации. В ней if(Root) никогда не выполняется. Потому что как был Node *Root = NULL;, так и остался.
А во 2 реализации, вы сдвигаете указатель на начало списка до последнего элемента, А потом добавляете ещё один. Вот так у вас и остается всего 2 элемента в списке.

Node *AddElemEnd2(Node *Root, int i)
{
    ....
    else 
    { 
        while(Root->next != NULL)
            Root = Root->next;   // указатель на начало движется по списку
    }
    return Root;
}

Точнее список весь там есть, просто указатель Root указывает на предпоследний элемент, а не на первый. Если вы станете на последний элемент и начнете выводить список с конца в начало, то список выведется весь.

Ну и неоптимально добавление - чтобы вставить элемент вы каждый раз проходите по всему списку. Тут есть варианты.
1 - сделать класс списка и хранить указатели на начало и конец списка. И добавлять элементы в конец или начало без прохода по списку.

struct MyList
{
    Node *Root;
    Node *Tail;
    // int size; // можно и размер хранить, если он нужен
}

2 - закольцевать список. Т.к. список двунаправленный, можно сделать чтобы последний элемент указывал на первый, а Root->prev на последний.
В этих случаях вставка будет выполняться за константное время, независимо от длины списка.

БЛОГ НА HUSL

Добавить элемент в конец двусвязного списка

Ответы (1 шт):