[C] Zu dumm für Zeiger in dynamischen Datenstrukturen

[quinte17]

deine einfache verkettete liste funktioniert so leider nicht.

soll ich dir jetzt auch noch funktionnen schreiben, damit du siehst dass die funktioniert?

struct liste{
int element;
struct liste *next;
};

struct kopf{
struct liste *first;
struct liste *last;
} a;

void insert(int x){
  struct liste *tmp;
  tmp = malloc(sizeof(struct liste));
  tmp->next = NULL;
  tmp->element = x;
  if(!first) // liste leer
  {
    a.first = tmp;
    a.last = tmp;
  }
  else // nicht leer
  {
    (a.last)->next = tmp;
    a.last = tmp;
  }
}

int get()
{
  if(!a.first)
    error("liste zu leer");
  struct liste *freeelement;
  int tmp= (a.first)->element;
  freeelement = a.first;
  a.first = (a.first)->next;
  if(a.first == NULL) // letztes element ging raus
    a.last == NULL;
  free(freeelement);
  return tmp;
}

nicht kompilegetestet verdeutlicht aber dass es funktioniert.

[msi]

soll ich dir jetzt auch noch funktionnen schreiben, damit du siehst dass die funktioniert?

struct liste{
int element;
struct liste *next;
};

struct kopf{
struct liste *first;
struct liste *last;
} a;

void insert(int x){
  struct liste *tmp;
  tmp = malloc(sizeof(struct liste));
  tmp->next = NULL;
  tmp->element = x;
  if(!first) // liste leer
  {
    a.first = tmp;
    a.last = tmp;
  }
  else // nicht leer
  {
    (a.last)->next = tmp;
    a.last = tmp;
  }
}

int get()
{
  if(!a.first)
    error("liste zu leer");
  struct liste *freeelement;
  int tmp= (a.first)->element;
  freeelement = a.first;
  a.first = (a.first)->next;
  if(a.first == NULL) // letztes element ging raus
    a.last == NULL;
  free(freeelement);
  return tmp;
}

nicht kompilegetestet verdeutlicht aber dass es funktioniert.

und wie lösch ich jetzt in O(1) du hast den prev pointer vergessen in der struct. ohne den kannst du nur das erste element der liste in O(1) löschen, für das letzte brauchst du O(n).