目録

定義

単方向連結リストの実装

ヘッダーノードなし

ヘッダーノードあり

単方向連結リストの空判定（Empty）

ヘッダーノードなし

ヘッダーノードあり

単方向連結リストの位置指定挿入（ListInsert）

ヘッダーノードなし

ヘッダーノードあり

指定ノードの後方挿入操作（InsertNextNode）

指定ノードの前方挿入操作（InsertPriorNode）

単方向連結リストの位置指定削除（ListDelete）

ヘッダーノードなし

ヘッダーノードあり

指定ノードの削除操作（DeleteNode）

単方向連結リストの位置指定検索（GetElem）

単方向連結リストの値指定検索（LocateElem）

単方向連結リストの長さ（Length）

単方向連結リストの作成

末尾挿入法

先頭挿入法

定義

線形リストの連続的ストレージ方式が単方向連結リストです。

利点：大きな連続的なメモリ領域を必要とせず、容量変更が容易 欠点：ランダムアクセスができず、ポインタを格納するため追加のメモリを消費

単方向連結リストの実装

typedef struct Node{      //単方向連結リストのノード定義 
    int value;           //各ノードがデータ要素を保持 
    struct Node *link;    //次のノードを指すポインタ 
}Node,*Chain;

単方向連結リストを表現するには、最初のノードを指すヘッドポインタLを宣言するだけです。

//単方向連結リストの最初のノードを指すポインタを宣言
Node * first;      //これはノードであることを強調
Chain list;        //これは単方向連結リストであることを強調

ヘッダーノードなし

#include<stdio.h>

typedef struct Node{      //単方向連結リストのノード定義 
    int value;           //各ノードがデータ要素を保持 
    struct Node *link;    //次のノードを指すポインタ 
}Node,*Chain;


//空の単方向連結リストを初期化
bool InitChain(Chain &list){
    list = NULL;          //空のリスト、まだノードはない 
    return true; 
}
 
int main(){
    Chain list;           //単方向連結リストを指すポインタを宣言 
    //空のリストを初期化 
    InitChain(list);      
    return 0; 
} 

ヘッダーノードあり

#include<stdio.h>

typedef struct Node{      //単方向連結リストのノード定義 
    int value;           //各ノードがデータ要素を保持 
    struct Node *link;    //次のノードを指すポインタ 
}Node,*Chain;


//単方向連結リストを初期化（ヘッダーノードあり）
bool InitChain(Chain &list){
    list = (Node *) malloc(sizeof(Node));    //ヘッダーノードを割り当て 
    if(list == NULL)                         //メモリ不足、割り当て失敗 
        return false;
    list->link = NULL;                       //ヘッダーノードの後にはまだノードがない 
    return true; 
}
 
int main(){
    Chain list;           //単方向連結リストを指すポインタを宣言 
    //空のリストを初期化 
    InitChain(list);      
    return 0; 
}

ヘッダーノードなしの場合、コード記述がより複雑になります。

最初のデータノードと後続のデータノードの処理では異なるコードロジックが必要です。

空リストと非空リストの処理では異なるコードロジックが必要です。

単方向連結リストの空判定（Empty）

ヘッダーノードなし

//単方向連結リストが空か判定
bool IsEmpty(Chain list){
    if(list == NULL)    
        return true; 
    else 
        return false;
}

//単方向連結リストが空か判定
bool IsEmpty(Chain list){
    return (list==NULL);
}

ヘッダーノードあり

//単方向連結リストが空か判定
bool IsEmpty(Chain list){
    if(list->link == NULL)    
        return true; 
    else 
        return false;
}

//単方向連結リストが空か判定
bool IsEmpty(Chain list){
    return (list->link == NULL);
}

単方向連結リストの位置指定挿入（ListInsert）

ヘッダーノードなし

