Insert an element into a linked list

Question

If I have two structures defined as follow, how can I insert a new element in the list ? I tried something, but I don't know where is the mistake. The function for inserting a new element is called insertFirst. In main I have lst=insertFirst(lst,7); lst=insertFirst(lst,8); Thank you!

typedef int DATA;
    struct element {
    DATA cheie;
    struct element *urm;
};
typedef struct element Element, *ELEMENT;

struct lista {
    int nr; //nr elemente
    ELEMENT inceput;
    ELEMENT sfarsit;
};
typedef struct lista Lista, *LISTA;


LISTA insertFirst(LISTA l, DATA x)
{
    LISTA w;
    w = (LISTA)malloc(sizeof(Lista));
    if (w == NULL)return NULL;
    w->inceput=(LISTA)malloc(sizeof(Lista));
    w->inceput->cheie = x;
    w->inceput->urm = l;

    LISTA p = l;
    for (; p->inceput->urm != NULL; p = p->inceput->urm);

    w->sfarsit->cheie = p->inceput->cheie;
    w->sfarsit->urm = NULL;
    return w;
}

`insertFirst` has a few issues. `w = (LISTA)malloc(sizeof(Lista)); ... w->inceput->cheie = x; ...` This looks like a problem. When did you initialize the pointer in `w->inceput`? I would also think your `insertFirst` needs to check of the `LISTA l` argument is `NULL` (in case this is the first element inserted in the list). — lurker, Feb 22 '18 at 11:53
Same way you allocated your `LISTA` pointer. Use `malloc`. Or assign them the address of a known data item (that's not on your local stack). By the way, [do not cast the return of `malloc`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — lurker, Feb 22 '18 at 11:57
It's working, but I have a another problem. How can I hold the last element...`sfarsit`? — user6131790, Feb 22 '18 at 12:00
Don't make some unknown changes behind the scenes and just declare it "working". This question posting no longer makes any sense. Your original posted code has a structure that defines a list. Your `insertFirst` creates a whole new list each time, not a new element to an existing list. It's a bit unclear what you're trying to do here. — lurker, Feb 22 '18 at 12:03

Vlad from Moscow · Answer 1 · 2018-02-22T13:08:52.347

It seems you mean the following. That is you have a two-sided singly-linked list.

LISTA insertFirst(LISTA l, DATA x)
{
    ELEMENT w;
    w = (ELEMENT)malloc(sizeof(Element));

    if ( w )
    {
        w->cheie = x;
        w->urm = l->inceput;

        l->inceput = w;
        if ( !l->sfarsit ) l->sfarsit = w;

        ++l->nr;
    }

    return l;
}

Another way to define the function is the following

int insertFirst(LISTA l, DATA x)
{
    ELEMENT w;
    w = (ELEMENT)malloc(sizeof(Element));

    int success = w != NULL;

    if ( success )
    {
        w->cheie = x;
        w->urm = l->inceput;

        l->inceput = w;
        if ( !l->sfarsit ) l->sfarsit = w;

        ++l->nr;
    }

    return success;
}

And in main you should define the list like

Lista l = { 0, NULL, NULL };

Here is a demonstrative program

#include <stdio.h>
#include <stdlib.h>

typedef int DATA;

struct element 
{
    DATA cheie;
    struct element *urm;
};
typedef struct element Element, *ELEMENT;

struct lista 
{
    int nr; //nr elemente
    ELEMENT inceput;
    ELEMENT sfarsit;
};
typedef struct lista Lista, *LISTA;

int insertFirst(LISTA l, DATA x)
{
    ELEMENT w;
    w = (ELEMENT)malloc(sizeof(Element));

    int success = w != NULL;

    if ( success )
    {
        w->cheie = x;
        w->urm = l->inceput;

        l->inceput = w;
        if ( !l->sfarsit ) l->sfarsit = w;

        ++l->nr;
    }

    return success;
}

void outputLista( LISTA l )
{
    printf( "%d: ", l->nr );

    for ( ELEMENT current = l->inceput; current; current = current->urm )
    {
        printf( "%d ", current->cheie );
    }
}

int main(void) 
{
    Lista l = { 0, NULL, NULL };

    insertFirst( &l, 7 );
    insertFirst( &l, 8 );

    outputLista( &l );
    putchar( '\n' );

    return 0;
}

Its output is

2: 8 7

As for your function implementation then it does not make sense. You do not need to create a new list in the function. What you need is to create a new element and insert it before the current first element of the list.

The function that inserts a new element at the end of the list can look like

int insertLast(LISTA l, DATA x)
{
    ELEMENT w;
    w = (ELEMENT)malloc(sizeof(Element));

    int success = w != NULL;

    if ( success )
    {
        w->cheie = x;
        w->urm = NULL;

        if ( l->sfarsit )
        {
            l->sfarsit->urm = w;
        }
        else
        {
            l->inceput = w;
        }

        l->sfarsit = w;

        ++l->nr;
    }

    return success;
}

Insert an element into a linked list

1 Answers1