list

listとは

STLのlistはいわゆる双方向連結リストと言われているものです。

双方向連結リストを言うものを説明する前に、まずリストについての説明をします。 リストとは任意の位置への要素の挿入・削除を要素の順序を変えることなく行うことにできるデータ構造のことです。 このような操作を配列を用いてやろうとすると、

int array[SIZE];
int rear;//データの末尾

//ポインタpの指す位置に新しいデータを挿入する。
void insert(int* p, int data)
{
  int* q;
  rear++;
  if(rear==SIZE)//full
    return;

  for(q=array+rear; q>p; q--)
    *q = *(q-1); //要素を1つずつずらす

  *p =data; //そして、空いた場所に新しいデータを挿入
}

//ポインタpの指す位置のデータを削除する
void erase(int* p)
{
  int* q;
  for(q=p; q<array+rear; q++)
    *q = *(a+1); //要素を1つずつ詰める
  rear--;
}

という風になります。 しかし、この方法では配列が満員になった場合に、それ以上要素の追加ができなくなります。また、挿入・削除が行われるたびに要素をずらしていく必要があるので かなりの時間が(平均時間計算量 O(SIZE) )かかります。

そこで、連結リストというものを使います。 連結リストには線形リスト(linear list、または単方向リスト(one-way list))と呼ばれるものと 双方向リスト(doubly linked list、two-way list)と呼ばれるものがあります。

線形リストから説明します。 まず、ノード(node:節目、結び目)といわれる構造体を定義します。

struct node
{
  node* next;
  int data;
};

そして、このノードを数珠繋ぎしていくと線形リストになります。

この際、一番後ろのノードのnextにはNULLポインタを入れておきます。

node *root, *rear;

void insert(node* p, int data)
{
  node* prev;
  for(prev=root; prev->next!=p && prev->next!=NULL; prev=prev->next);

  if(prev->next == NULL)//p don't exist;
    return;

  node* tmp = new node;
  tmp->data = data;
  tmp->next = p;
  prev->next = tmp;
}

void erase(node* p);
{
  node* prev;
  for(prev=root; prev->next!=p && prev->next!=NULL; prev=prev->next);

  if(prev->next == NULL)//p don't exist;
    return;

  prev->next = p->next;
  delete p;
}

これで要素をいくらでも追加できるようになりました。 しかし、先頭以外への要素の挿入・削除にはやはり時間がかかります(平均時間計算量O(N))。

次は双方向リストについて。 双方向リストでも線形リストと同様にまずノードという構造体を定義します。 線形リストと違うところは、次の要素を指すポインタnextの他に、 一つ前の要素を指すポインタも持っていることです。

struct node
{
  node *next, *prev;
  int data;
};

そして、このノードをつないでいくことで双方向リストになります。

void insert_prev(node* p, int data)
{
  node* q = new node;
  q->prev = p->prev;
  q->next = p;
  p->prev = q;
  q->prev->next = q;
  q->data = data;
}

void insert_next(node* p, int data)
{
  node* q = new node;
  q->next = p->next;
  q->prev = p;
  p->next = q;
  q->next->prev = q;
  q->data = data;
}

void erase(node* p)
{
  node* next = p->next;
  p->next->prev = p->prev;
  p->prev->next = p->next;
  delete p;
}

これで、任意の位置への要素の挿入がO(1)で行えるようになります。

ところで、リストの先頭のprev、末尾のnextをNULLにしていると、 リストの先頭への要素の挿入がうまくいきません。

node* root=NULL;

void insert_prev(node* p, int data)
{
  if(p==root)//挿入位置が先頭の場合、特別な処理が必要。
  {
    root = new node;
    root->prev = NULL;
    root->next = p;
    p->prev = root;
    return;
  }

  node* q = new node;
  q->prev = p->prev;
  q->next = p;
  p->prev = q;
  q->prev->next = q;
  q->data = data;
}

void erase(node* p)
{
  if(p==root)//挿入位置が先頭の場合、特別な処理が必要。
  {
    p = p->next;
    delete root;
    root = p;
    return;
  }

  node* next = p->next;
  p->next->prev = p->prev;
  p->prev->next = p->next;
  delete p;
}

ここで、リストの先頭rootには要素を格納しないダミーノードを付けておき、 リストの末尾のnextにはNULLではなく、rootを代入しておきます。

node* root;//ダミーノード

void init()
{
  root = new node;
  root->next = root;
  root->prev = root;
}

こうすることで、先頭、末尾への要素の追加が簡単になり、 if(p==root)の部分を書く必要がなくなります。 また、リストの末尾(root->prevはリストの末尾を指している)へのアクセスも容易になります。 こういう構造のリストを循環リストといいます。

listの特徴

• 先頭から順番にしかアクセスできない([]を使って添え字を指定してのアクセスができない)
• 任意の箇所への要素の追加、削除が O(1) で行える
• 常にリスト中の要素数分のメモリだけを利用(vectorやdequeは、コンテナ中の要素数よりも多目のメモリを確保し、足りなくなったときにメモリを確保しなおす)