//i番目の位置に要素eを挿入（ヘッダーノードなし）
bool InsertNode(Chain &list, int position, int value){
    if(position<1)
        return false;
    if(position==1){              //最初のノードへの挿入操作は他のノード操作と異なる
        Node *newNode =  (Node *) malloc(sizeof(Node));
        newNode->value = value;
        newNode->link= list;
        list = newNode;           //ヘッドポインタが新ノードを指す 
        return true;              
    } 
    Node *current;                //ポインタcurrentが現在スキャン中のノードを指す 
    int index = 1;                //現在currentの位置 
    current = list;               //currentは最初のノードを指す（ヘッダーノードではない）
    while(current!=NULL && index<position-1){//i-1番目のノードを見つけるループ 
        current=current->link;
        index++; 
    } 
    if(current==NULL)             //position値が不正
        return false;
    Node *newNode =  (Node *) malloc(sizeof(Node));
    newNode->value = value;
    newNode->link=current->link;
    current->link = newNode;      //ノードnewNodeをcurrentの後に接続 
    return true;                  //挿入成功 
}

ヘッダーノードあり

//i番目の位置に要素eを挿入（ヘッダーノードあり）
bool InsertNode(Chain &list, int position, int value){
    if(position<1)
        return false;
    Node *current;                //ポインタcurrentが現在スキャン中のノードを指す 
    int index = 0;                 //現在currentの位置 
    current = list;               //listはヘッダーノードを指し、ヘッダーノードは0番目のノード（データなし）
    while(current!=NULL && index<position-1){//i-1番目のノードを見つけるループ 
        current=current->link;
        index++; 
    } 
    if(current==NULL)             //position値が不正
        return false;
    Node *newNode =  (Node *) malloc(sizeof(Node));
    newNode->value = value;
    newNode->link=current->link;
    current->link = newNode;      //ノードnewNodeをcurrentの後に接続 
    return true;                  //挿入成功 
}

最良時間計算量：O(1)

最悪時間計算量：O(n)

平均時間計算量：O(n)

指定ノードの後方挿入操作（InsertNextNode）

//後方挿入操作：ノードpの後に要素eを挿入
bool InsertAfter(Node *current, int value){
    if(current==NULL)         
        return false;
    Node *newNode =  (Node *) malloc(sizeof(Node));
    if(newNode==NULL)           //メモリ割り当て失敗 
        return false;
    newNode->value = value;     //ノードnewNodeにデータ要素eを保存 
    newNode->link=current->link;
    current->link = newNode;    //ノードnewNodeをcurrentの後に接続 
    return true;                
}

時間計算量：O(1)

指定ノードの前方挿入操作（InsertPriorNode）

//前方挿入操作：ノードpの前に要素eを挿入
bool InsertBefore(Node *current, int value){
    if(current==NULL)         
        return false;
    Node *newNode =  (Node *) malloc(sizeof(Node));
    if(newNode==NULL)           //メモリ割り当て失敗 
        return false;
    newNode->link = current->link;
    current->link = newNode;    //ノードnewNodeをcurrentの後に接続 
    newNode->value = current->value;  //currentの要素をnewNodeにコピー 
    current->value = value;    //currentの要素をeで上書き 
    return true;                
}

時間計算量：O(1)

単方向連結リストの位置指定削除（ListDelete）

ヘッダーノードなし

bool RemoveNode(Chain &list, int position, int &value){
    if(position<1)
        return false;
    if(position==1){              //最初のノードの削除操作は他のノード操作と異なる
        Node *temp;
        temp = list;    
        value = temp->link->value;
        temp->link->value = null;
        list = temp->link;               //ヘッドポインタが新ノードを指す 
        return true;              
    } 
    Node *current;                //ポインタcurrentが現在スキャン中のノードを指す 
    int index = 0;                //現在currentの位置 
    current = list;               //listはヘッダーノードを指し、ヘッダーノードは0番目のノード（データなし）
    while(current!=NULL && index<position-1){//i-1番目のノードを見つけるループ 
        current=current->link;
        index++; 
    } 
    if(current==NULL)             //position値が不正
        return false;
    if(current->link==NULL)       //i-1番目のノードの後に他のノードがない 
        return false;
    Node *temp = current->link;   //tempを削除ノードを指すようにする 
    value = temp->value;          //valueで要素の値を返す 
    current->link = temp->link;   //ノード*tempをリンクから"切断" 
    free(temp);                   //ノードのストレージ領域を解放 
    return true;                  //削除成功 
}

ヘッダーノードあり

