Указатели и динамическая память

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

Визуализатор операций с односвязным списком

Список не обеспечивает прямого доступа к элементам набора по номеру. Для перемещения по списку и получения значения используется итератор списка (указатель на текущий элемент).

// Тип для узла списка
typedef struct Node {
  int value;
  struct Node *next;
} Node;

// Тип для итератора списка
typedef struct {
  Node* curr=0;
  bool isDone() { return !curr; }
  void GotoNext() {  if(curr) curr=curr->next; }
  int& Item() {
    if(curr)
      return curr->value;
    else {
      printf("Конец списка\n");
      exit(1);
    }
  }
} ListIterator;
// Тип для всего списка
typedef struct { 
  Node* root=0;
  void AddFront() {
    Node* p=malloc(sizeof(Node));
    p->value=v;
    p->next=root;
    root=p;
  }
  void DelFront() {
    if(root) {
      Node* p=root->next;
      free(root);
      root=p;
    }
  }
  void AddAfter(ListIterator& li, int v) {
    if(li.curr) {
      Node* p=malloc(sizeof(Node));
      p->value=v;
      p->next=li->curr->next;
      li.curr->next=p;
    }
  }
  void DelAfter(ListIterator& li) {
    if(li.curr && li.curr->next) {
      Node* p=li.curr->next->next;
      free(li.curr->next);
      li.curr->next=p;
    }
  }
  void GotoFirst(ListIteraror& li) {
    li.curr=root;
  }
  void DelAll() {
    while(root) DelFront();
  }
} List;
// Примеры действий со списком
List a;
a.AddFront(1);
a.AddFront(2);
ListIterator ai;
for(a.GotoFirst(ai); !ai.isDone(); ai.GotoNext())
   printf("%d\n",ai.Item());

Если в итераторе хранить указатели на текущий и предыдущий элементы, то не нужно будет разделять функции по удалению или добавлению значений в начало и середину списка:

Визуализатор операций с другим итератором

Также упрощаются действия, если хранить указатель не только на следующий, но и на предыдущий элемент списка:

Визуализатор операций с двусвязным списком