線形リストに要素をBackward(指定要素の直前)追加

線形リストの途中に新たな要素を指定要素の前に追加します。

// 線形リストの作成
#include <stdio.h>
#include <stdlib.h>

struct list {
  int key;
  struct list *next;
};

struct list *get_list(void);
void print_list(struct list *p);
int get_data(void);
void insert_before(struct list *x, struct list *p);

#define EOD -1
/* 初期データリスト */
int a[ ] = { 1, 2, 3, 4, 5, 6, EOD };
	
int main( )
{
  struct list *listptr, *new;

  listptr = get_list( );
  print_list( listptr );

  new = (struct list *)malloc(sizeof(struct list));
  new->key = 888;
  new->next = NULL;
  insert_before( new, listptr->next->next );
  print_list( listptr );

  return 0;
}

/* 入力データが空になるまでリストを作成 */
struct list *get_list( void ) {
  int d;
  struct list *p,*newp;

  p = NULL;           // リストの先頭項目を終端するNULLを入れる
  while( ( d = get_data( ) ) != EOD) {
// 一項目分の記憶領域を確保し，その領域へのポインタを返す
// (struct list *)はmallocの返すデータの型をlist構造体型の情報にキャスト(変換)
    newp = (struct list *)malloc(sizeof(struct list));
    newp->key = d;    // mallocで取得した一項目分の記憶領域にデータを書き込む
    newp->next = p;   // pに保管していた一つ前の項目のアドレス(最初はNULL)をnextアドレスとして書込む
    p = newp;         // 現記憶領域へのポインタをpに保管
    print_list( p );
  }
  return p;           // この時点で、pはリストの最終項目へのポインア(のアドレス)
}

/* データ取得 */
int get_data(void) {
  static int i=0;
  
  return a[i++];
}

/* リストの印刷 */
void print_list(struct list *p) {
  while (p != NULL) {
    printf("<%d> [%0x %0x] ", p->key, p, p->next);
    p = p->next;
  }
  printf("\n");
}
/* リストへの挿入: 指定要素の直前 */
/* pで示される構造体の前にxで示される構造体を挿入 */
void insert_before(struct list *x, struct list *p) {
  struct list tmp;

  printf("<Insert [%0x] before [%0x]>\n", x, p);
  printf("<p key=%d next=%0x>\n", p->key, p->next);
  printf("<x key=%d next=%0x>\n", x->key, x->next);

  tmp = *x;
  printf("<tmp [%0x] key=%d next=%0x>\n", tmp, tmp.key, tmp.next);

  *x = *p;
  printf("<x [%0x] key=%d next=%0x>\n", x, x->key, x->next);

  *p = tmp;
  printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next);

  p->next = x;
  printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next);
}

実行結果は

C:\TDM-GCC-64\work>linklistInsertBackword
<1> [9b1390 0]
<2> [9b74f0 9b1390] <1> [9b1390 0]
<3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]
<4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]
<5> [9b7550 9b7530] <4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]
<6> [9b7570 9b7550] <5> [9b7550 9b7530] <4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]
<6> [9b7570 9b7550] <5> [9b7550 9b7530] <4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]
<Insert [9b7590] before [9b7530]>
<p key=4 next=9b7510>
<x key=888 next=0>
<tmp [62fdf0] key=888 next=0>
<x [9b7590] key=4 next=9b7510>
<p [9b7530] key=888 next=0>
<p [9b7530] key=888 next=9b7590>
<6> [9b7570 9b7550] <5> [9b7550 9b7530] <888> [9b7530 9b7590] <4> [9b7590 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]

挿入処理の本体は

void insert_before(struct list *x, struct list *p) {
  struct list tmp;

  tmp = *x;         //step1
  printf("<tmp [%0x] key=%d next=%0x>\n", tmp, tmp.key, tmp.next);

  *x = *p;          //step2
  printf("<x [%0x] key=%d next=%0x>\n", x, x->key, x->next);

  *p = tmp;         //step3
  printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next);

  p->next = x;      //step4
  printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next);
}

実行イメージは