Skip to content

Instantly share code, notes, and snippets.

@ser1zw

ser1zw/LinkedList.c

Created June 23, 2015 05:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ser1zw/f36f37fde6c14dfcfc58 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ser1zw/f36f37fde6c14dfcfc58 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ser1zw created this gist Jun 23, 2015.
    194 changes: 194 additions & 0 deletions LinkedList.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,194 @@
    // -*- mode: c; coding: utf-8 -*-
    /*
    * リンクリストの練習
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    /*
    * リストの要素型
    */
    typedef struct _ListElement {
    struct _ListElement* prev; // 前の要素へのポインタ
    struct _ListElement* next; // 次の要素へのポインタ
    char* data; // データ
    } ListElement;

    /*
    * リスト型
    */
    typedef struct {
    ListElement* first; // 先頭の要素へのポインタ
    ListElement* last; // 末尾の要素へのポインタ
    size_t size; // 要素数
    } LinkedList;

    /*
    * 新しく要素を作成する
    * @param data_size 作成する要素のデータサイズ
    * @return 作成した要素へのポインタ（エラー時はNULL）
    */
    ListElement* newElement(size_t data_size) {
    ListElement* elem = (ListElement*)malloc(sizeof(ListElement));
    if (elem == NULL) {
    return NULL;
    }
    elem->data = (char*)malloc(sizeof(char) * data_size);
    if (elem->data == NULL) {
    free(elem);
    return NULL;
    }
    return elem;
    }

    /*
    * 新しくリストを作成する
    * @return 作成したリストへのポインタ（エラー時はNULL）
    */
    LinkedList* newList() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    if (list == NULL) {
    return NULL;
    }
    list->first = NULL;
    list->last = NULL;
    list->size = 0;
    return list;
    }

    /*
    * リストにデータを追加する
    * @param list 対象のリストへのポインタ
    * @param data 追加するデータへのポインタ
    * @param data_size 追加するデータのサイズ
    * @return 成功した場合は0、失敗した場合は-1
    */
    int pushElement(LinkedList* list, char* data, size_t data_size) {
    if (list == NULL) {
    return -1;
    }
    ListElement* elem = newElement(data_size);
    if (elem == NULL) {
    return -1;
    }
    void* ret = memcpy(elem->data, data, data_size);
    if (ret == NULL) {
    return -1;
    }

    if (list->first == NULL) {
    list->first = elem;
    }

    if (list->last == NULL) {
    list->last = elem;
    }
    else {
    list->last->next = elem;
    elem->prev = list->last;
    list->last = elem;
    }
    list->size++;
    return 0;
    }

    /*
    * リストから要素を削除する
    * @param list 対象のリストへのポインタ
    * @param index 削除する要素の番号（0始まり）
    * @return 成功した場合は0、失敗した場合は-1
    */
    int deleteElement(LinkedList* list, size_t index) {
    ListElement* elem = list->first;
    size_t i = 0;
    for (i = 0; elem && i < index; i++) {
    elem = elem->next;
    }
    if (elem == NULL) {
    return -1;
    }
    ListElement* prev = elem->prev;
    ListElement* next = elem->next;

    if (prev == NULL) { // 先頭
    list->first = next;
    }
    else {
    prev->next = next;
    }
    if (next == NULL) { // 末尾
    list->last = prev;
    }
    else {
    next->prev = prev;
    }

    free(elem->data);
    free(elem);
    list->size--;
    return 0;
    }

    /*
    * リストを削除する
    * @param list 対象のリストへのポインタ
    */
    void deleteList(LinkedList* list) {
    ListElement* p = list->first;
    ListElement* tmp = NULL;
    while (p) {
    tmp = p;
    p = p->next;
    free(tmp->data);
    free(tmp);
    }
    free(list);
    }

    void showList(LinkedList* list) {
    ListElement* p = list->first;
    int i = 1;
    while (p) {
    printf(" %d:\t%s\n", i++, p->data);
    p = p->next;
    }
    }

    void showListBackward(LinkedList* list) {
    ListElement* p = list->last;
    int i = list->size;
    while (p) {
    printf(" %d:\t%s\n", i--, p->data);
    p = p->prev;
    }
    }

    int main(int argc, char *argv[])
    {
    LinkedList* list = newList();
    pushElement(list, "123", 4);
    pushElement(list, "456", 4);
    pushElement(list, "789", 4);
    pushElement(list, "123456", 7);
    pushElement(list, "234567", 7);
    pushElement(list, "345678", 7);
    pushElement(list, "456789", 7);

    puts("Forward:");
    showList(list);
    puts("Backward:");
    showListBackward(list);
    puts("-----");
    puts("** Delete elements **");
    deleteElement(list, 0);
    deleteElement(list, 3);
    deleteElement(list, list->size - 1);
    puts("Forward:");
    showList(list);
    puts("Backward:");
    showListBackward(list);

    deleteList(list);
    return 0;
    }