てけもぐ Tech 忘備録

番兵付き双方向循環リスト

対象読者

基本勉強中の方

解決すること

リンクリストで前からも後ろからもアクセスしたい場合などに

内容

C言語などやってると、リンクリストは結構使うのではないかと思うのですが、リンクリストの中でも番兵付き双方向循環リストは結構好きで。

番兵は、要は null で終わる代わりに入れておく目印で、こいつがあるとnull の場合を特別扱いせずにスムーズに処理できる。

そして、双方向だと前にも後ろにも処理を進められる。

んで、循環にしておくと tail は必要なく、 head だけ保持しておけば前に追加するもの後ろに足すのも出来る。

#include<stdio.h>
#include<stdlib.h>

typedef struct _Link Link;
struct _Link {
  char *s;
  Link *prev;
  Link *next;
};

Link *link_init(){
  Link *ln = malloc(sizeof(Link)); 
  ln->s = NULL;
  ln -> prev = ln;
  ln -> next = ln;
  return ln;
}

Link *link_push(Link *sentinel, char *s){
  Link *ln = malloc(sizeof(Link)); 
  ln->s = s;
  ln->prev = sentinel;
  ln->next = sentinel->next;
  sentinel->next->prev = ln;
  sentinel->next = ln;
  return ln;
}

Link *link_add(Link *sentinel, char *s){
  Link *ln = malloc(sizeof(Link)); 
  ln->s = s;
  ln->next = sentinel;
  ln->prev = sentinel->prev;
  sentinel->prev->next = ln;
  sentinel->prev = ln;
  return ln;
}

Link *link_rm(Link *sentinel, Link *ln){
  ln->prev->next = ln->next;
  ln->next->prev = ln->prev;
  return ln;
}

void link_print(Link *sentinel){
  for(Link *ln = sentinel->next ;ln != sentinel; ln=ln->next){
    printf("%s\n", ln->s);
  }
}

int main(){
  Link *sentinel = link_init();
  Link *ln1 = link_push(sentinel, "link_1");
  Link *ln2 = link_push(sentinel, "link_2");
  Link *ln3 = link_add(sentinel, "link_3");
  link_print(sentinel); 
  free(link_rm(sentinel, ln2));
  link_print(sentinel); 
}

これなら、スタックの形でもキューの形でも処理出来ますし、head と tail の両方を保持するために別の構造体をもつなんてことをしなくて済む。

番兵の prev/next に自分自身を入れておくんですよね。これで null チェックしなくてよくなる。これ知った時は感動しました。

以下のように link_new() などとして、prev と next を取るようにしたものを作って楽したりも。push/add を別立てて作らずそのまま link_new() だけでもOKかと。

Link *link_new(char *s, Link *prev, Link *next){
  Link *ln = malloc(sizeof(Link)); 
  ln->s = s;
  ln->prev = prev;
  ln->next = next;
  prev->next = ln;
  next->prev = ln;
}

Link *link_push(Link *sentinel, char *s){
  link_new(s, sentinel, sentinel->next);
}

Link *link_add(Link *sentinel, char *s){
  link_new(s, sentinel->prev, sentinel);
}

Tags

#C