二重リンクリストのインジェクション関数は、pop（）の呼び出し後にhead要素に任意に戻ることを指します。

Question

EDIT：私の質問は、提案された複製とはまったく異なります。私の質問は、それがどれほど具体的であるかを考えれば、奇妙な行動の理由が追跡可能でなければならない非常に特殊なケースを求めているのに対し、一般的なケースについては質問しています。

私は二重LL実装でいくつかの本当に奇妙な動作をしています。 基本的には、もし私がpop()（先頭から）要素とならばinject()（他の要素を追加します）、最後のテール要素は、一見無意味な理由でリストの先頭を指しますデフォルトでは少なくともランダムなアドレス）。

問題を解決する方法を理解しました。注射するとき、私は新しいノードの "次へ"をNULLにしていませんでした。

しかし、注入されたノードが、指し示す場所の特定の方向なしで頭を指すことを選択する理由を理解したいと思います。

頭から始まって（尾から始まらない）リストを移動すると、最後のテール要素がリストの先頭を指しているので、私は永遠にループし続けます。

EDIT：だから私は、ポインタがちょうどinject()でmalloc関数への呼び出しの後、ポインタがすでに先頭のアドレスを指して作成されたいくつかのクレイジーな理由で指しているアドレスをプリントアウトしようとしました。これはinject()を呼び出す前にpop()に電話すると発生します。信じられないほど奇妙な...

int pop() 
{ 
    node* temp = head; 
    int value = temp->value;  
    head = temp->next; 
    free(temp); 
    head->previous = NULL; 
    size--; 
    return value; 
} 

void inject(int value) 
{ 
    if (tail == NULL) 
    {    
     tail = malloc(sizeof(node)); 
     tail->value = value; 
     tail->next = NULL; 
     tail->previous = NULL; 
     head = tail; 
     size++; 
    } 
    else 
    { 
     node* new_node = malloc(sizeof(node)); 
     printf("pointing to: %p\n", new_node->next);// points to head after pop() call 
     new_node->value = value; 
     tail->next = new_node; 
     new_node->previous = tail; 
     tail = new_node; 
     //new_node->next = NULL; 
     size++; 
    } 
} 

注入でコメントアウト行は（）の問題を解決するが、それでも私はポップ後に注入した場合の尾が頭に戻って指すことになり理由を説明しません。

は、以下のmain（）の場合で前のコードです：

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

node* head = NULL; 
node* tail = NULL; 

int head_value(); 
int tail_value(); 
void push(int); 
int pop(); 
void inject(int); 
int eject(); 

int size = 0; 

Answer 1

node* new_node = malloc(sizeof(node)); 
    printf("pointing to: %p\n", new_node->next);// points to head after pop() call 

new_node->nextがmallocがそこに入れたいものは何でもゴミが含まれます。 がに頭を向けることがありますが、それは初期化していないので、printfはゴミで意味を見つけようとしています。

あなたのコードはメモリ管理を全面的に分散します。それを修正しようとするよりも、構造体に関する私の株式アドバイスを使って書き直しましょう：常にそれらを初期化して破壊する関数を書きます。 常にです。たとえそれが愚かで些細なようであっても。これは、その場所のいたるところにコードを散らすことを避け、毎回わずかに異なるようにします。それはあなたがそれを使用しようとする前に構造体の基本的な機能をテストすることができます。これは、メモリ管理ではなく、アルゴリズムに焦点を当てることができます。

---

まず、構造体を調整しましょう。 nodeは型にとって非常に悪い名前です。あなた（または他の誰か）が変数nodeを呼び出して競合する可能性があります。私はそれをNodeと呼びました、変数と組み込み変数との混同を避けるために大文字にしました。

typedef struct Node { 
    int value;  
    struct Node* next; 
    struct Node* previous;  
} Node; 

今、私たちはNode_newとNode_destroyを書くことができます。

Node *Node_new() { 
    Node *node = malloc(sizeof(Node)); 
    node->value = 0; 
    node->next = NULL; 
    node->previous = NULL; 

    return node; 
} 

