Связные списки в С++. Базовые операции.

Интерфейс обработки списков.

---

Для распределения памяти под узлы списка и ее освобождения объявляются собственные функции. Функция construct применена для удобства реализации.

// list.h

typedef int Item;
struct node
{
  Item item;
  node * next;
};
typedef node *link;
typedef link *Node;

void construct(int);
link newNode(int);
void deleteNode(Node);
void insert(link, link);
link remove(link);
Node next(Node);
Item item(Node);

Реализация интерфейса обработки списков

---

Эта программа создает свободный список, который инициализируется в соответствии с максимальным количеством узлов, используемых программой. Все узлы взаимосвязаны. Когда клиентская программа удаляет узел, он привязывается к свободному списку.

#include <iostream>
#include <stdlib.h>
#include "list.h"

using namespace std;

link freelist;

void construct(int N)
{
  freelist = new node[N+1];
  for (int i = 0; i < N; i++)
  {
    freelist[i].next = &freelist[i+1];
  }
  freelist[N].next = 0;
}

link newNode(int i)
{
  link x = remove(freelist);
  x->item = i;
  x->next = x;
  return x;
}

void deleteNode(link x)
{
  insert(freelist, x);
}

void insert(link x, link t)
{
  t->next = x->next;
  x->next = t;
}

link remove(link x)
{
  link t = x->next;
  x->next = t->next;
  return t;
}

link next(link x)
{
  return x->next;
}

Item item(link x)
{
  return x->item;
}

void print_list(link x)
{
  link head = x, t = x;
  cout << "---list---" << endl;
  do
  {
    cout << t->item << endl;
    t = t->next;
  } while(t != head);
  cout << "---end-list---" << endl;
}

link reverse(link x)
{
  link t, y = x, r = 0;
  while (y != 0)
  {
    t = y->next;
    y->next = r;
    r = y;
    y = t;
  }

  return r;
}

int main(int argc, char *argv[])
{
  int N = 10;
  link x, t;

  construct(N);
  x = newNode(1);

  for (int i = 2; i <= N; i++ )
  {
    t = newNode(i);
    insert(x, t);
  }

  print_list(x);

  print_list(reverse(x));

  return 0;
}

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