bool RemoveNode(Chain &list, int position, int &value){
    if(position<1)
        return false;
    Node *current;                //ポインタcurrentが現在スキャン中のノードを指す 
    int index = 0;                //現在currentの位置 
    current = list;               //listはヘッダーノードを指し、ヘッダーノードは0番目のノード（データなし）
    while(current!=NULL && index<position-1){//i-1番目のノードを見つけるループ 
        current=current->link;
        index++; 
    } 
    if(current==NULL)             //position値が不正
        return false;
    if(current->link==NULL)       //i-1番目のノードの後に他のノードがない 
        return false;
    Node *temp = current->link;   //tempを削除ノードを指すようにする 
    value = temp->value;          //valueで要素の値を返す 
    current->link = temp->link;   //ノード*tempをリンクから"切断" 
    free(temp);                   //ノードのストレージ領域を解放 
    return true;                  //削除成功 
}

最良時間計算量：O(1)

最悪時間計算量：O(n)

平均時間計算量：O(n)

指定ノードの削除操作（DeleteNode）

//指定ノードpを削除
bool RemoveNode(Node *current){
    if(current==NULL)         
        return false;
    Node *temp = current->link;   //tempを*currentの後続ノードを指すようにする 
    current->value = current->link->value; //後続ノードとデータ域を交換 
    current->link = temp->link;  //ノード*tempをリンクから"切断" 
    free(temp);                   //ノードのストレージ領域を解放 
    return true;        
}

時間計算量：O(1)

単方向連結リストの位置指定検索(GetElem)

//位置指定検索、i番目の要素を返す（ヘッダーノードあり）
Node * FindByPosition(Chain list, int position){
    if(position<1)
        return NULL;
    Node * current;               //ポインタcurrentが現在スキャン中のノードを指す
    int index = 0;                //currentの位置
    current = list;               //listはヘッダーノードを指し、ヘッダーノードは0番目のノード（データなし）
    while(current!=NULL && index<position) { //i番目のノードを見つけるループ 
        current=current->link;
        index++; 
    }
    return current;
}

時間計算量：O(n)

単方向連結リストの値指定検索(LocateElem)

//値指定検索、データ域==eのノードを見つける
Node * FindByValue(Chain list, int value){
    Node *current = list->link;
    //最初のノードからデータ域がeのノードを検索
    while (current!=NULL && current->value !=value)
        current = current->link; 
    return current;               //見つかればそのノードのポインタを返し、なければNULLを返す 
}

時間計算量：O(n)

単方向連結リストの長さ(Length)

//リストの長さを求める（ヘッダーノードあり）
int GetLength(Chain list){
    int length = 0;               //リストの長さをカウント
    Node *current =list;
    while (current->link != NULL){
        current->link;
        length++; 
    } 
    return length;
}

時間計算量：O(n)

単方向連結リストの作成

末尾挿入法

//末尾挿入法（ヘッダーノードあり）
Chain CreateByTailInsert(Chain &list){
    int input;                
    list=(Chain)malloc(sizeof(Node));    //ヘッダーノードを作成 
    Node *newNode,*tail = list;          //tailは末尾ポインタ
    scanf("%d",&input);                   //ノードの値を入力 
    while(input!=9999){                   //9999を入力すると終了 
        newNode=(Node)malloc(sizeof(Node));
        newNode->value =input;
        tail->link=newNode;
        tail = newNode;                   //tailが新しい末尾ノードを指す 
        scanf("%d",&input);
    } 
    tail->link=NULL;                      //末尾ノードのポインタをNULLに設定 
    return list;        
}

時間計算量：O(n)

先頭挿入法

//先頭挿入法（ヘッダーノードあり）
Chain CreateByHeadInsert(Chain &list){
    Node *newNode;
    int input;                
    list=(Chain)malloc(sizeof(Node));    //ヘッダーノードを作成 
    list->link=NULL;                      //初期状態で空のリスト 
    scanf("%d",&input);                   //ノードの値を入力 
    while(input!=9999){                   //9999を入力すると終了 
        newNode=(Node)malloc(sizeof(Node));  //新ノードを作成 
        newNode->value = input;
        newNode->link = list->link;
        list->link = newNode;             //新ノードをリストに挿入、listはヘッダーノード 
        scanf("%d",&input);
    } 
    return list;        
}