void Node_destroy(Node *node) { 
    free(node); 
} 

Node_destroy

は愚かに見えるかもしれませんが、それは Nodeを破壊する方法を覚えておくことから、あなた（または他の誰か）を解放します。そして、それは Nodeの内部構造を（これを書いている間に起こった）残りのコードを変更することなく変更することができます。

---

グローバルを使用しています。グローバル化はすべてをより複雑にし、コードでできることを制限します。代わりに、head、tail、sizeなどのものを独自の構造にラップし、その周囲を渡します。

typedef struct { 
    Node *head; 
    Node *tail; 
    size_t size; 
} LinkedList; 

そして、独自の作成および破棄機能が必要です。 LinkedList_destroyを心配し、潜在的に台無しにするために、すべてのノードで、LinkedListののユーザーのためにその1つの以下の事をクリーンアップするための責任を取ることを

LinkedList *LinkedList_new() { 
    LinkedList *list = malloc(sizeof(LinkedList)); 
    list->head = NULL; 
    list->tail = NULL; 
    list->size = 0; 

    return list; 
} 

void LinkedList_destroy(LinkedList *list) { 
    for(Node *node = list->head; node != NULL; node = node->next) { 
     Node_destroy(list->head); 
    } 

    free(list); 
} 

注意。

LinkedList_destroyNodeの仕組みについて知らずにNode_destroyに電話することができます。これは、カプセル化と抽象化が即座にNodeの恩恵を受ける方法です。しかし、再帰を使用しないでください。リストは任意に長くなり、再帰はスタックのオーバーフローを引き起こします。

---

ここでは、物事が適切に作成され破棄されたことをプッシュアンドポップで書いています。それらは、グローバルを使用するのではなく、LinkedListをとることに注意してください。

void LinkedList_push(LinkedList *list, int value) 
{ 
    Node *node = Node_new(); 
    node->value = value; 

    switch(list->size) { 
     /* The list is empty, this is the first node */ 
     case 0: 
      list->head = list->tail = node; 
      break; 
     default: 
      list->tail->next = node; 
      node->previous = list->tail; 
      list->tail = node; 
      break; 
    } 

    list->size++; 
} 

int LinkedList_pop(LinkedList *list) { 
    Node *popped = list->tail; 

    switch(list->size) { 
     /* The list is empty, nothing to pop */ 
     case 0: 
      fprintf(stderr, "LinkedList was empty when popped.\n"); 
      exit(1); 
      break; 
     /* Popped the last node */ 
     case 1: 
      list->head = list->tail = NULL; 
      break; 
     /* Only one node left, it's both the head and tail */ 
     case 2: 
      list->tail = list->head; 
      list->tail->previous = list->tail->next = NULL; 
      break; 
     default: 
      list->tail = popped->previous; 
      list->tail->next = NULL; 
      break; 
    } 

    /* Have to do this at the end because size_t is unsigned 
     it can't go negative */ 
    list->size--; 

    int value = popped->value; 
    Node_destroy(popped); 

    return value; 
} 

私はので、私はすべての特別な場合を明確に区別することができswitchを使用しました。

これはプッシュアンドポップのベスト実装か、バグフリーでもないとは言いませんが、構造体が正しく初期化されたか解放されたかを気にせずに書き込むことができます。あなたは、メモリ管理ではなく、ロジックに集中することができます。

---

し、それを実証するためのすべての作品は...

void LinkedList_print(LinkedList *list) { 
    for(Node *node = list->head; node != NULL; node = node->next) { 
     printf("%d\n", node->value); 
    } 
} 

int main() { 
    LinkedList *list = LinkedList_new(); 

    for(int i = 0; i < 3; i++) { 
     LinkedList_push(list, i); 
    } 

    while(list->size != 0) { 
     printf("list->size: %zu\n", list->size); 
     LinkedList_print(list); 
     LinkedList_pop(list); 
    } 

    LinkedList_destroy(list); 
} 

$ ./test 
list->size: 3 
0 
1 
2 
list->size: 2 
0 
1 
list->size: 1 
0