Cでの循環単一リンクリストのエレガントな実装？

Question

古典的なデータ構造を辿り、リンクされたリストで停止しました。単なる循環型の単一リンクリストを実装しましたが、私はこのリストをよりエレガントな方法で表現できると圧倒されています。 効率性とコードの可読性を念頭に置いて、誰かが単一リンク循環リストのためのより簡潔で効率的なソリューションを提示できますか？

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


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


struct list{ 
    struct node* head; 
}; 


struct node* init_node(int value){ 
    struct node* pnode; 
    if (!(pnode = (struct node*)malloc(sizeof(struct node)))){ 
     return NULL; 
    } 
    else{ 
     pnode->value = value; 
    } 
    return pnode; 
} 

struct list* init_list(){ 
    struct list* plist; 
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){ 
     return NULL;   
    } 
    plist->head = NULL; 
    return plist; 
} 


void remove_node(struct list*a plist, int value){ 

    struct node* current, *temp; 
    current = plist->head; 
    if (!(current)) return; 
    if (current->value == value){ 
     if (current==current->next){ 
      plist->head = NULL; 
      free(current); 
     } 
     else { 
      temp = current; 
      do {  
       current = current->next;  
      } while (current->next != plist->head); 

      current->next = plist->head->next; 
      plist->head = current->next; 
      free(temp); 
     } 
    } 
    else { 
     do { 
      if (current->next->value == value){ 
       temp = current->next; 
       current->next = current->next->next; 
       free(temp); 
      } 
      current = current->next; 
     } while (current != plist->head); 
    } 
} 

void print_node(struct node* pnode){ 
    printf("%d %p %p\n", pnode->value, pnode, pnode->next); 
} 
void print_list(struct list* plist){ 

    struct node * current = plist->head; 

    if (!(current)) return; 
    if (current == plist->head->next){ 
     print_node(current); 
    } 
    else{ 
     do { 
      print_node(current); 
      current = current->next; 

     } while (current != plist->head); 
    } 

} 

void add_node(struct node* pnode,struct list* plist){ 

    struct node* current; 
    struct node* temp; 
    if (plist->head == NULL){ 
     plist->head = pnode; 
     plist->head->next = pnode; 
    } 
    else { 
     current = plist->head; 
     if (current == plist->head->next){ 
      plist->head->next = pnode; 
      pnode->next = plist->head;  
     } 
     else { 
      while(current->next!=plist->head) 
       current = current->next; 

      current->next = pnode; 
      pnode->next = plist->head; 
     } 

    } 
} 

Answer 1

Linuxカーネルソース内の循環リンクリストを見てみましょう：http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

その美しさは、あなたがリストに合うようにあなたのデータのための特別な構造体を持っていないという事実に由来リストとして持ちたい構造体にstruct list_head *を含める必要があります。リスト内の項目にアクセスするためのマクロは、オフセット計算を処理してstruct list_headからデータへのポインタを取得します。

kernelnewbies.org/FAQ/LinkedListsで、カーネルで使用されているリンクリストのより詳しい説明があります（申し訳ありませんが、2つのハイパーリンクを投稿するのに十分なカルマはありません）。

編集：リストはダブルリンクされたリストであり、あなたのようにシングルリンクされたリストではありませんが、コンセプトを採用して独自のシングルリンクリストを作成することができます。

Answer 2

いくつかのコメント：

• 私はあなたがヘッドノードを削除すると削除機能が正しく循環リストのポインタを調整しないと、リストは3つの要素よりも大きくなっていると思います。リストは循環型なので、リストの最後のノードを新しいヘッドに向けなければなりません。
• "find_node"関数を作成することで、削除機能をわずかに短縮することができます。しかし、リストは循環型であるため、非円形リストよりも複雑なヘッドノードを削除する場合もある。
• コード「美しさ」は、見る人の目の前にあります。コードは読んで理解しやすいので、野生のコードを遥かに凌駕します。

Answer 3

リストの要素（いわゆる「センチネル」）のようにリストヘッドを扱うと、リスト処理（特に循環リストの処理）が簡単になります。特別なケースがたくさん消えます。あなたはセンチネルのためにダミーノードを使うことができますが、次のポインタが構造体の最初のものであれば、それを行う必要はありません。もう1つ大きなトリックは、リストを変更するたびに前のノードの次のポインタへのポインタを保持することです（後で変更することができます）。すべてをまとめて、あなたはこれを得る：

struct node* get_sentinel(struct list* plist) 
{ 
    // use &plist->head itself as sentinel! 
    // (works because struct node starts with the next pointer) 
    return (struct node*) &plist->head; 
} 

struct list* init_list(){ 
    struct list* plist; 
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){ 
     return NULL;   
    } 
    plist->head = get_sentinel(plist); 
    return plist; 
} 

void add_node_at_front(struct node* pnode,struct list* plist){ 
    pnode->next = plist->head; 
    plist->head = pnode; 
} 

void add_node_at_back(struct node* pnode,struct list* plist){ 
    struct node *current, *sentinel = get_sentinel(plist); 

    // search for last element 
    current = plist->head; 
    while (current->next != sentinel) 
     current = current->next; 

    // insert node 
    pnode->next = sentinel; 
    current->next = pnode; 
} 

void remove_node(struct list* plist, int value){ 
    struct node **prevnext, *sentinel = get_sentinel(plist); 
    prevnext = &plist->head; // ptr to next pointer of previous node 
    while (*prevnext != sentinel) { 
     struct node *current = *prevnext; 
     if (current->value == value) { 
      *prevnext = current->next; // remove current from list 
      free(current); // and free it 
      break; // we're done! 
     } 
     prevnext = &current->next; 
    } 
} 

void print_list(struct list* plist){ 
    struct node *current, *sentinel = get_sentinel(plist); 
    for (current = plist->head; current != sentinel; current = current->next) 
     print_node(current); 
} 

Answer 4

私は以下を使って、動的循環単一リンクリストを作成する。必要なのはサイズだけです。

Node* createCircularLList(int size) 
{ 
    Node *it; // to iterate through the LList 
    Node *head; 

    // Create the head /1st Node of the list 
    head = it = (Node*)malloc(sizeof(Node)); 
    head->id = 1; 

    // Create the remaining Nodes (from 2 to size) 
    int i; 
    for (i = 2; i <= size; ++i) { 
     it->next = (Node*)malloc(sizeof(Node)); // create next Node 
     it = it->next;       // point to it 
     it->id = i;        // assign its value/id 
     if (i == 2) 
      head->next = it; // head Node points to the 2nd Node 
    } 
    // close the llist by having the last Node point to the head Node 
    it->next = head; 

    return head; // return pointer to start of the list 
} 

と私はそうのようなNode ADTを定義します。

typedef struct Node { 
    int id; 
    struct Node *next; 
} Node;