Estruturas de Dados

Lista Encadeada — Uma Cadeia Ligada por Ponteiros

Definição do nó

typedef struct Node {
  int data;              // o dado armazenado
  struct Node *next;     // ponteiro para o próximo nó
} Node;

Imagem na memória

Operações principais

// (1) Criar um nó
Node* createNode(int val) {
  Node *n = malloc(sizeof(Node));
  n->data = val;
  n->next = NULL;
  return n;
}

// (2) Inserir no início (O(1) — rápido!)
void pushFront(Node **head, int val) {
  Node *n = createNode(val);
  n->next = *head;     // next do novo nó = head antigo
  *head = n;           // head agora aponta para o novo nó
}

// (3) Imprimir todos os elementos
void printList(Node *head) {
  for (Node *p = head; p != NULL; p = p->next)
    printf("%d → ", p->data);
  printf("NULL\n");
}

// (4) Liberar a memória (esquecer = vazamento!)
void freeList(Node *head) {
  while (head) {
    Node *tmp = head->next;
    free(head);
    head = tmp;
  }
}

Pilha — Último a Entrar, Primeiro a Sair (LIFO)

// push: adiciona no topo
void push(Node **top, int val) {
  Node *n = createNode(val);
  n->next = *top;
  *top = n;
}

// pop: remove do topo
int pop(Node **top) {
  if (*top == NULL) return -1;
  Node *tmp = *top;
  int val = tmp->data;
  *top = tmp->next;
  free(tmp);
  return val;
}

Fila — Primeiro a Entrar, Primeiro a Sair (FIFO)

// enqueue: adiciona na cauda
void enqueue(Node **head, Node **tail, int val) {
  Node *n = createNode(val);
  if (*tail) (*tail)->next = n;
  else *head = n;
  *tail = n;
}

// dequeue: remove da cabeça
int dequeue(Node **head, Node **tail) {
  if (!*head) return -1;
  Node *tmp = *head;
  int val = tmp->data;
  *head = tmp->next;
  if (!*head) *tail = NULL;
  free(tmp);
  return val;
}

Array vs Lista encadeada vs Pilha vs Fila

Demo de Lista Encadeada