この回の要点
• 連結リストによるリスト
– 連結リストの構造
– 連結リストの利点と欠点
– C言語による連結リストの実現
• ヘッダファイルによるソースファイルの分割
連結リスト（linked list）
• リストの実現の一種
• リストに含まれる各要素をリンクによって連結した構造
– リンクとは、他のデータへの参照のこと – 各要素は、自分から次のデータへのリンクを持つ – その要素が連なった構造が連結リスト 参照 リンク 名前 個人データ Ａさん Ｂさん Ｃさん Ｄさん Ｅさん Ｆさん連結リストの利点と欠点
• 利点
– データの挿入・削除が簡単＝O(1)
– サイズが可変（メモリの上限はある）
• 欠点
– 要素kにアクセスするのにリンクをたどる必要がある＝
O(N)
– データ以外にリンク分のメモリが必要
挿入 削除双方向連結リスト（double linked list）
• 前後の要素へのリンクを持つ連結リスト
– 要素を逆順にたどることが可能
– 2つのリンクを持つためのメモリが必要
参照 次へ 名前 年齢 個人データ（PD） 参照 前へ NULL Ａさん Ｂさん Ｃさん Ｄさん Ｅさん Ｆさん 双方向連結リスト NULL個人情報型PD
参照 next name age 参照 prev メンバー char *name 名前 int age 年齢 PD *prev,*next 前後のリンク 関数 PD* makePD(const char*,int) PDの生成 void free(PD*) PDの破棄 void insertBefore(PD*,PD*) 前に挿入 void insertAfter(PD*,PD*) 後に挿入 void remove(PD*) 削除 void print(PD*) 表示PD.h
#ifndef __PD__h #define __PD__h /*** *** 個人情報 ***/ #include <stdio.h> #include <stdlib.h> #include <string.h> // 個人情報型の宣言typedef struct PDtag {
struct PDtag *prev,*next; // 前後の個人情報へのリンク char *name; // 名前
int age; // 年齢
PD.h
// プロトタイプ宣言PD *makePD(const char *n,int a); // 生成 void free(PD *pd); // 破棄 void insertBefore(PD *pd1,PD *pd2); // pd1の前にpd2を接続 void insertAfter(PD *pd1,PD *pd2); // pd1の後にpd2を接続 void remove(PD *pd); // pdを取り外す void print(PD *pd); // 表示 #endif // __PD__h ここまでが、1回しか読み込まれない
PD.cc
/*** *** PDの実装 ***/ #include "PD.h" // 個人情報の生成PD *makePD(const char *n,int a){ PD *pd=(PD*)malloc(sizeof(PD)); pd->prev=pd->next=NULL; pd->name=(char*)malloc(strlen(n)+1); strcpy(pd->name,n); pd->age=a; return pd; } // 個人情報の破棄 void free(PD *pd){ free(pd->name); free((void*)pd);
PD.cc
// 個人情報pd1の前に個人情報pd2を接続void insertBefore(PD *pd1,PD *pd2){ if(pd1==NULL || pd2==NULL) return; if(pd1->prev) pd1->prev->next=pd2; pd2->prev=pd1->prev; pd2->next=pd1; pd1->prev=pd2; } 続く pd2 pd1 pd1 前に挿入
PD.cc
// 個人情報pd1の後ろに個人情報pd2を接続 void insertAfter(PD *pd1,PD *pd2){if(pd1==NULL || pd2==NULL) return; if(pd1->next) pd1->next->prev=pd2; pd2->prev=pd1; pd2->next=pd1->next; pd1->next=pd2; } pd1 pd2 pd1 後に挿入
PD.cc
// 個人情報pdを取り外す void remove(PD *pd){ if(pd==NULL) return; if(pd->prev) pd->prev->next=pd->next; if(pd->next) pd->next->prev=pd->prev; pd->prev=pd->next=NULL; } // 個人情報を表示する void print(PD *pd){ printf("%s(%d)",pd->name,pd->age); } pd 削除双方向リンクリストListPD
メンバー PD *first,*last 先頭と末尾の要素 int size 要素数 関数 ListPD* makeLlistPD() 生成 void free(ListPD*) 破棄 void addTop(ListPD*,PD*) 先頭に追加 void add(ListPD*,PD*) 末尾に追加 void remove(ListPD*,PD*) 要素を削除 PD* get(ListPD*,int) 取り出し int getSize(ListPD*) 要素数 PD PD PD first PDListPD.h
#ifndef __ListPD__h #define __ListPD__h /*** *** 個人情報のリスト ***/ #include "PD.h" // 個人情報リスト型の宣言 typedef struct { PD *first,*last; // 先頭と末尾の要素 int size; // 要素数 } ListPD; ヘッダファイルの重複読み込みを回避 続くListPD.h
ListPD *makeListPD(); // 個人情報リストの生成 void free(ListPD *lp); // 個人情報リストの破棄 void addTop(ListPD *lp,PD *pd); // リストlpの先頭に個人情報pdを挿入 void add(ListPD *lp,PD *pd); // リストlpの末尾に個人情報pdを追加 void remove(ListPD *lp,PD *pd); // リストlpの要素pdを削除 PD *get(ListPD *lp,int n); // n番目の要素を得る（先頭は0番） int getSize(ListPD *lp); // 要素数 void print(ListPD *lp); // 表示ListPD.cc
/*** *** ListPDの実装 ***/ #include "ListPD.h" // 個人情報リストの生成 ListPD *makeListPD(){ ListPD *lp=(ListPD*)malloc(sizeof(ListPD)); lp->first=lp->last=NULL; lp->size=0; return lp; } // 個人情報リストの破棄 void free(ListPD *lp){ free((void*)lp); } 続くListPD.cc
// リストlpの先頭に個人情報pdを挿入 void addTop(ListPD *lp,PD *pd){ if(lp->first==NULL) lp->first=lp->last=pd; else{ insertBefore(lp->first,pd); lp->first=pd; } lp->size++; } PD PD PD PD last first PD pdListPD.cc
// リストlpの末尾に個人情報pdを追加 void add(ListPD *lp,PD *pd){ if(lp->last==NULL) lp->first=lp->last=pd; else{ insertAfter(lp->last,pd); lp->last=pd; } lp->size++; } 続く PD PD PD PD last first PD pdListPD.cc
// 要素pdを削除 void remove(ListPD *lp,PD *pd){ if(lp->first==pd) lp->first=pd->next; if(lp->last==pd) lp->last=pd->prev; remove(pd); lp->size--; } // n番目の要素を得る（先頭は0番） PD *get(ListPD *lp,int n){ PD *p=lp->first;for(int i=0;i<n && p;i++) p=p->next; return p; PD PD PD last first PD pd
